树遍历如何工作？

这是序遍历的代码 -树遍历如何工作？

void preOrder(node *root) 
{  
    if(root!=NULL) 
    { 
     cout<<root->data<<" "; 
     preOrder(root->left); 
     preOrder(root->right); 
    }   
}

当我们已经达到左边的最后一个节点，它是如何去正确的节点？我的意思是左右节点之间没有链接，虽然它们都有相同的父节点，但是在到达最后一个节点之后，它如何回到父节点？

来源

2017-06-26 Nick Hill

您应该搜索递归函数如何工作。这会给你一个线索（提示：堆栈相关）。 – Javia1492

有关递归的定义，请参阅递归。 –

@ Yan.F那是错的。每次迭代都不打印每个子节点。它是递归调用的，打印左节点直到空节点，然后右子节点直到空。 – Javia1492

是的！同一节点的两个孩子之间不存在direct链接。

现在用上面的递归代码来帮助你，看看从geeksforgeeks获得的下面的图像。

直接跳转到最左边的节点，因为你知道你是怎么到达了那里，现在让我们来了解它是如何移动回其父等等等等。

当您将出现以下行时，您肯定会因为if(root!=NULL)作为4的左孩子和右孩子为空，仍然没有得到它吗？别担心，请看下面的解释。现在

，你在这是在这种情况下4最左边的节点，负责达到这个节点的路线是：

preOrder(root->left)和你没有见过，这是什么线下至今

即你从未见过以下行：

preOrder(root->right);。

4的左边子女是null，因为递归条件破坏了，最后你看到了preOrder(root->right);。这不是某种巫术，这就是递归。现在，当你看到4的正确孩子，这又是null。

那么，现在根的值是多少？

根的值是2因为2是带你到4放在第一位唯一的价值。递归就像级别内的级别，当最后一级关闭时，呼叫回到它上面的级别2为4。最后，下面的行会把它带到右边的孩子的2这是5。

preOrder(root->right);

拿走：

1）当你看到cout<<root->data<<" ";打印当前根的价值。

2）只要你看到preOrder(root->left);你移动到根的左边的孩子。

3）每当你看到preOrder(root->right);你移动到根的右边的孩子。

4）如果root的值是NULL你什么都不做，你将被带回到呼叫线路，该线路将是preOrder(root->left);或preOrder(root->right);。

如果我们按照我上面说你猜对给定二叉树的前序遍历，这将是：

1 2 4 5 3

现在，我建议你阅读和学习递归，然后接近上方问题再次。

来源

2017-06-27 08:35:56

谢谢Shivam。我昨天看了一些关于递归的视频，现在我知道它是如何工作的。你能告诉区别'if（root！= NULL）'和'if（root == NULL）return;'为上面的代码吗？ –

如果（root！= NULL）是递归中断条件。与for循环类似，您也有递归中的检查条件。当你访问** 4 **的左边孩子时，它是* NULL *，并且它必须在那一刻中断。 –

您正在递归地调用该函数。每次调用preOrder都会在线程的执行堆栈上创建我们称之为框架的东西。这些帧跟随树中的每个路径。当你从函数中return，它的调用帧被从堆栈中移除（或“弹出”）并且控制返回到前一帧。

这就是为什么当你到达叶子时，你“回溯”到父亲然后到兄弟子树（通过第二次调用preOrder）。你所说的“链接”实际上是在执行堆栈上创建的。

来源

2017-06-26 18:39:45 vencik

树遍历如何工作？

回答

相关问题