二叉樹中的遞歸函數解釋

我正在瀏覽二叉樹教程。
而我稍微卡住使用遞歸函數。說例如我需要計算樹中的節點數二叉樹中的遞歸函數解釋

int countNodes(TreeNode *root)  
{ 
     // Count the nodes in the binary tree to which 
     // root points, and return the answer. 
    if (root == NULL) 
     return 0; // The tree is empty. It contains no nodes. 
    else 
    { 
     int count = 1; // Start by counting the root. 
     count += countNodes(root->left); // Add the number of nodes 
             //  in the left subtree. 
     count += countNodes(root->right); // Add the number of nodes 
             // in the right subtree. 
     return count; // Return the total. 
    } 
} // end countNodes()

現在我的疑問是 - >它將如何計算根 - >左 - >左邊的權利？或root-> right-> left-> left？由於

來源

2011-10-23 samprat

另請參見[樹結構和計算機程序的解釋]遞歸（http://mitpress.mit.edu/sicp/full-text/book/book-ZH-11.html#%_sec_1.2.2） – outis

有了遞歸函數，你應該遞歸地思考！以下是我會覺得這個功能：

我開始編寫函數的簽名，這是
```
int countNodes(TreeNode *root) 
```
因此，首先，是不是遞歸的情況下。例如，如果給定的樹是NULL，那麼沒有節點，所以我返回0.
然後，我觀察到我的樹中的節點數是左子樹的節點數加上右子樹的節點數加1（根節點）。因此，我基本上調用了左右節點的函數，並添加了加1的值。
- 請注意，我認爲該功能已正常工作！

爲什麼我這樣做？簡單來說，該功能應該適用於任何二叉樹？那麼，根節點的左子樹實際上就是二叉樹！正確的子樹也是一棵二叉樹。所以，我可以放心地假設用同樣的函數可以計算這些樹的節點。一旦我擁有了它們，我只需加左+右+ 1即可獲得我的結果。

遞歸函數是如何工作的？你可以使用筆和紙遵循的算法，但總之它是這樣的：

比方說，你調用函數與此樹：

a 
/\ 
b c 
/\ 
    d e

你看，根本不爲空，所以你叫左子樹的功能：

和後來的右子樹

c 
/\ 
d e

雖然在調用正確的子樹之前，需要評估左側的子樹。

那麼，你是在功能與輸入的電話：

你看這根不爲空，所以你調用該函數的左子樹：

NULL

返回0，而右子樹：

NULL

也返回0。您的計算節點的數量樹，它是0 + 0 + 1 = 1

現在，你的原樹的左子樹這是

拿到1和調用該函數用於

c 
/\ 
d e

在這裏，你再次調用該函數的左子樹

這類似於情況3210返回1，然後右子樹

也返回1，你評價在樹節點的數量爲1 + 1 + 1 = 3

現在，你的回報首先調用函數，然後評估樹中節點的數量爲1 + 3 + 1 = 5.

因此，您可以看到，對於每個左側和右側，您再次調用該函數，並且如果他們有左邊或右邊的孩子，這個函數會被一次又一次地調用，並且每次它在樹中都變得更深。因此，root->left->left或root->right->left->left不會被直接評估，而是會在後續調用之後進行評估。

來源

2011-10-23 00:44:56 Shahbaz

那太好評論了。我想我現在知道編碼在做什麼。我會再次查看代碼，如果被卡住了，我會再次ping你們，但atm似乎我已經理解了你的解釋 – samprat

@to所有人然後在下面的函數void printTree（struct node * node）{if（node == NULL ）返回; printTree（node-> left）; printf（「％d」，node-> data）; printTree（node-> right）; }在這個函數中，然後當它在b後遇到NUll時它會接受節點== NULL並因此返回（從函數退出），因此下面的代碼像printf將不會執行我對嗎？ – samprat

@samprat，正好。當你從函數返回時，你只需返回並且不要執行任何後續操作。 – Shahbaz

http://www.jargon.net/jargonfile/r/recursion.html

UPDATE：的一點是，兩者的數據結構和程序是遞歸的。

對於數據結構這意味着：子樹也是一棵樹。
因爲它意味着代碼：計數樹：=計數子樹（再加一）

來源

2011-10-23 00:36:33 wildplasser

好評... – FailedDev

應該真的有評論... – sarnold

說你叫countNodes(myTree);。假設myTree不爲空，countNodes將最終執行count += countNodes(root->left);，其中root是myTree。它會重新輸入您的countNodes函數，並且整個樹的根源爲root->left（即myTree->left）。然後邏輯重演;如果沒有root->left，則該函數返回0.否則，它最終將再次調用count += countNodes(root->left);，但這次的root實際上是myTree->left。這樣它會計數myTree->left->left。之後它會對正確的節點做同樣的事情。

來源

2011-10-23 00:36:56

但是根據我的理解，代碼最終會碰到root == NULL的情況，根據你的例子說它發生了myTree-> left-> left，然後它會返回0，所以當它有機會返回計數？ – samprat

如果我有12345的inorder值，那麼root == 4，所以它會去左邊，這是root-> left == 2，它不是null，所以它會去root-> left-> left，w等於1之後，沒有葉子，所以函數countnodes（root-> left-> left-> left）將變爲null並返回0？ – samprat

@samprat瞭解遞歸的重要一點是，有多個'countNodes'副本一次執行，每個都有自己的'count'值。當'root == NULL'時，它將返回0給調用函數。除非你在樹的頂部，否則這將是另一個'countNodes'框架爲由（root）代表的（子）樹的父節點執行，其中0將被添加到'count'的運行值中，幀。當該幀返回時，返回的值將被添加到對應於從根節點開始的兩個級別的另一個「count」中，等等。 –

每個子樹都有自己的根，就像實際的樹有一個根一樣。計數與每個子樹的計數相同。所以你只要繼續下去，直到你到達葉節點並停止本地遞歸，返回並加入節點。

來源

2011-10-23 00:40:00

這就是遞歸算法的美妙之處。該函數是在當前節點及其子節點上定義的。你只需要說服自己，只要對左右兒童的遞歸調用是正確的，那麼當前的調用就是正確的。完全相同的推理適用於孩子和他們的孩子，等等......這一切都會發揮作用。

來源

2011-10-23 00:41:04

它將以root-> left - >（subnode-> left）等開始，直到該分支返回0如果它不是實際的節點（樹中的葉）;

然後最深的節點將檢查root-> right並重復相同的過程。嘗試用小喬木想象這一點：

enter image description here

因此，在這種情況下，你的函數會去A-> D-> B，則正確的節點都將返回0，你會得到一個最後的+1你的C節點。

來源

2011-10-23 00:42:08 FailedDev

這基本上是遞歸的做的，它的每次加1 countNodes叫，因爲它得到一個子節點（），並終止當它試圖去葉節點的下一個孩子（因爲葉沒有孩子）。每個節點遞歸調用countNodes爲它的每個左右兒童和計數緩慢增加和泡沫到頂部。

嘗試，看看這樣說，其中1爲不存在的節點每個節點和0被添加在遞歸停止：

的1，每個加起來，與節點的父（遞歸的每個級別的調用函數）添加1 + left_size + right_size並返回結果。因此，在每一個階段返回的值是：

我不能肯定，使得它更清楚，但我希望它沒有。

來源

2011-10-23 00:43:56 AusCBloke

你寫的算法實現是詳盡的。它訪問整棵樹。

如果樹爲空，則count爲零。如果沒有，我們得到左邊的節點，我們稱它爲L，然後給我們的計數加1。

由於證明樹的子樹本身就是一棵樹，所以我們再次對以L爲根的樹執行相同的算法。

我們現在將它作爲具有根權限節點的樹作爲根。

現在...這確實有效。

樹的子樹是樹，也是空的或單個節點的樹。你應該看看樹的定義。

你可以使用Mathematical Induction來證明它，並用歸納推理的方式來描述你的問題。遞歸算法通常使用一種非常類似於歸納推理的結構。

來源

2011-10-23 00:44:48

訣竅遞歸函數的是，有一個基礎案例和感應步驟，就像mathematical induction。

基本情況是您的遞歸算法如何知道停止。在這種情況下，它是if (root == NULL) - 此節點不代表樹。該行在二叉樹的每個節點上執行，即使它在當時調用每個節點。樹的所有節點都是錯誤的，但是當您開始在葉節點的子節點上調用遞歸例程 - 全部爲NULL - 則它將返回0作爲節點數。

歸納步是從一個國家解決您的遞歸算法移動到下一個未解決的狀態由如何轉換尚未解決的問題轉化爲（一個或多個）已經解決的問題。您的算法需要計算樹中的節點數量;您需要1爲當前節點，然後您有兩個更簡單的問題 - 左側樹中的節點數和右側樹上的節點數。獲取這兩者，將它們加在一起，爲當前節點添加1，並將其作爲這個樹中的節點計數返回。

這個概念真的是many algorithms in computer science的基礎，所以它是值得研究，直到你完全理解它。另見quicksort,Fibonocci sequence。

來源

2011-10-23 00:45:24 sarnold

繪製整個樹，然後爲所有葉子節點分配1（葉子節點在N層）。之後，您應該能夠通過求和來計算由較高級別（N-1）上的每個節點生成的節點數目：如果節點有兩個孩子，則爲1 + 1，如果節點只有一個孩子，則爲1。因此，對於N-1級別的每個節點，分配值1 +總和（左，右）。在此之後，您應該能夠計算整個樹的節點數量。你發佈的遞歸，就是這麼做的。

來源

2011-10-23 00:56:52

認爲該程序首先在最深的分支。然後它向後返回計數到其前一個成員。

A 
/\ 
    B C 
/\ \ 
D E F

因此，首先在程序運行，直到

count += countNodes(root->left);

它暫停什麼它迄今（aparently沒什麼特別的）來完成，並進入B.同樣的情況存在，並且去D.在d它一樣。不過在這裏我們有一個特例。該方案認爲在開始在行

if (root == NULL)

的不存在左子d的確實NULL。因此你回到0. 然後我們回到我們上次停頓的地方，我們繼續這樣。上次我們在B點，所以我們繼續以往的線

count += countNodes(root->left);

和運行下一行

count += countNodes(root->right);

這下去，直到你回到A.但在A點，我們再次剛剛暫停在搜索A的左邊休假之後，我們繼續正確的休假。一旦我們完成了通過whola一個分支，我們回到A.

此時去我們沒有任何未完成的事業離開了，所以我們只是回到我們通過整個這個過程中收集的計數（暫停）。

來源

2011-10-23 01:01:48 Pithikos

二叉樹中的遞歸函數解釋

回答

相關問題