在沒有葉子/節點的二叉樹中計算節點？在計劃中？

我試圖創建一個函數，返回給定的二叉樹中的節點數，但我沒有訪問該節點？和葉子？在R5RS語言中起作用。另外，我不太瞭解這種函數的終止條件，因爲我嘗試的大多數變體都會導致內存不足。感謝您提前提供任何幫助。在沒有葉子/節點的二叉樹中計算節點？在計劃中？

(define (make-tree value left right) 
    (list value left right)) 

(define (value tree) 
    (car tree)) 

(define (left tree) 
    (cadr tree)) 

(define (right tree) 
    (caddr tree))  

(define (tree-node-count t) 
    (cond ((null? t)0) 
     ((...?) 
     (else (+ 
       (tree-node-count left) 
       (tree-node-count right)))))

來源

2015-10-28 TPerson

R5RS方案中沒有'node？'或'leaf？'*過程*。就像'value'和'left'一樣，它們需要根據您對節點的建模方式來創建。 – Sylwester

我問的問題是如何在沒有它們的情況下創建這個功能？我不太清楚如何定義它們。我最好的嘗試是（定義（leaf？n）（和（equal？left'（））（equal？right'（）））），當我給它一個葉子時返回#f。 – TPerson

事實上，你不需要一個leaf?或node?過程中，如果我們計算節點的數量，只需添加1爲他們每個人：

(define (tree-node-count t) 
    (cond ((null? t) 0) 
     (else (+ 1 
       (tree-node-count (left t)) 
       (tree-node-count (right t))))))

來源

2015-10-28 01:08:12

當我給這個函數列表'（5 1 10）時，它的內存不足。這是（左）和（右）我定義的錯？ – TPerson

讓我檢查... –

@TPerson我的錯誤，遞歸中的參數名稱錯誤。請再試一次，並注意''（5 1 10）''不是一個正確的樹，用這個代替：'（tree-node-count'（5（）（）））' –

有沒有在Scheme中執行二叉樹的標準方法，因此程序（如left和right,leaf?和node?）對建模數據的不同方式具有不同的實現。例如。下面是一個使用矢量：

(define TYPE-TREE (vector 'TREE)) ; private 

(define (make-tree value left right) 
    (vector TYPE-TREE value left right)) 

(define (tree? tree) 
    (and (vector? tree) 
     (eq? (vector-ref tree 0) TYPE-TREE))) 

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

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

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

(define (tree-node-count tree) 
    (let aux ((tree tree) (count 0)) 
    (if (not (tree? tree)) 
     count 
     (aux (tree-right tree) 
      (aux (tree-left tree) (+ 1 count)))))) 

(define test (make-tree 5 (make-tree 2 '() '()) (make-tree 10 '() '()))) 
(tree-node-count test) ; ==> 3

當然，你會在一個庫中把這個包，並保持TYPE-TREE隱藏。要回答您的問題，您需要將其過程替換爲其實施。在上述模型中的情況下tree-node-count是這樣的：

(define (tree-node-count tree) 
    (let aux ((tree tree) (count 0)) 
    (if (not (and (vector? tree) 
        (eq? (vector-ref tree 0) TYPE-TREE))) 
     count 
     (aux (vector-ref tree 3) 
      (aux (vector-ref tree 2) (+ 1 count))))))

正如你可以看到它的原程序的身體的一個簡單的替換。我當然會反對，因爲這隻會讓代碼和程序員的意圖不太清楚。刪除抽象並不會贏得你的觀點。

來源

2015-10-28 12:35:22 Sylwester

在沒有葉子/節點的二叉樹中計算節點？在計劃中？

回答

相關問題