algorithm - 在计划中制作树

Question

(define (entry tree) (car tree))
(define (left-branch tree) (cadr tree))
(define (right-branch tree) (caddr tree))
(define (make-tree entry left right) (list entry left right))

(define (mktree order items_list)
  (cond ((= (length items_list) 1)
         (make-tree (car items_list) '() '()))
        (else 
         (insert2 order (car items_list) (mktree order (cdr items_list))))))

(define (insert2 order x t)
  (cond ((null? t) (make-tree x '() '()))
      ((order x  (entry t))
       (make-tree (entry t) (insert2 order x (left-branch t)) (right-branch t)))
      ((order  (entry t) x )
       (make-tree (entry t) (left-branch t) (insert2 order x (right-branch t))))
      (else t)))

结果是：

(mktree (lambda (x y) (< x y)) (list 7 3 5 1 9 11))
(11 (9 (1 () (5 (3 () ()) (7 () ()))) ()) ())

但我试图得到：

(7 (3 (1 () ()) (5 () ())) (9 () (11 () ())))

问题出在哪里？

Answer 1

在这里，试试这个：

(define (mktree order lst)
  (let loop ((lst  lst)
             (tree '()))
    (if (null? lst)
        tree
        (loop (cdr lst) (insert order (car lst) tree)))))

(define (insert order ele tree)
  (cond ((null? tree)
         (make-tree ele '() '()))
        ((order ele (entry tree))
         (make-tree (entry tree)
                    (insert order ele (left-branch tree))
                    (right-branch tree)))
        ((order (entry tree) ele)
         (make-tree (entry tree)
                    (left-branch tree)
                    (insert order ele (right-branch tree))))
        (else tree)))

它按预期工作：

(mktree < '(7 3 5 1 9 11)) 
> '(7 (3 (1 () ()) (5 () ())) (9 () (11 () ())))

您的insert2过程很好，但是该mktree过程应该表示为列表上的迭代，累加器跟踪到目前为止插入的元素的树。这有两个效果：

1. mktree现在是尾递归的并且
2. 列表中元素的迭代顺序颠倒了

最后一个特别会解决您的问题：即使您的解决方案生成二叉树，order 属性也会与您的预期相反。请注意，反转输入列表也将起作用。

Answer 2

Oscar Lopez 的答案是正确的，由于 insert2 函数调用的递归性质，它首先使 S 表达式完全展开，然后从列表的最后 2 个元素开始评估（在您的情况下为 9 和 11） ...作为证明，您可以看到，如果您以相反的顺序放入列表中，您会得到正确的结果：

(mktree (lambda (x y) (< x y)) (list 11 9 1 5 3 7))

(7 (3 (1 () ()) (5 () ())) (9 () (11 () ())))