bst（方案）中所有小于 x 的值

Question

有人说这个问题是重复的。我看了另一个问题，它是一种与 scheme 不同的编程语言。

我正在尝试编写一个函数（小于 x 树），它将显示树中小于或等于 x 的所有节点。

我有一个旧代码 return 是树的最小值，但我不知道如何 return 值列表？这只看树的左边。我如何在两个子树（左和右）中查看它？

(define (bst-smallest bs-tree)
  (cond ((null? bs-tree)
     '())
    ((null? (bst-left bs-tree))
     (bst-value bs-tree))
    (else
     (bst-smallest (bst-left bs-tree)))))

Answer 1

一个简单的解决方案是迭代树（我将使用 in-order traversal 来保持顺序）并在列表中累积恰好小于或等于给定值的所有元素.请注意，第二个条件利用树的顺序来避免遍历树上必然大于我们要查找的元素的元素：

(define (bst-lte bs-tree value)
  (cond ((null? bs-tree)                     ; if tree is empty
         '())                                ; return empty list
        ((> (bst-value bs-tree) value)       ; if current element > value
         (bst-lte (bst-left bs-tree) value)) ; go to the left
        (else                                ; else advance recursion
         (append                             ; `append` the result
          (bst-lte (bst-left bs-tree) value) ; traverse the left subtree
          (list (bst-value bs-tree))         ; add it to the answer
          (bst-lte (bst-right bs-tree) value))))) ; traverse the right subtree

Answer 2

您不想直接 return 值列表。先建一棵树会更有意义。

想想你的基本情况。调用输入树iTree和目标值x

iTree 是空的 -- return 空树。
iTree节点大于x -- 在左树上递归

否则用iTree的节点建一棵树，左边是iTree的左树，右边是iTree的右树递归。

 (define (lessthan x tree)
      (define (helper itree)
        (cond ((empty? itree) empty-tree)
              ((> (node itree) x) (helper (left-tree itree)))
              (else (make-tree (node itree) 
                               (left-tree itree) 
                               (helper (right-tree itree))))))
              (tree->list (helper tree)))

这不是工作代码，但应该很容易适应您的实施。

bst（方案）中所有小于 x 的值

all values less than x in bst (scheme)

tree

scheme

binary-tree

binary-search-tree