1

我想在 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 添加一个新节点。

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

代码级别为中级学生

4

1 回答 1

0

这：

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

是一种非常奇怪的写法，如果短于两个元素(rest list)，它也可以确保错误。list

改变这一点，我们注意到它仍然会导致空列表错误；所以处理这种可能性的子句必须移到顶部

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

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

分开你的顾虑。每项任务都值得拥有自己的专用功能。以这种方式编写它将使您可以轻松地将这两个任务结合起来，通过对列表枚举函数进行一些小改动，以利用插入函数。

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

于 2017-11-12T15:27:30.543 回答