堆棧是如何組織的？ ：刪除一個二叉樹

Question

我有這段代碼從內存中刪除二叉樹，但我不知道如何遞歸調用destroy(<#node* tree#>)遞歸調用時如何遞歸。我知道當你到達分支的末尾時，遞歸結束，並且結束那個調用並開始在遞歸中上升，但是如果遞歸函數調用保持在它停止的地方，則調用destroy(tree->right)等待執行，而destroy(tree->left)完成？

struct node{ 
    int value; 
    node* left; 
    node* right; 
}; 

void destroy(node* tree){ 
    if(tree != NULL){ 
     destroy(tree->left); 
     destroy(tree->right); 
     delete tree; 
    } 
} 

Answer 1

你必須抓住一張紙形象化，但是是的，他們是連續的，沒有在樹上兩個地在同一個節點或你就會有問題。

它會去像

destroy(root) 
>destroy(l) 
    >l 
     >l 
     (...) 
    >r 
    (...) 
>r 
    >l 
    (...) 
    >r 
    (...) 
>delete root 
>end 

所以你會開始推動地址在地址，直到最後到達分支的末端，那麼你彈出一次，不斷探索，直到下一個分支的末端和等等。最後，在最後的分支上，你將彈出所有的函數，直到你回到原來的那個，並刪除根節點。

Answer 2

destroy（樹 - >左）在銷燬之前完全執行（tree-> right）。

但是，請記住左樹有左側和右側。所以在這裏它會再次一路走到左邊的第一個路上，然後回到右邊的路上。右側可能包含最先處理的左側節點。

堆棧對此沒有什麼影響。無論你何時向樹中更深入一個控制桿（即調用左側或右側的銷燬），函數調用可能會將一些變量推送到堆棧 - 例如返回地址和當前節點指針。當到達葉子並且函數調用開始返回時，這些變量再次從堆棧中取出。

通常情況下，這應該不是問題，但如果您的樹有很多層次，則可能需要考慮堆棧使用情況。

如果假定一個空棧開始，並期待在第一次調用摧毀離開，你將有：

堆棧= |第一次離開|

現在這可能會導致另一個電話左：

stack = | first left |第二個離開|

甚至第三個電話到左：

堆棧= |第一次離開|第二個離開|第三個離開|

現在撥打第三個左側回覆：

stack = | first left |第二個離開|

但是這個權利將被稱爲：

stack = | first left |第二個離開|第一個權利|

這項權利可能對一個節點的左邊，這樣我們將得到：

堆棧= |第一次離開|第二個離開|第一個權利|首先離開|

這將繼續，直到所有節點返回 - 像這樣

stack = | first left |第二個離開|第一個權利|

stack = | first left |第二個離開|

stack = | first left |

堆棧=

，現在是時候做同樣的從頂部右側

堆棧= |第一權|

等等...

爲了在你的代碼的簡單例子，將最有可能導致一個4字節的返回地址推到堆棧樹中的每個級別。所以，即使在較深的樹級別下，堆棧使用率也會很低。