scheme - 二叉树插入节点程序未按预期工作(方案)

Question

我实现了一个在二叉树中插入节点的函数。
树节点是 (left-node key right-node) 形式的列表。
(insert tree n) 是我的插入节点函数，其中 tree 是二叉搜索树中的树节点列表，我想添加键值 n 作为新节点。

因此，(insert '(((() 4 ()) 5 (() 2 ())) 6 ()) 7) 给出的输出为
(((() 4 ()) 5 (() 2 ())) 6 (() 7 ()))。

现在，我想做的是这样的:
1。定义值列表。 (define (f) (list '1 `2 `3 `4 `5 ))
2。循环遍历列表并在树中一个接一个地输入值，从一棵空树开始。

因此，当我尝试执行第 2 步时，我执行了以下操作:

(define x ()) ;; Tree x is initially empty
(insert x 2)  ;; This prints (() 2 ())
(insert x 1)  ;; This prints (() 1 ()). I want it to be ((() 1 ()) 2 ()).
(insert x 3)  ;; This prints (() 3 ()). I want it to be ((() 1 ()) 2 (() 3 ())).

这就是我卡住的地方。
我在下面提供了我的插入功能。

(define (left tree) (list-ref tree 0))
(define (value tree) (list-ref tree 1))
(define (right tree) (list-ref tree 2))

(define (insert tree n)
  (cond
    [( null? tree ) ( list () n () )]
    [(< n (cadr tree)) (list (insert (car tree) n) (cadr tree) (caddr tree))] 
    [(> n (cadr tree)) (list (car tree) (cadr tree) (insert (caddr tree) n))] 
    [else tree] 
  )
)

有人可以建议我如何实现我的预期输出吗？

Answer 1

您的代码存在三个问题。请注意，在下文中我对代码有点粗鲁:我只是直言不讳，因为我写得很快，而且我不是试图对你个人无礼!

你还没有定义你需要的所有抽象

您至少需要一个构造树节点的函数、一个测试空树的函数和一个表示空树的对象。这是一组更完整的抽象:

(define null-tree '())

(define (tree-null? tree)
  (eq? tree null-tree))

(define (make-tree-node left key right)
  (list left key right))

(define (left tree)
  (list-ref tree 0))

(define (value tree)
  (list-ref tree 1))

(define (right tree)
  (list-ref tree 2))

您的insert 函数没有使用抽象

它没有使用您定义的那些，更不用说缺少的那些，导致它是一个无法理解的 1960 年代风格的困惑。这是它的一个版本，它在整个过程中都使用了抽象(这也修复了一些奇怪的间距和悬垂的括号问题，这些问题有助于没有人阅读您的代码):

(define (insert tree n)
  (cond
    [(tree-null? tree)
     (make-tree-node null-tree n null-tree)]
    [(< n (value tree))
     (make-tree-node (insert (left tree) n)
                     (value tree)
                     (right tree))]
    [(> n (value tree))
     (make-tree-node (left tree)
                     (value tree)
                     (insert (right tree) n))]
    [else tree]))

你还没明白insert是一个函数

它获取一棵树并返回一棵添加了元素的树，而不是获取一棵树并通过副作用向其添加元素。 insert 从不修改它的任何参数，而是构造一个合适的新树(或者如果要添加的元素已经存在，则返回现有树)。

因此，例如，为了添加一系列元素，您需要使用添加了这些元素的 insert 构建一个树序列:

(define (insert-elements tree elts)
  (if (null? elts)
      tree
      (insert-elements (insert tree (first elts)) (rest elts))))

现在:

> (insert-elements null-tree '(7 1 2 3 4 7 202 48 20 0))
'(((() 0 ()) 1 (() 2 (() 3 (() 4 ())))) 7 (((() 20 ()) 48 ()) 202 ()))

---

为什么要使用抽象

如果我改变树的抽象:

(define null-tree '/)

(define (tree-null? tree)
  (eq? tree null-tree))

(define (make-tree-node left key right)
  (vector left key right))

(define (left tree)
  (vector-ref tree 0))

(define (value tree)
  (vector-ref tree 1))

(define (right tree)
  (vector-ref tree 2))

然后我可以对这个新的树类型使用完全相同的函数:

> (insert-elements null-tree '(7 1 2 3 4 7 202 48 20 0))
'#(#(#(/ 0 /) 1 #(/ 2 #(/ 3 #(/ 4 /)))) 7 #(#(#(/ 20 /) 48 /) 202 /))