将值插入方案中的二叉树中
将值插入方案中的二叉树中
提问于 2015-11-01 09:21:33
我试图创建一个函数，将一个值插入到二进制搜索树中。函数中的条件似乎正常工作，但我不太确定当我到达列表中的空点时，如何实际插入该值。
bst-元素指的是另一个函数，我检查该值是否已经存在于树中，因为树不应该有重复的值。
(define (bst-insert item bst-tree)
(cond ((bst-element? item bst-tree)bst-tree)
((null? bst-tree) ??? )
((< item (bst-value bst-tree))(bst-insert item (bst-left bst-tree)))
((> item (bst-value bst-tree))(bst-insert item (bst-right bst-tree)))))回答 1
Stack Overflow用户
回答已采纳
发布于 2015-11-01 11:27:52
如果您想以一种功能的方式在树中插入一个值，即没有副作用，您不能假设只有当您到达应该插入新值的叶子时，才有一些事情要做。相反，您应该在访问树时重新构建树，这样最终的结果就是在正确位置插入项的新树。
由于您没有展示树是如何实现的，我假设空树被表示为'()，并且存在一个函数(make-bst item left right)来构建具有特定item、left子树和right子树的树。在这些假设下，以下是一个可能的解决方案：
(define (bst-insert item bst-tree)
(cond ((null? bst-tree) (make-bst item '() '()))
((= (bst-value bst-tree) item) bst-tree)
((< item (bst-value bst-tree))
(make-bst (bst-value bst-tree)
(bst-insert item (bst-left bst-tree))
(bst-right bst-tree)))
(else (make-bst (bst-value bst-tree)
(bst-left bst-tree)
(bst-insert item (bst-right bst-tree))))))请注意，如果项目已经存在，则在此函数中进行检查，而不需要将工作与另一个函数重复。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/33460740
复制相关文章
相似问题
腾讯云开发者
