該函數如何計算樹中節點的數量？

計算樹中節點數量的函數。該函數如何計算樹中節點的數量？

int count(node *t) 
{  
    int i; 
    if (t == NULL)   
     return(0); 
    i = 1 + count(t->left) + count(t->right); // recursion occurs address of left node is passed and 
    return(i);        // continue to pass until whole left node 
}            // is traversed and the value of t is 
               // NULL and 0 is returned same for right node counting 
               // i = 1 + 0 + 0 = 1

節點數如何計算？

來源

2011-05-05 srbh

左節點是一個子樹。右節點也是一個子樹。函數調用自己，子樹作爲參數，計數遞增。現在，當計數器到達葉子時，它沒有任何孩子，所以它返回0.意義'葉子樹計數'。現在它達到了一級，結果是'1 +左葉數+右葉數'= 3'。同樣的，它還有一個更高的層次並且可以得到總數。 **假設所有節點都有離開葉子的左右兒童。那麼，概念不會改變** – Mayank 2011-05-05 10:17:38

這是計數樹節點的遞歸實現。它被稱爲根節點，並返回「左子樹中的一個正數節點加右子樹中的節點數」，這是遞歸地完成，直到它到達葉節點。

來源

2011-05-05 10:11:57 sharptooth

我知道的是遞歸遍歷左子樹，直到找到最後一個節點，現在t的值爲NULL，並且在count（t-> left）時返回的值對於右子樹並返回0來計數（t->右）。現在增加i = 1 + 0 + 0 = 1;那麼它如何計算左右節點的總數 – srbh 2011-05-05 10:26:00

@srbh：該鍵一旦遞歸調用開始，則前一個調用將暫停「暫停」，並等待遞歸調用結束，然後使用其結果。所以調用樹首先下到葉節點，然後調用以FIFO順序開始返回並且總結來自子樹的節點數量。 – sharptooth 2011-05-05 11:06:44

這意味着爲遞歸調用維護堆棧並繼續推送每個節點的地址，直到找到空節點。然後進入count（t-> right）找到正確的節點，直到找到NULL節點。節點的先前地址現在返回到它的父節點，再次計算左右節點，依此類推。請糾正我錯在哪裏。 – srbh 2011-05-05 11:26:42

總數包括當前/根節點加上左分支上的計數加上右分支上的計數。您的哨兵是NULL，這意味着您已經到達您當前正在計數的任何分支的葉節點。然後你放鬆回來。遞歸:)

來源

2011-05-05 10:15:23 dubnde

首先，你自己試過了嗎？

基本上，它爲每個非零節點加1。大概是這樣的：1 + number_of_nodes_to_the_left + number_of_nodes_to_the_right。這擴展到：1+(1+number_of_nodes_to_the_left_in_left+number_of_nodes_to_the_right_in_left) + (1+number_of_nodes_to_the_left_in_right + number_of_nodes_to_the_right_in_right)。繼續擴展，您會看到樹中每個非空節點基本上都是1 + 1 + 1 +....。

編輯：爲了說明這一點，不妨考慮下面的樹：

 Node0 
     | 
(left) | (right) 
Node1 _|_ Node2 
      | 
    (left) | (right) 
    Node3 _|_ Node4

當你這樣做int node_count = count(Node0)，因爲節點0不爲空，它關係到return語句是： return 1 + count(left) + count(right)。您需要了解一個基本的事情，即您的遞歸函數中的某個操作只發生在其他操作之後。換句話說，直到操作count(left)完成後纔會發生操作count(right)。現在看看你在那裏的return語句，並根據上面的樹翻譯它。這將是1+count(Node1)+count(Node2)。所以count(Node2)在count(Node1)完成之前沒有得到計算。因此，對於count(Node1)，count函數將以Node1作爲參數被調用（再次）。因此，現在讓我們忘掉半計算表達式1+count(Node1)+count(Node2)（我們稍後再回來）。

現在對於count(Node1)，Node1不是NULL，因此進入return語句。這將（再次）是1+count(left)+count(right)。但是等一下，Node1沒有左右節點。因此，當count(left)被調用的參數爲NULL時，它將返回0，並且count(right)也會發生同樣的情況。所以count(Node1)的表達式變成1 + 0 + 0。沒有更多的計數函數被調用Node1，因此它返回到它的原始調用者，這是返回語句count(Node0)。

由於我們有count(Node1)想通了，我們用count(Node0)的返回語句替換它。現在變成1 + (1 + 0 + 0) + count(Node2)。

現在我打算讓這個更快一點。由於Node2有兩個子節點，Node2的return語句將爲1 + count(Node3) + count(Node4)。就像Node1,count(Node3)和count(Node4)將分別返回1 + 0 + 0，將count(Node2)的返回語句變爲1 + (1 + 0 + 0) + (1 + 0 + 0)。

現在count(Node2)已完全計算，讓我們迴歸到count(Node2)原始調用者，這是1 + (1 + 0 + 0) + count(Node2)。替換我們從count(Node2)那裏得到的，我們得到1 + (1+0+0) + (1 + (1+0+0) + (1+0+0))。把它加起來，我們得到5的值。 將此值返回到稱爲count(Node0)的任何函數，如語句int node_count = count(Node0)和node_count將具有值5。

來源

2011-05-05 10:16:54

我認爲我的遞歸概念並不好。但是在這個遞歸調用計數中（t-> left）繼續調用自身，並且在左節點的地址被傳遞的情況下僅繼續左節點，並且最終找到空值，它返回零來進行計數（t-> left）。「有一個NULL值，它如何返回來計算正確的節點。請回復。 – srbh 2011-05-05 10:56:55

我已經添加了一些細節。 – 2011-05-07 20:26:51

考慮這些樹：

樹沒有節點（即一個NULL指針） - 返回0

與一個節點，根樹。這將調用：

i=1+count(t->left)+count(t->right);

與左，右NULL，因此將返回1 + 0 + 0

一棵樹，根和一個右葉

i=1+count(t->left)+count(t->right);

將返回1 （根據上述規則）的樹根爲0，樹根爲1的根（按上述規則），即1 + 0 + 1

依此類推。

來源

2011-05-05 10:17:20

To understand recursion, you must first understand recursion.

來源

2011-05-05 10:22:29 pmg

+1這真是太棒了 – dubnde 2011-05-05 14:10:57

該函數如何計算樹中節點的數量？

回答

相關問題