這個雙遞歸調用如何顯示數據C++

我不確定以下代碼如何顯示rChild和lChild中的數據。在它到達顯示代碼之前，該函數在傳遞參數ptr-rChild的情況下被調用。所以顯示代碼永遠不會有機會執行，因爲在顯示代碼之前總是有一個函數調用。此外，當函數被再次調用，但是這次參數是lChild時，當第一個函數調用參數rChild時，它如何在lChild中顯示數據。這個雙遞歸調用如何顯示數據C++

void CTree::DisplayTree(PersonRec * ptr) 
{ 
    if (ptr != NULL) 
    { 
     DisplayTree(ptr->rChild); 
     cout << "Name: " << ptr->name << "\t" << "Bribe Offered: " << ptr->bribe << endl; 
     DisplayTree(ptr->lChild); 
    } 

}

來源

2016-11-21 H. Lee

它總是先穿過左邊的小孩。當它離開左邊時，它將開始穿越右側。

這被稱爲「按順序」遞歸。

https://en.wikipedia.org/wiki/Tree_traversal

來源

2016-11-21 04:42:19

它首先遍歷'rChild'（這可能意味着正確） – asimes

是的，這是正確的。右孩子第一 –

採取樹下面作爲一個例子，其中Node0是傳遞給DisplayTree第一PersonRec*（右側是該節點訪問以供參考的順序）：

  Node0      1st 
     / \     / \ 
    Node2  Node1    5th  2nd 
    / |  | \   /|  | \ 
NULL NULL  NULL NULL 7th 6th  4th 3rd

第一個電話輸入if語句並通過Node1至DisplayTree（如rChild）
第二呼叫進入if語句，並傳遞NULL到DisplayTree（如rChild）
因爲參數是NULL並返回到第二呼叫（Node1）
第二呼叫的第三呼叫不進入if語句現在打印Node1，然後傳遞到NULLDisplayTree（如lChild）
第四打不進if語句，並返回到第二個呼叫（Node1）
第二呼叫已經完成，並返回到第一個呼叫（Node0）
第一呼叫現在打印Node0然後傳遞Node2到DisplayTree（如lChild）
第五呼叫進入if語句，並傳遞NULL到DisplayTree（如rChild）
第六打不進if語句，並返回到第五輪（Node2）
第五呼叫現在打印Node2然後通過NULL到DisplayTree（如lChild）
第七打不進if語句，並返回到第五輪（Node2）
第五調用完成並返回到第一個呼叫
的第一個電話已完成

編輯：用較小的示例解決您的評論。考慮一棵樹只有一個沒有孩子的節點，這次我們可以更多地關注代碼。樹是這樣的：

 Node0 
    / \ 
NULL  NULL

第一次你的代碼被調用時，Node0在傳遞if (ptr != NULL)是true，因此進入執行if語句。下一行DisplayTree(ptr->rChild);使用NULL調用該函數。在該呼叫期間，if (ptr != NULL)是false因此執行不會輸入if語句。結果，執行返回到先前的調用，並且下一行代碼是cout << "Name: " << ptr->name...，它打印Node0的信息，這就是爲什麼有輸出。該行完畢後，呼叫，DisplayTree(ptr->lChild);也因爲它通過NULL，然後所有的遞歸結束

來源

2016-11-21 04:45:46 asimes

這仍然是我很混淆 –

@ H.Lee，什麼部分是混亂？你能夠效仿這個例子嗎？ – asimes

那麼，當pyr = NULL時，函數如何繼續運行。這不會讓你擺脫if語句嗎？當發生這種情況時，如果另一個調用的函數已經具有不同的參數值，那麼程序如何能夠返回到先前的函數調用並打印該數據。 –

的「遞歸函數」的概念很簡單，但它可以是一個小在第一次遇到恐嚇束手無策。大約有這麼多的好資源和我個人都享有以下的人非常多：

http://www.cplusplus.com/articles/D2N36Up4/

http://www.cprogramming.com/tutorial/lesson16.html

正如你可能知道，函數調用被放置在堆棧存儲器中，因爲這個內存是有限的，一旦太多人被調用而沒有結束，程序就會崩潰。因此，遞歸定義的一個重要部分是停止條件，該條件指定何時以及在什麼情況下函數將停止調用自身並中斷遞歸循環。在你的代碼中，行if (ptr != NULL)是停止標準。因此，你的問題的答案

所以不會顯示代碼永遠不會得到執行的機會，因爲顯示代碼之前總是有一個函數調用。

是，當它到達樹在rChild和lChild是NULL的葉DisplayTree遞歸調用將結束。這就是當DisplayTree(ptr->rChild);將立即返回葉節點並且cout << "Name: " << ptr->name << "\t" << "Bribe Offered: " << ptr->bribe << endl;代碼行有機會執行和打印數據。當然，這一切都取決於你的樹是否定義良好。從你的代碼中，可以假定函數期望葉節點對於rChild和lChild具有NULL值。因此，如果按照本規範構建樹，就會滿足停止條件並顯示數據。在另一方面，如果樹構造不正確，程序將會崩潰，因爲堆棧溢出（見en.wikipedia.org/wiki/Stack_overflow）

來源

2016-11-21 06:40:04 MxNx

但是當父節點的左右子節點不爲null時怎麼辦？它不會打破if語句，那麼它將如何獲得顯示數據的機會 –

@ H.Lee這完全取決於您的樹是否定義良好。從你的代碼中，可以假定函數期望葉節點對於rChild和lChild具有NULL值。所以如果樹是按照這個規範構造的，它會顯示數據。另一方面，如果樹的構造不正確，程序將因堆棧溢出而崩潰（請參閱https://en.wikipedia.org/wiki/Stack_overflow） – MxNx

每當你看到一個遞歸函數調用，知道函數將回報在某些時候，下一個語句將被執行。但是如何？那麼，DisplayTree(ptr->rChild)將繼續調用它自己，並在收到空指針時停止。這就是爲什麼您的if (ptr != NULL)檢查如此重要 - 它可以防止無限遞歸，並且在邏輯上也不想取消引用空指針。

當接收到空指針的函數返回時，編譯器將調用堆棧關閉到發出調用的最後一幀。在那裏它將轉向下一個陳述。這將是它將打印樹中最右邊的節點的時間。然後它會以ptr->lChild遞歸調用它自己，它將在中找到最右邊的節點樹，並重新開始該過程。

這是一個inorder遍歷的例子。當我看到這樣的函數時，我喜歡對自己說「這個函數首先爲右子樹，當前節點和左子樹執行中間語句」，這使得它更容易理解。

來源

2016-11-21 07:13:55 0x499602D2

當您聲明它傳遞ptr lChild，然後搜索最右側該樹中的節點，只有當rChild爲NULL時纔會在lChild中打印數據？ –

@ H.Lee是的，只有當給定節點的右子樹爲空時，遞歸調用纔會返回，編譯器將彈出最後一個堆棧幀，並轉到前一個堆棧幀的下一個語句（即「cout」聲明）。然後它將轉到其左邊的子樹並重復該子樹的過程。 – 0x499602D2

@ H.Lee如果您繪製二叉樹的圖像，您可以使用手指，從根開始，每次函數調用一次向下移動樹中的每個節點。 'display（p-> right）'表示將你的手指移動到右邊的子樹，'display（p-> left）'表示移動到左邊的子樹。如果函數返回（因爲'ptr == NULL'），則轉到您來自的前一個節點並轉到下一個語句。一切完成後，你的手指應該回到根部。 – 0x499602D2

這個雙遞歸調用如何顯示數據C++

回答

相關問題