二叉树中的递归功能说明 [英] Recursive functional explanation in binary tree

问题描述

我正在阅读二叉树的教程.
而且我在使用递归函数时有些卡住.例如说我需要不计算树中的节点数

I was going through the tutorial of binary tree .
And I am slightly stuck in use of recursive function . say for example I need to count no of nodes in a tree

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-> left-> left of right?或root-> right-> left-> left ?? 谢谢

Now my doubt is-> how would it count say root->left->left of right ? or root->right->left->left?? Thanks

推荐答案

使用递归函数，您应该进行递归思考！这是我对这个功能的看法:

With recursive functions, you should think recursively! Here's how I would think of this function:

• 我开始编写函数的签名，即

• I start writing the signature of the function, that is

int countNodes( TreeNode *root ) 

因此，首先是非递归的情况.例如，如果给定的树是NULL，则没有节点，因此我返回0.

So first, the cases that are not recursive. For example, if the given tree is NULL, then there are no nodes, so I return 0.

• 请注意，我假设该功能已正确运行！

我为什么要这样做?很简单，该功能应该可以在任何二叉树上运行，对吗?好吧，根节点的左子树实际上是一棵二叉树！右边的子树也是二叉树.因此，我可以放心地假设使用相同的countNodes函数，我可以计算那些树的节点.一旦有了它们，我只需添加left + right + 1即可得到结果.

Why did I do this? Simple, the function is supposed to work on any binary tree right? Well, the left sub-tree of the root node, is in fact a binary tree! The right sub-tree also is a binary tree. So, I can safely assume with the same countNodes functions I can count the nodes of those trees. Once I have them, I just add left+right+1 and I get my result.

递归函数如何真正起作用?您可以使用笔和纸来遵循该算法，但是总之，它是这样的:

How does the recursive function really work? You could use a pen and paper to follow the algorithm, but in short it is something like this:

假设您使用此树调用该函数:

Let's say you call the function with this tree:

  a
 / \
b   c
   / \
  d   e

您看到根不为空，因此您调用左侧子树的函数:

You see the root is not null, so you call the function for the left sub-tree:

b

以及随后的右子树

   c
  / \
 d   e

在调用右子树之前，需要先评估左子树.

Before calling the right sub-tree though, the left sub-tree needs to be evaluated.

因此，您正在通过输入调用函数:

So, you are in the call of the function with input:

b

您看到根不为null，因此您调用左侧子树的函数:

You see that the root is not null, so you call the function for the left sub-tree:

NULL

返回0，并返回正确的子树:

which returns 0, and the right sub-tree:

NULL

它也返回0.您计算树的节点数，它是0 + 0 + 1 = 1.

which also returns 0. You compute the number of nodes of the tree and it is 0+0+1 = 1.

现在，您为原始树的左子树得到了1，该子树是

Now, you got 1 for the left sub-tree of the original tree which was

b

该函数被调用

   c
  / \
 d   e

在这里，您再次调用左侧子树的函数

Here, you call the function again for the left sub-tree

d

类似于b的情况，返回1，然后是右边的子树

which similar to the case of b returns 1, and then the right sub-tree

e

也会返回1，您将树中的节点数评估为1 + 1 + 1 = 3.

which also returns 1 and you evaluate the number of nodes in the tree as 1+1+1 = 3.

现在，您返回该函数的第一个调用，并评估树中的节点数为1 + 3 + 1 = 5.

Now, you return the first call of the function and you evaluate the number of nodes in the tree as 1+3+1 = 5.

因此，如您所见，对于左右的每个子对象，您都需要再次调用该函数，并且如果它们有左子对象或右子对象，则函数会一次又一次地被调用，并且每次在树中更深时都会被调用.因此，root->left->left或root->right->left->left不会直接求值，而是在随后的调用之后求值.

So as you can see, for each left and right, you call the function again, and if they had left or right children, the function gets called again and again and each time it goes deeper in the tree. Therefore, root->left->left or root->right->left->left get evaluated not directly, but after subsequent calls.

这篇关于二叉树中的递归功能说明的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！