使用Racket实现二叉树：编写递归插入函数tree-insert

问题背景 #

已知 '(6 (3 (2) (5)) (7 () (9))) 是一棵排序二叉树，需要编写递归函数 tree-insert，接收一棵二叉树和一个数字，返回插入该数字后的新二叉树。题目给出的测试示例如下：

• (tree-insert 8 '()) 应返回 '(8)
• (tree-insert 5 '(8)) 应返回 '(8 (5))
• (tree-insert 3 '(6 () (7))) 应返回 '(6 (3) (7))
• (tree-insert 4 '(6 (3) (7))) 应返回 '(6 (3 () (4)) (7))

核心逻辑 #

排序二叉树的插入规则清晰明确：

• 若当前树为空，直接生成以目标值为根的单节点树。
• 若目标值小于当前根节点值，递归插入到左子树，保留原根节点和右子树。
• 若目标值大于当前根节点值，递归插入到右子树，保留原根节点和左子树。
• （注：示例未涉及重复值，这里默认忽略重复值直接返回原树；若需处理重复，可调整为插入左/右子树）

Scheme 代码实现 #

(define (tree-insert val tree)
  (cond
    ; 空树直接返回新节点
    ((null? tree) (list val))
    (else
     (let ((root (car tree))
           (left (if (>= (length tree) 2) (cadr tree) '()))
           (right (if (>= (length tree) 3) (caddr tree) '())))
       (cond
         ((< val root)
          ; 插入左子树，根据原树结构调整返回的列表长度
          (if (null? right)
              (list root (tree-insert val left))
              (list root (tree-insert val left) right)))
         ((> val root)
          ; 插入右子树，同理处理列表长度
          (if (null? left)
              (list root left (tree-insert val right))
              (list root left (tree-insert val right))))
         ; 遇到重复值直接返回原树
         (else tree))))))

示例验证 #

用题目给出的测试用例验证：

1. (tree-insert 8 '()) → '(8)，符合预期。
2. (tree-insert 5 '(8)) → '(8 (5))，正确插入左子树。
3. (tree-insert 3 '(6 () (7))) → '(6 (3) (7))，左子树为空时成功插入新节点。
4. (tree-insert 4 '(6 (3) (7))) → '(6 (3 () (4)) (7))，在左子树的右分支插入节点，完全匹配示例结果。

内容的提问来源于stack exchange，提问作者Anoosha Syed