樹遍歷如何工作？

這是序遍歷的代碼 -樹遍歷如何工作？

void preOrder(node *root) 
{  
    if(root!=NULL) 
    { 
     cout<<root->data<<" "; 
     preOrder(root->left); 
     preOrder(root->right); 
    }   
}

當我們已經達到左邊的最後一個節點，它是如何去正確的節點？我的意思是左右節點之間沒有鏈接，雖然它們都有相同的父節點，但是在到達最後一個節點之後，它如何回到父節點？

來源

2017-06-26 Nick Hill

您應該搜索遞歸函數如何工作。這會給你一個線索（提示：堆棧相關）。 – Javia1492

有關遞歸的定義，請參閱遞歸。 –

@ Yan.F那是錯的。每次迭代都不打印每個子節點。它是遞歸調用的，打印左節點直到空節點，然後右子節點直到空。 – Javia1492

是的！同一節點的兩個孩子之間不存在direct鏈接。

現在用上面的遞歸代碼來幫助你，看看從geeksforgeeks獲得的下面的圖像。

直接跳轉到最左邊的節點，因爲你知道你是怎麼到達了那裏，現在讓我們來了解它是如何移動回其父等等等等。

當您將出現以下行時，您肯定會因爲if(root!=NULL)作爲4的左孩子和右孩子爲空，仍然沒有得到它嗎？別擔心，請看下面的解釋。現在

，你在這是在這種情況下4最左邊的節點，負責達到這個節點的路線是：

preOrder(root->left)和你沒有見過，這是什麼線下至今

即你從未見過以下行：

preOrder(root->right);。

4的左邊子女是null，因爲遞歸條件破壞了，最後你看到了preOrder(root->right);。這不是某種巫術，這就是遞歸。現在，當你看到4的正確孩子，這又是null。

那麼，現在根的值是多少？

根的值是2因爲2是帶你到4放在第一位唯一的價值。遞歸就像級別內的級別，當最後一級關閉時，呼叫回到它上面的級別2爲4。最後，下面的行會把它帶到右邊的孩子的2這是5。

preOrder(root->right);

拿走：

1）當你看到cout<<root->data<<" ";打印當前根的價值。

2）只要你看到preOrder(root->left);你移動到根的左邊的孩子。

3）每當你看到preOrder(root->right);你移動到根的右邊的孩子。

4）如果root的值是NULL你什麼都不做，你將被帶回到呼叫線路，該線路將是preOrder(root->left);或preOrder(root->right);。

如果我們按照我上面說你猜對給定二叉樹的前序遍歷，這將是：

1 2 4 5 3

現在，我建議你閱讀和學習遞歸，然後接近上方問題再次。

來源

2017-06-27 08:35:56

謝謝Shivam。我昨天看了一些關於遞歸的視頻，現在我知道它是如何工作的。你能告訴區別'if（root！= NULL）'和'if（root == NULL）return;'爲上面的代碼嗎？ –

如果（root！= NULL）是遞歸中斷條件。與for循環類似，您也有遞歸中的檢查條件。當你訪問** 4 **的左邊孩子時，它是* NULL *，並且它必須在那一刻中斷。 –

您正在遞歸地調用該函數。每次調用preOrder都會在線程的執行堆棧上創建我們稱之爲框架的東西。這些幀跟隨樹中的每個路徑。當你從函數中return，它的調用幀被從堆棧中移除（或「彈出」）並且控制返回到前一幀。

這就是爲什麼當你到達葉子時，你「回溯」到父親然後到兄弟子樹（通過第二次調用preOrder）。你所說的「鏈接」實際上是在執行堆棧上創建的。

來源

2017-06-26 18:39:45 vencik

樹遍歷如何工作？

回答

相關問題