二叉树中的递归函数解释
我正在阅读二叉树教程。
而且我在使用递归函数方面略有困难。 比方说，我需要计算树中的节点数
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 ?? 谢谢
使用递归函数，你应该递归思考！ 这是我如何看待这个function：
-
我开始编写函数的签名，即
int countNodes( TreeNode *root ) -
首先，这些案例不是递归的。 例如，如果给定的树是
NULL，那么没有节点，所以我返回0。 - 然后，我观察到我树中的节点数是左子树的节点数加上右子树的节点数加1（根节点）。 因此，我基本上调用左右节点的函数，并添加值1。
- 请注意，我认为该function已正常工作！
我为什么这样做？ 很简单，该函数应该适用于任何二叉树吗？ 那么，根节点的左子树实际上是二叉树！ 右子树也是二叉树。 因此，我可以安全地假设使用相同的countNodes函数，我可以计算这些树的节点。 一旦我拥有它们，我只需添加左+右+ 1即可得到我的结果。
递归函数如何真正起作用？ 您可以使用笔和纸来遵循算法，但简而言之，它是这样的：
假设您使用此树调用该函数：
a / \ bc / \ de
您看到root不为null，因此您调用左子树的函数：
b
以及右边的子树
c / \ de
在调用右子树之前，需要评估左子树。
所以，你正在使用输入调用函数：
b
您看到根不是null，因此您调用左子树的函数：
NULL
返回0，右侧子树：
NULL
也会返回0.您计算树的节点数，它是0 + 0 + 1 = 1。
现在，你得到原始树的左子树的1
b
并调用该函数
c / \ de
在这里，您再次为左子树调用该函数
d
类似于b的情况返回1，然后是右子树
e
它也返回1并且您将树中的节点数评估为1 + 1 + 1 = 3。
现在，返回函数的第一次调用，并将树中的节点数评估为1 + 3 + 1 = 5。
因此，您可以看到，对于每个左右，您再次调用该函数，如果它们有左或右子节点，则该函数会一次又一次地被调用，并且每次在树中更深入时。 因此， root->left->left或root->right->left->left不会直接评估，而是在后续调用之后评估。
这基本上就是递归的作用，每当countNodes被调用到子节点（ int count = 1; ）时它会加int count = 1;并在它尝试转到叶节点的下一个子节点时终止（因为叶子没有儿童）。 每个节点以递归方式为每个子节点的左右子节点调用countNodes ，并且计数缓慢增加并冒泡到顶部。
尝试以这种方式查看，其中为每个节点添加1，为递归停止的不存在节点添加0：
1 / \ 1 1 / \ / \ 1 0 0 0 / \ 0 0
每个1加起来，节点的父（每个递归级别的调用函数）加上1 + left_size + right_size并返回该结果。 因此，每个阶段返回的值将是：
4 / \ 2 1 / \ / \ 1 0 0 0 / \ 0 0
我不确定是否更清楚，但我希望它能做到。
假设您调用countNodes(myTree); 。 假设myTree不为null， 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 。 后来它对正确的节点做了同样的事情。
这就是递归算法的美妙之处。 该函数是在当前节点及其子节点上定义的。 只要对左右子项的递归调用是正确的，您只需要说服自己当前的调用是正确的。 完全相同的推理适用于孩子和他们的孩子，等等…这一切都只是工作。
它将以root-> left – >（subnode-> left）等开始，直到该分支返回0，例如，如果它不是实际节点（树中的叶子）;
然后最深的节点将检查root-> right并重复相同的过程。 尝试用一棵小树来形象化：
因此，在这种情况下，您的函数将转到A-> D-> B，然后右侧节点将全部返回0，您将从C节点获得最后+1。
您编写的算法实现是详尽无遗的。 它访问整棵树。
如果树为空，则计数为零。 如果没有，我们得到左边的节点，我们称之为L，我们在计数中加1。
由于已经certificate树的子树本身就是树，因此我们在具有L作为根的树上再次执行相同的算法。
我们现在为具有根权限节点的树执行此操作。
现在……这确实有效。
树的子树是树，也用于空节点或单节点。 你应该看一下树的定义。
您可以使用数学归纳来certificate它，并根据归纳推理来表达您的问题。 递归算法通常使用与归纳推理非常相似的结构。
递归函数的技巧是有一个基本情况和一个归纳步骤 ，就像数学归纳一样 。
基本情况是您的递归算法如何知道停止 。 在这种情况下， if (root == NULL) – 此节点不表示树。 此行在二叉树中的每个节点上执行，即使它当时调用每个节点。 对于树的所有节点都是错误的，但是当你开始在叶子节点的子节点上调用递归例程时 – 它们都是NULL – 那么它将返回0作为节点的计数。
归纳步骤是通过将未解决的问题转换为（一个或多个）已解决的问题， 将递归算法从一个已解决状态移动到下一个未解决状态。 您的算法需要计算树中的节点数量; 当前节点需要1 ，然后你有两个更简单的问题 – 左边树中的节点数，右边树上的节点数。 获取这两者，将它们添加到一起，为当前节点添加1 ，并将其作为此树中的节点数返回。
这个概念确实是计算机科学中许多算法的基础，所以在你完全理解它之前，它是值得研究的。 另见quicksort ， Fibonocci序列 。
认为该计划首先在最深的分支机构。 然后它向后返回计数到其前一个成员。
A / \ BC / \ \ DEF
所以首先程序运行直到
count += countNodes(root->left);
它暂停了到目前为止所做的事情（显然没什么特别的），然后进入B.同样的情况发生在那里，然后进入D.在D，它也是如此。 但是在这里我们有一个特例 。 该计划从一开始就在线上看到
if ( root == NULL )
D的不存在的左子节点确实是NULL 。 因此你回到0.然后我们回到上次暂停的地方，我们继续这样做。 上次我们在B，所以我们继续走线
count += countNodes(root->left);
然后运行下一行
count += countNodes(root->right);
这种情况一直持续到你回到A.但是在A点再次我们在搜索A的左边离开后暂停了。因此我们继续正确的离开。 一旦我们完成了通过whola那个分支我们回到A.
此时我们还没有任何未完成的业务（暂停），所以我们只返回我们在整个过程中收集的计数。
每个子树都有自己的根，就像实际的树有根一样。 计数与每个子树的计数相同。 因此，您只需继续操作，直到到达叶节点并停止本地递归，然后返回并添加节点。
绘制整个树，然后为所有叶节点分配1（叶节点在N级）。 之后，您应该能够通过求和来计算更高级别（N-1）上每个节点生成的节点数：如果节点有两个子节点则为1 + 1;如果节点只有一个子节点，则为1。 因此，对于级别N-1上的每个节点，分配值1 + sum（左，右）。 在此之后，您应该能够计算整个树的节点数。 您发布的递归，就是这样做的。
http://www.jargon.net/jargonfile/r/recursion.html
更新：关键是数据结构和程序都是递归的。
- 对于数据结构，这意味着：子树也是树。
- 对于代码，它意味着：计算树：=计算子树（并添加一个）