不明白這個計劃功能使二叉樹

Question

我聽不太懂這些功能：

(define (list->tree elements) 
    (car (partial-tree elements (length elements)))) 

(define (partial-tree elts n) 
    (if (= n 0) 
    (cons '() elts) 
    (let ((left-size (quotient (- n 1) 2))) 
     (let ((left-result (partial-tree elts left-size))) 
     (let ((left-tree (car left-result)) 
      (non-left-elts (cdr left-result)) 
      (right-size (- n (+ left-size 1)))) 
     (let ((this-entry (car non-left-elts)) 
       (right-result (partial-tree (cdr non-left-elts) 
              right-size))) 
      (let ((right-tree (car right-result)) 
       (remaining-elts (cdr right-result))) 
      (cons (make-tree this-entry left-tree right-tree) 
        remaining-elts)))))))) 

我猜partial-tree將整個列表分爲二，遞歸使得各佔一半的子樹。但是我完全迷失了所有涉及的car/cdr。具體做法是：

1. 爲什麼car需要(car (partial-tree elements (length elements)))？

2. 爲什麼left-result在(let ((left-result (partial-tree elts left-size)))佔據整個列表elts而不是一半呢？

3. 什麼是這個remaining-elts：

   (cons (make-tree this-entry left-tree right-tree) 
        remaining-elts)))) 
   

我試圖用一個測試用例'(1 3 5 7 9)，但是當我看到遞歸調用(partial-tree elts left-size)，我完全糊塗了，不知道是什麼left-result,left-tree,right-result即可。

我真的很感激提示如何思考這個。

Answer 1

如果您想知道遞歸如何工作，那麼最好記下所有步驟（使用少量輸入）。假設我們有(1 3 5 7 9)作爲list->tree的輸入。然後partial-tree會做以下步驟：

;; > (partial-tree '(1 3 5 7 9) 5) 
;; left-size : 2 
;; >> *1 (partial-tree '(1 3 5 7 9) 2) 
;;  left-size : 0 
;;  >>> *1 (partial-tree '(1 3 5 7 9) 0) 
;;  >>>> n == 0 
;;  <<<< '(() . (1 3 5 7 9)) 
;;  left-result : '(() . (1 3 5 7 9)) 
;;  left-tree  : '() 
;;  non-left-elts : '(1 3 5 7 9) 
;;  this-entry : 1 
;;  right-size : 1 
;;  >>> *2 (partial-tree '(3 5 7 9) 1) 
;;  left-size : 0 
;;  >>>> *1 (partial-tree '(3 5 7 9) 0) 
;;   >>>>> n == 0 
;;   <<<<< '(() . (3 5 7 9)) 
;;  left-result : '(() . (3 5 7 9)) 
;;  left-tree  : '() 
;;  non-left-elts : '(3 5 7 9) 
;;  this-entry : 3 
;;  right-size : 0 
;;  >>>> *2 (partial-tree '(5 7 9) 0) 
;;   >>>>> n == 0 
;;   <<<<< '(() . (5 7 9)) 
;;  right-tree  : '() 
;;  remaining-elts : '(5 7 9) 
;;  <<<< *3 '(#(() 3()) . (5 7 9)) 
;;  right-result : '(#(() 3()) . (5 7 9)) 
;;  right-tree : '#(() 3()) 
;;  remaining-elts : '(5 7 9) 
;;  <<< '(#(() 1 #(() 3())) . (5 7 9)) 
;; left-result : '(#(() 1 #(() 3())) . (5 7 9)) 
;; left-tree  : #(() 1 #(() 3())) 
;; non-left-elts : '(5 7 9) 
;; this-entry : 5 
;; >> *2 (partial-tree '(7 9) 2) 
;;  left-size : 0 
;;  >>> *1 (partial-tree '(7 9) 0) 
;;  >>>> n == 0 
;;  <<<< '(() . (7 9)) 
;;  left-result : '(() . (7 9)) 
;;  left-tree  : '() 
;;  non-left-elts : '(7 9) 
;;  this-entry : 7 
;;  right-size : 1 
;;  >>> *2 (partial-tree '(9) 1) 
;;  left-size : 0 
;;  >>>> *1 (partial-tree '(9)) 
;;   >>>>> n == 0 
;;   <<<<< '(() . (9)) 
;;  left-result : '(() . (9)) 
;;  left-tree  : '() 
;;  non-left-elts : '() 
;;  this-entry : 9 
;;  right-size : 0 
;;  >>>> *2 (partial-tree '() 0) 
;;   >>>>> n == 0 
;;   <<<<< '(() .()) 
;;  right-result : '(() .()) 
;;  right-tree  : '() 
;;  remaining-elts : '() 
;;  <<<< *3 '(#(() 9()) .()) 
;;  right-result : '(#(() 9()) .()) 
;;  right-tree  : '#(() 9()) 
;;  remaining-elts : '() 
;;  <<< *3 '(#(() 7 #(() 9())) .()) 
;; right-result : '(#(() 7 #(() 9())) .()) 
;; right-tree  : 
;; remaining-elts : '() 
;; << *3 '(#(() 1 #(() 3())) 5 #(() 7 #(() 9())) .()) 
;; < '(#(() 1 #(() 3())) 5 #(() 7 #(() 9())) .()) 

我以前做的*1是第一partial-tree調用其構造左樹。 *2是構建右樹的第二個partial-tree調用。然後*3是非零輸入的返回值。爲了便於理解，我還爲每個變量設置了什麼樣的值。

現在的你的問題的答案：

1. 由於partial-tree結果中包含2個元素，構造樹，其餘的元素（這是無效）。
2. 左邊的樹應該總是將輸入列表的第一個元素作爲輸入。然後將其餘的元素傳遞給正確的樹形結構。請記住，這是遞歸，所以每個正確的樹構造都會減少元素並調用左樹構造。
3. 它是在下一次迭代中構建的剩餘元素。最後它將是空的。

希望這會有助於你的理解。

Answer 2

廣告1）

(partial-tree elts n)返回一個對兩個值之一：第一值是與elts第一n元件和所述第二值的樹是elts剩餘元素的列表（其可以包含更多元素比n）。

廣告2） 大小left-size確定列表中使用的元素數量。 沒有必要先修剪列表。

Ad 3）元素n + 1，n + 2等elts。即沒有用於製作樹的元素。

#lang racket 
(define (list->tree elements) 
    (car (partial-tree elements (length elements)))) 

(define (make-tree this left-tree right-tree) 
    (match (list left-tree this right-tree) 
    [(list '() x '()) (list x)] 
    [(list '() x r) (list x r)] 
    [(list l x '()) (list l x)] 
    [(list l x r) (list l x r)])) 

(define (partial-tree elts n) 
    (if (= n 0) 
     (cons '() elts) 
     (let* ([left-size  (quotient (- n 1) 2)] 
      [left-result (partial-tree elts left-size)] 
      ; left result is now a pair of 
      [left-tree  (car left-result)]  ; a tree with (n-1)/2 elementer 
      [non-left-elts (cdr left-result)]  ; a list of elements not in left-tree 

      [this-entry  (car non-left-elts)] ; the (n-1)/2+1'th element 

      [right-size  (- n left-size 1)]  ; n - left-size - 1 

      ; note: left-size + 1 + right-size = n 

      [right-result (partial-tree (cdr non-left-elts) right-size)] 
      [right-tree  (car right-result)] ; a tree with n - left-size - 1 elements 
      [remaining-elts (cdr right-result)]) ; element n+1, n+2, ... of elts 
     (cons (make-tree this-entry left-tree right-tree) ; a tree with n elements 
       remaining-elts))))       ; element n+1, n+2, ... of elts 

(partial-tree '(a b c d e f g h) 1) 
(partial-tree '(a b c d e f g h) 2) 
(partial-tree '(a b c d e f g h) 3) 
(partial-tree '(a b c d e f g h) 4) 
(partial-tree '(a b c d e f g h) 5) 
(partial-tree '(a b c d e f g h) 6) 
(partial-tree '(a b c d e f g h) 7) 
(partial-tree '(a b c d e f g h) 8) 

輸出：

'((a) b c d e f g h) 
'((a (b)) c d e f g h) 
'(((a) b (c)) d e f g h) 
'(((a) b (c (d))) e f g h) 
'(((a (b)) c (d (e))) f g h) 
'(((a (b)) c ((d) e (f))) g h) 
'((((a) b (c)) d ((e) f (g))) h) 
'((((a) b (c)) d ((e) f (g (h)))))