方案二叉搜索樹

Question

我已經定義輔助功能是：

;; returns value of node 
(define (value node) 
    (if (null? node) '() 
     (car node))) 

;; returns left subtree of node 
(define (left node) 
    (if (null? node) '() 
     (cadr node))) 

;; returns right subtree of node 
(define (right node) 
    (if (null? node) '() 
     (caddr node))) 

，我試圖寫一個函數leaves的左到右，返回，以便與樹的葉子列表。

(define (leaves tree) 
    (if (and (?null (left tree)) (?null (right tree))) 
     ??? 
     (leaves (left tree)) (leaves (right tree)))) 

但那是據我可以得到

例如：（葉 '（1（2（）（））（3（）（））））應該評估爲'（2 3 ）

Answer 1

在你到目前爲止，???將需要評估葉的價值，即。因爲它是迭代的基本情況。另外，您將需要結合您在迭代情況下從基本案例中獲得的值。 list通常是一個很好的第一選擇，當你需要結合多個結果cons通常是我的第二次嘗試。考慮這些建議，您leaves功能如下：

(define (leaves tree) 
    (if (and (null? (left tree)) (null? (right tree))) 
     (value tree) 
     (list (leaves (left tree)) (leaves (right tree))))) 

，當您的(leaves '(1 (2()()) (3()())))樣品進行確實評估爲(2 3)。

然而;你沒有完成！我們只用1級遞歸進行測試。如果我們製作一棵更大的樹，會怎樣像這樣：(leaves '(1 (2 (4()()) (5()())) (3 (6()()) (7()()))))運行這個給出((4 5) (6 7))。這些都是正確的順序值，但是我們有太多的結構，括號太多。這是你在整個計劃生涯中遇到的一個典型問題，所以讓我解釋爲什麼會發生這種情況，以及如何着手解決問題。

如果看看我們的if表格的兩個分支，你會注意到(value tree)返回一個原子或在這種情況下的一個數字。 else分支採用???中的兩個，並將其轉換爲???的列表。我們將多次執行else分支 - 任何時候我們都不在基本情況下。這意味着我們將繼續換行，換行並換行到更深入更深的列表結構中。所以這就是我們所做的。

讓我們在我們的基本情況下返回一個列表，並將我們的列表保持在遞歸情況下。要在我們的基本情況下返回一個列表，只需返回(list (value tree))而不僅僅是(value tree)。在遞歸情況下，我們需要一個帶有2個列表的函數，並將它們組合起來而不需要創建更深的列表。這樣的功能確實存在 - append。因此，讓我們看看我們的leaves功能貌似現在：

(define (leaves tree) 
     (if (and (null? (left tree)) (null? (right tree))) 
      (list (value tree)) 
      (append (leaves (left tree)) (leaves (right tree))))) 

間奏曲 - 測試用例

球拍具有非常低的障礙稱爲rackunit進入測試套件庫。讓我們把幾個快速的測試用例放在文件的底部。

(require rackunit) 
;;empty tree 
(check-equal? (leaves '()) '()) 

;;simple balanced tree 
(check-equal? 
(leaves '(1 (2()()) (3()()))) 
'(2 3)) 

;;larger balanced tree 
(check-equal? 
(leaves '(1 (2 (4()()) (5()())) (3 (6()()) (7()())))) 
'(4 5 6 7)) 

;;unbalanced tree 
(check-equal? 
(leaves '(1 (2 (4()())()) (3()()))) 
'(4 3)) 

近日，球拍已增加了對submodules支持和具體的支持測試子模塊，如果你是好奇，想看看他們。

---

回到我們的葉子問題。運行我們的測試，我們注意到我們的功能在不平衡的樹上表現不佳。當我們有一個節點只有1片葉時，我們會得到額外的()。這是因爲無論何時我們處於非葉節點時，我們都在遍歷左右子樹。我們真正需要的是我們的if另外兩個案例。我們可以嵌套if，但方案的cond形式更有意義。現在

，我們的目標填寫模板是：

(define (leaves tree) 
    (cond [(leaf? tree) (...)] 
    [(and (has-left? tree) (has-right? tree)) 
    (...)] 
    [(has-left? tree) (...)] 
    [(has-right? tree) (...)] 
    [else (error "should never get here")])) 

，我會停在那裏的情況下，這是家庭作業，並給你認識的滿意度和解決這個休息方式。我希望我的解釋給了你更多的方向，只是「這是代碼」的答案。

Answer 2

好吧，這好像你在做Breadth First Search，但如果你有兩個孩子（或者只有一個孩子，如果你不想打印只有一個孩子的節點）的變化， 。

我會盡力解決這個問題，然後改變你的解決方案來解決這個問題。

Answer 3

(define (list-of-leaves tree) 
    (if(leaf? tree) 
    (list (node tree)) 
    (cond((right-branch-only? tree)(list-of-leaves (right-branch tree))) 
      ((left-branch-only? tree)(list-of-leaves (left-branch tree))) 
      (else(append (list-of-leaves (left-branch tree)) 
         (list-of-leaves (right-branch tree)))))))