免費的樹形結構與非遞歸函數

Question

假設我有一個結構，看起來像這樣：

struct tree_suspects { 
    char **description; 
    struct tree_suspects *right_description; 
    struct tree_suspects *wrong_description; 
} 

..我想free每個節點用malloc他們每個人都分配了。

該樹應該能夠容納數百個節點而沒有問題。因此，使用遞歸函數對於堆棧幀來說效率會非常低，那麼是否有任何形式的循環或某種東西可以讓我將數組中的所有節點分組？遞歸真的是唯一的方法嗎？

Answer 1

不是。您可以使用任何列表，堆棧或隊列結構，但除非您知道元素的總數（在這種情況下，您可以預先分配列表並使用類似於環形緩衝區的內容），否則不會提供顯着的優勢。

你確定遞歸是一個問題嗎？使用通常的遞歸，幾百個節點對我來說聽起來完全沒問題。你在做什麼建築？

如果您擔心內存訪問，您應該確保將這些節點及其數據放入類似的內存位置。由於您使用的是二叉樹，因此您至少可以將樹本身放在一個數組中（如果樹中有n個節點，則該數組的開銷最多爲n-1）。我認爲不需要優化字符串，但是如果您也想這樣做，那麼可以使用例如子索引字符數組。

關於樹結構的存儲佈局，平衡樹很容易存儲（https://en.wikipedia.org/wiki/Binary_tree#Arrays）。在這種情況下，應該避免不平衡的樹木，我建議像紅黑樹這樣的東西不太難實施。

Answer 2

使用遞歸函數會大大低效堆放數百個節點的

在一個平衡的樹是不是一個大問題：一個平衡樹級別的十幾個會很容易地適應了一千多，所以遞歸在這種情況下不會有問題。

如果樹不平衡，您可以構建一個非遞歸函數來處理它，方法是保留要釋放的顯式堆棧節點。將根推入堆棧，然後創建一個循環，將下一個元素從堆棧中移出，將其兩個子元素推入堆棧，然後釋放節點本身。該算法將遍歷整個樹，並在堆棧爲空時停止。