如何獲取二叉樹的大小？

Question

我有一個非常簡單的二進制樹狀結構，是這樣的：

struct nmbintree_s { 
    unsigned int size; 
    int (*cmp)(const void *e1, const void *e2); 
    void (*destructor)(void *data); 
    nmbintree_node *root; 
}; 

struct nmbintree_node_s { 
    void *data; 
    struct nmbintree_node_s *right; 
    struct nmbintree_node_s *left; 
}; 

有時我需要提取另一個「樹」，我需要以更新的獲取大小的「提取的樹」初始'樹'的大小。

我想兩種做法：

1）使用遞歸函數，是這樣的：在一個反覆做

unsigned int nmbintree_size(struct nmbintree_node* node) { 
    if (node==NULL) { 
    return(0); 
    } 
    return(nmbintree_size(node->left) + nmbintree_size(node->right) + 1); 
} 

2）前序/序/後序遍歷方式（使用堆棧/隊列）+計算節點。

您認爲哪種方法更能「防止內存故障」/性能？

任何其他建議/提示？

備註：我可能會在將來爲我的小項目使用此實現。所以我不想意外失敗:)。

Answer 1

只需使用遞歸函數。用這種方式實現起來很簡單，並且不需要使其更加完整。

如果你這樣做「手動」，你基本上最終會實現同樣的事情，只是你不會使用系統調用棧作爲臨時變量，而是使用自己的棧。通常這不會有超過更復雜代碼的優勢。

如果您後來發現在您的程序中花費大量時間來計算樹的大小（可能不會發生這種情況），您仍然可以開始分析事情並嘗試手動實現的執行方式。但是，如果在提取過程中已經跟蹤了大小的變化，那麼可能會更好地進行算法改進。

Answer 2

如果您的「非常簡單」的二叉樹不平衡，那麼遞歸選項是可怕的，因爲不受限制的遞歸深度。迭代遍歷有相同的時間問題，但至少堆棧/隊列在你的控制之下，所以你不需要崩潰。事實上，在每個節點和獨佔訪問中使用標誌和額外的指針，您可以在沒有任何堆棧/隊列的情況下迭代您的樹。

另一種選擇是每個節點在其下面存儲子樹的大小。這意味着無論何時添加或刪除某些內容，都必須一直跟蹤更新所有大小的根。所以再次如果樹不平衡這是一個沉重的操作。

如果樹是平衡的，那麼它不是很深。所有的選項都是無故障的，性能是通過測量來估計的:-)但是根據你的樹節點結構，它不是平衡的，或者你正在玩指向最低有效位標誌的愚蠢遊戲......

對此可能沒有多少意思。對於二叉樹的許多實際應用（特別是如果它是一個二進制搜索樹），你會早日意識到，你希望它是平衡的。因此，當您達到該點時節省您的能量:-)

Answer 3

這棵樹有多大，您需要多長時間知道一次它的大小？據說，遞歸函數是最簡單的，也可能是最快的。

如果樹像10^3個節點，並且每秒更改10^3次，那麼您可以保留一個外部計數，當您刪除一個節點時遞減，當您添加一個節點時遞增。除此之外，簡單是最好的。個人而言，我不喜歡任何需要使用計數和「上」指針等額外信息來裝飾節點的解決方案（儘管有時候我會這樣做）。任何額外的數據都會使結構非規範化，因此改變它會涉及額外的代碼和額外的錯誤機會。