bst (方案)中所有小于x的值
bst (方案)中所有小于x的值
提问于 2015-11-16 01:04:37
有人说这个问题是重复的。我看了另一个问题，它是一种不同于方案的编程语言。
我试图编写一个函数(小于x树)，它将显示树中小于或等于x的所有节点。
我有一个旧代码，它返回树的最小值，但我不知道如何返回值列表？这只看在树的左边。在两个子树(左和右)中，它的外观如何？
(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)))))回答 2
Stack Overflow用户
回答已采纳
发布于 2015-11-16 02:05:11
一个简单的解决方案是在树上迭代(我将使用有序遍历来保持顺序)，并将所有恰好小于或等于给定值的元素累加到列表中。请注意，第二个条件利用了树的顺序来避免遍历树上的元素，这些元素必须大于我们要寻找的元素：
(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 subtreeStack Overflow用户
发布于 2015-11-16 02:05:12
您不想直接返回一个值列表。先建一棵树就更有意义了。
想想你的基本案子。调用输入树iTree和目标值x
- iTree为空--返回空树。
- iTree节点大于左侧树上的x-重排。
- 否则，用iTree的节点构建一棵树，在左侧构建iTree的左侧树，在右侧的iTree树上构建递归树。 (定义(小于x树)(定义(助手itree) ) (cond (空的)？( itree) (空树) ((> (节点itree) x) (助手(左侧树itree) )(其他(做树(节点itree) (左树itree)(帮助树(右树itree)(树->列表(助手树)
这不是有效的代码，但是应该很容易适应您的实现。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/33727072
复制相关文章
相似问题
腾讯云开发者
