在方案中将值插入二叉搜索树

Question

我正在尝试创建一个将值插入二叉搜索树的函数。函数内的条件似乎工作正常，但我不太确定一旦到达列表中应该去的空点后如何实际插入值。

bst-element 指的是另一个函数，我检查该值是否已经存在于树中，因为树应该没有重复项。

(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)))))

Answer 1

如果您想以函数式方式在树中插入一个值，即没有副作用，您不能假设 只有 当您到达您应该在其中插入新值的叶子。相反，您应该在访问树时 重建 树，以便最终结果是在正确位置插入项目的新树。

由于您没有显示树是如何实现的，我假设空树表示为 '()，并且存在一个函数 (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))))))

请注意，检查项目是否已存在是在该函数内进行的，无需与另一个函数重复工作。