Scheme语言实现BST添加节点异常求助：仅返回根节点与null

你的问题出在递归添加节点后没有更新当前节点的子树引用，原函数最后直接返回了原始节点，导致新创建的节点无法挂载到树上。

问题代码的核心缺陷 #

在(< value x)和(> value x)分支中，你只是递归调用了tree-add处理子树，但没有将递归返回的新子树替换掉原节点的left或right字段，最后直接返回原tree，相当于白做了递归操作，自然无法添加新节点。

修复后的代码 #

(struct tree-node (val left right) #:transparent)

(define (tree-add tree value)
  (if (null? tree)
      (tree-node value null null)
      (let ([x (tree-node-val tree)])
        (cond
          [(= value x) tree] ; 值已存在，直接返回原节点
          [(< value x)
           ; 创建新节点，保留原val和right，更新left为递归添加后的子树
           (tree-node x (tree-add (tree-node-left tree) value) (tree-node-right tree))]
          [(> value x)
           ; 创建新节点，保留原val和left，更新right为递归添加后的子树
           (tree-node x (tree-node-left tree) (tree-add (tree-node-right tree) value))]))))

测试示例 #

调用示例：

(define my-tree null)
(set! my-tree (tree-add my-tree 5))
(set! my-tree (tree-add my-tree 3))
(set! my-tree (tree-add my-tree 7))
my-tree ; 输出：(tree-node 5 (tree-node 3 #f #f) (tree-node 7 #f #f))

这样就能正确将新节点挂载到二叉搜索树的对应位置了。

内容的提问来源于stack exchange，提问作者Gary Xiong