如何在Racket初学者版中用简单递归从无序列表构建二叉搜索树

你要求的不使用累加器、不依赖有序列表、不提前排序的简单递归实现可以按如下思路完成：

• 递归终止条件：输入列表为空时返回empty
• 递归逻辑：
  1. 取列表第一个元素作为当前根节点的key
  2. 遍历剩余元素，拆分为两个子列表：所有小于根key的元素组成左子列表，所有大于根key的元素组成右子列表，等于根key的元素直接去重，和你原有实现逻辑一致
  3. 分别递归处理左子列表生成左子树，递归处理右子列表生成右子树
  4. 组合根、左子树、右子树返回节点即可

以下是完全适配Racket Beginner Student版本的实现代码：

(define-struct node (key left right))
;; A Node is a (make-node Nat BT BT)
;; A binary tree (BT) is one of:
;;  * empty
;;  * Node

;; simple-build-bst: (listof Num) -> BT
;; 不使用累加器、不提前排序、不依赖有序列表的简单递归构建BST
(define (simple-build-bst lst)
  (cond
    [(empty? lst) empty]
    [else
     (local [(define root (first lst))
             (define smaller (filter (lambda (x) (< x root)) (rest lst)))
             (define larger (filter (lambda (x) (> x root)) (rest lst)))]
       (make-node root
                  (simple-build-bst smaller)
                  (simple-build-bst larger)))]))

你可以用示例输入测试：(simple-build-bst (list 1 2 3 5 0 9 3 5 2))，生成的二叉树结构完全符合你的示例要求，且满足二叉搜索树的定义。该实现和你原有累加器逐个插入的逻辑生成的BST结构完全等价。

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