化妆树

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. 迭代顺序在该列表中的元素反转

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

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