在 Racket 中使用二叉搜索树

Question

我想在 Racket 中创建一个二叉搜索树。树的结构如下所示：

(define-struct tree-node (left right root))

现在我想在树中添加这些数字：

(define ex-list (list 1 4 6 2 7 8))

我的插入程序代码：

(define (insert-in-tree list tree) 
  (cond
    [(empty? tree) 
      (insert-in-tree (cons (second list) (rest (rest list))) 
                      (make-tree-node empty empty (first list)))]
    [(empty? list) 
      tree]
    [(> (first list) (tree-node-root tree)) 
      (insert-in-tree (cons (second list) (rest (rest list))) 
                      (make-tree-node 
                          (tree-node-left tree) 
                          (make-tree-node empty empty (first list)) 
                          (tree-node-root tree)))]
    [(< (first list) (tree-node-root tree)) 
      (insert-in-tree (cons (second list) (rest (rest list))) 
                      (make-tree-node 
                          (make-tree-node empty empty (first list)) 
                          (tree-node-right tree) 
                          (tree-node-root tree)))]
    [(= (first list) (tree-node-root tree)) 
      (insert-in-tree (cons (second list) (rest (rest list))) tree)]
    [else tree]))

我对代码的看法：

首先它检查给定的树是否为空，如果是，将创建一个新树
当列表中的第一个数字大于树的根时，它将被添加到右侧，较小的添加到左侧
相同的数字将被忽略

我的问题： 当树只是 1 并且过程将 4 添加为新的根元素时右边。当我添加 6 时，它将替换 4，但它应该为 6 添加一个新节点。

我知道这个版本的代码不起作用，因为在列表只有一个元素的情况下，这个代码不起作用。

代码水平中级

Answer 1

这个：

(cons (second list) (rest (rest list)))

是一种非常奇怪的写(rest list)的方式，如果list比两个元素短，这也确保了一个错误。

改变它，我们注意到它仍然会导致空列表错误；所以处理 this 不测事件的子句必须移到顶部

(define (insert-in-tree list tree)
  (cond
    [ (empty? list)
      tree ]
    [ (empty? tree)
      (insert-in-tree (rest list)
                      (make-tree-node empty empty (first list))) ]
    [ (> (first list) (tree-node-root tree))
      (insert-in-tree (rest list)
                      (make-tree-node
    ........

至少现在不会报错:

> (insert-in-tree (list 1 2 3) empty)
(make-tree-node '() (make-tree-node '() '() 3) 1)
> (insert-in-tree (list 1 2 3 4 3 5) empty)
(make-tree-node '() (make-tree-node '() '() 5) 1)
>

但是从头开始，你的方法都是错误的。您的代码混淆了两个本质上独立的问题：枚举列表元素和将元素插入树中。

分开您的顾虑。每个任务都应该有自己的专用功能。以这种方式编写将使您很容易将这两个任务结合起来，只需对列表枚举函数进行一些小改动，即可使用插入函数。

插入函数将实现比较逻辑，并利用...插入函数，在需要时插入分支，因为树枝本身就是树。

在 Racket 中使用二叉搜索树

Work with binary search trees in Racket

tree

scheme

binary-search-tree

racket

racket-student-languages