請問這個函數計算二叉樹的節點數

鑑於這個代碼塊：

int func_1(struct node* node) 
{ 
    if (node == NULL) 
     return 0; 
    else 
     return func_1(node->left) + 1 + func_1(node->right); 
}

而這個二叉搜索樹：

返回值是7

我知道遞歸，這裏有點簡單，我試圖跟進，我不明白它是如何返回7.我計算出它只是左，左，然後一次正確，就是這樣。這將返回3.即使它正確的3倍，根後，它仍然會返回6而不是7.

你能幫我一下嗎？

從語義上講，它需要左節點+ 1（當前節點）的數量+右節點的數量。

with func_1（x）我的意思是在該特定節點上調用該函數。

所以完整的計算是

該原理經常使用在遞歸：

2016-07-06 14:29:04

這是我的確切解釋！清楚並且重點。 – Module

這是完美的！ –

爲了清楚起見，我添加了一些關於遞歸的基本原理。 –

看看葉節點7

當func_1被稱爲與節點7的值，if語句將跳轉到其他部分，因爲指針指向此節點是有效的。

然後func_1將被調用兩次左邊的孩子和一次右邊的孩子。在這兩種情況下，函數都返回0，因爲左邊和右邊的孩子都是NULL。該函數將返回1：

return func_1(node->left) + 1 + func_1(node->right);

等同於：

return func_1(NULL) + 1 + func_1(NULL);

變爲：

return 0 + 1 + 0;

2016-07-06 14:24:44 2501

我明白了。謝謝2501！ –

看這個說法

return func_1(node->left) + 1 + func_1(node->right); 
          ^^^^^

如果一個節點不等於NULL它自己加上數字左右子樹中相對於該節點的節點。

所以你會得到一個結果，它等於不等於NULL的節點數。

2016-07-06 14:26:35

回答