这个双递归调用如何显示数据C++

我不确定以下代码如何显示rChild和lChild中的数据。在它到达显示代码之前，该函数在传递参数ptr-rChild的情况下被调用。所以显示代码永远不会有机会执行，因为在显示代码之前总是有一个函数调用。此外，当函数被再次调用，但是这次参数是lChild时，当第一个函数调用参数rChild时，它如何在lChild中显示数据。这个双递归调用如何显示数据C++

void CTree::DisplayTree(PersonRec * ptr) 
{ 
    if (ptr != NULL) 
    { 
     DisplayTree(ptr->rChild); 
     cout << "Name: " << ptr->name << "\t" << "Bribe Offered: " << ptr->bribe << endl; 
     DisplayTree(ptr->lChild); 
    } 

}

来源

2016-11-21 H. Lee

它总是先穿过左边的小孩。当它离开左边时，它将开始穿越右侧。

这被称为“按顺序”递归。

https://en.wikipedia.org/wiki/Tree_traversal

来源

2016-11-21 04:42:19

它首先遍历'rChild'（这可能意味着正确） – asimes

是的，这是正确的。右孩子第一 –

采取树下面作为一个例子，其中Node0是传递给DisplayTree第一PersonRec*（右侧是该节点访问以供参考的顺序）：

  Node0      1st 
     / \     / \ 
    Node2  Node1    5th  2nd 
    / |  | \   /|  | \ 
NULL NULL  NULL NULL 7th 6th  4th 3rd

第一个电话输入if语句并通过Node1至DisplayTree（如rChild）
第二呼叫进入if语句，并传递NULL到DisplayTree（如rChild）
因为参数是NULL并返回到第二呼叫（Node1）
第二呼叫的第三呼叫不进入if语句现在打印Node1，然后传递到NULLDisplayTree（如lChild）
第四打不进if语句，并返回到第二个呼叫（Node1）
第二呼叫已经完成，并返回到第一个呼叫（Node0）
第一呼叫现在打印Node0然后传递Node2到DisplayTree（如lChild）
第五呼叫进入if语句，并传递NULL到DisplayTree（如rChild）
第六打不进if语句，并返回到第五轮（Node2）
第五呼叫现在打印Node2然后通过NULL到DisplayTree（如lChild）
第七打不进if语句，并返回到第五轮（Node2）
第五调用完成并返回到第一个呼叫
的第一个电话已完成

编辑：用较小的示例解决您的评论。考虑一棵树只有一个没有孩子的节点，这次我们可以更多地关注代码。树是这样的：

 Node0 
    / \ 
NULL  NULL

第一次你的代码被调用时，Node0在传递if (ptr != NULL)是true，因此进入执行if语句。下一行DisplayTree(ptr->rChild);使用NULL调用该函数。在该呼叫期间，if (ptr != NULL)是false因此执行不会输入if语句。结果，执行返回到先前的调用，并且下一行代码是cout << "Name: " << ptr->name...，它打印Node0的信息，这就是为什么有输出。该行完毕后，呼叫，DisplayTree(ptr->lChild);也因为它通过NULL，然后所有的递归结束

来源

2016-11-21 04:45:46 asimes

这仍然是我很混淆 –

@ H.Lee，什么部分是混乱？你能够效仿这个例子吗？ – asimes

那么，当pyr = NULL时，函数如何继续运行。这不会让你摆脱if语句吗？当发生这种情况时，如果另一个调用的函数已经具有不同的参数值，那么程序如何能够返回到先前的函数调用并打印该数据。 –

的“递归函数”的概念很简单，但它可以是一个小在第一次遇到恐吓束手无策。大约有这么多的好资源和我个人都享有以下的人非常多：

http://www.cplusplus.com/articles/D2N36Up4/

http://www.cprogramming.com/tutorial/lesson16.html

正如你可能知道，函数调用被放置在堆栈存储器中，因为这个内存是有限的，一旦太多人被调用而没有结束，程序就会崩溃。因此，递归定义的一个重要部分是停止条件，该条件指定何时以及在什么情况下函数将停止调用自身并中断递归循环。在你的代码中，行if (ptr != NULL)是停止标准。因此，你的问题的答案

所以不会显示代码永远不会得到执行的机会，因为显示代码之前总是有一个函数调用。

是，当它到达树在rChild和lChild是NULL的叶DisplayTree递归调用将结束。这就是当DisplayTree(ptr->rChild);将立即返回叶节点并且cout << "Name: " << ptr->name << "\t" << "Bribe Offered: " << ptr->bribe << endl;代码行有机会执行和打印数据。当然，这一切都取决于你的树是否定义良好。从你的代码中，可以假定函数期望叶节点对于rChild和lChild具有NULL值。因此，如果按照本规范构建树，就会满足停止条件并显示数据。在另一方面，如果树构造不正确，程序将会崩溃，因为堆栈溢出（见en.wikipedia.org/wiki/Stack_overflow）

来源

2016-11-21 06:40:04 MxNx

但是当父节点的左右子节点不为null时怎么办？它不会打破if语句，那么它将如何获得显示数据的机会 –

@ H.Lee这完全取决于您的树是否定义良好。从你的代码中，可以假定函数期望叶节点对于rChild和lChild具有NULL值。所以如果树是按照这个规范构造的，它会显示数据。另一方面，如果树的构造不正确，程序将因堆栈溢出而崩溃（请参阅https://en.wikipedia.org/wiki/Stack_overflow） – MxNx

每当你看到一个递归函数调用，知道函数将回报在某些时候，下一个语句将被执行。但是如何？那么，DisplayTree(ptr->rChild)将继续调用它自己，并在收到空指针时停止。这就是为什么您的if (ptr != NULL)检查如此重要 - 它可以防止无限递归，并且在逻辑上也不想取消引用空指针。

当接收到空指针的函数返回时，编译器将调用堆栈关闭到发出调用的最后一帧。在那里它将转向下一个陈述。这将是它将打印树中最右边的节点的时间。然后它会以ptr->lChild递归调用它自己，它将在中找到最右边的节点树，并重新开始该过程。

这是一个inorder遍历的例子。当我看到这样的函数时，我喜欢对自己说“这个函数首先为右子树，当前节点和左子树执行中间语句”，这使得它更容易理解。

来源

2016-11-21 07:13:55 0x499602D2

当您声明它传递ptr lChild，然后搜索最右侧该树中的节点，只有当rChild为NULL时才会在lChild中打印数据？ –

@ H.Lee是的，只有当给定节点的右子树为空时，递归调用才会返回，编译器将弹出最后一个堆栈帧，并转到前一个堆栈帧的下一个语句（即“cout”声明）。然后它将转到其左边的子树并重复该子树的过程。 – 0x499602D2

@ H.Lee如果您绘制二叉树的图像，您可以使用手指，从根开始，每次函数调用一次向下移动树中的每个节点。 'display（p-> right）'表示将你的手指移动到右边的子树，'display（p-> left）'表示移动到左边的子树。如果函数返回（因为'ptr == NULL'），则转到您来自的前一个节点并转到下一个语句。一切完成后，你的手指应该回到根部。 – 0x499602D2

这个双递归调用如何显示数据C++

回答

相关问题