使用递归的二叉树的大小

Question

谁能准确解释一下这个递归是如何工作的？我们计算了左子树和右子树的大小，但是左子树右侧（即右子树）的节点呢？还有，为什么每次调用都要加1？

int size(struct node* node) // We pass root 
{
   if (node==NULL) 
      return 0;
   else    
      return(size(node->left) + 1 + size(node->right));  
}

Answer 1

这就是递归的工作原理。

int size(struct node* node) // We pass root 
{
if (node==NULL) 
return 0; //if the current node is null return a 0 so no add 1 is done
else    
return(size(node->left) + 1 + size(node->right));  
}

让我们拆分 return 语句

return

size(node->left) 递归调用当前节点的左节点

当前节点+1

size(node->right) 递归调用当前节点的右节点

当递归完成时，它将 return 整棵树的当前大小

如果我们从树的头部开始，它将递归调用左子树，直到它遇到空值，returns 0 对于那个节点，所以没有为它做加 1，然后返回up 1 level 调用最后一个节点的右子树 not null 并继续直到整个树完成，为每个非 null 节点加 1。

示例

        5

    3       8

1      4 7     9

是树

递归从 5

开始

它有左右子树

左边叫前3 三个有左右子树先离开所以它变为 1。 1 没有子树但 1 不为空所以它调用左子树 returns 0

0 + 1 + 0 是第 1 个节点 return 即 1.

然后回到 3

3 有一个右子树，所以它调用

4 没有子树，所以它的 return 将是 0 + 1 + 0

现在回到3 它的 return 将是 1 + 1 + 1

现在回到 5 所以来自 3 节点的 return 将是 3

所以现在在递归中它将是 3 + 1 + size->right

它将递归 return 右子树，因此 return 将是

3 + 1 + 3 这是 7 个节点不为空

Answer 2

每棵二叉树都有一个根。根可以为空，在这种情况下，这棵树为空且大小为 0。否则，至少有一个顶点（根）加上从根垂下的任何子树中包含的许多顶点。这导致计算大小的两种情况：

如果根顶点为空，则这棵树的大小为零，故事结束。
如果它不为空，则根顶点是两个子树（左子树和右子树）的父节点。不管子树是否为空，树的总大小将为[the size of the left subtree] + [the size of the right subtree] + 1 (for the root vertex itself).

此时您需要认识到子树本身就是一棵树。您还需要采用 "recursive leap of faith" size() 是一个 returns 树大小的函数，而不用担心它如何设法这样做。如果你能接受这个事实，那么上面概述的第二种情况可以通过在左子树上调用 size() 函数，在右子树上调用它，对结果求和，然后添加1 代表当前（子）树的根！对于左侧和右侧，如果没有子树，则返回的贡献将为零。否则，请相信该函数会交还该子树的大小，并使用结果计算当前（子）树的大小，而您又将其交还给通过 return 语句调用您的人。

使用递归的二叉树的大小

size of a binary tree using recursion

recursion

binary-tree