gpt4 book ai didi

c++ - 使用一个堆栈的后序遍历

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:41:39 49 4
gpt4 key购买 nike

我正在努力了解使用堆栈的 DFS 树遍历。我发现将递归解决方案转换为用于前序遍历的迭代解决方案非常直观。但是,我发现使用此链接很难理解后序遍历。 https://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/ .是否有一种直观且更简单的思考方式? 预购代码:

void iterativePreorder(node *root)
{
// Base Case
if (root == NULL)
return;

// Create an empty stack and push root to it
stack<node *> nodeStack;
nodeStack.push(root);

/* Pop all items one by one. Do following for every popped item
a) print it
b) push its right child
c) push its left child
Note that right child is pushed first so that left is processed first */
while (nodeStack.empty() == false)
{
// Pop the top item from stack and print it
struct node *node = nodeStack.top();
printf ("%d ", node->data);
nodeStack.pop();

// Push right and left children of the popped node to stack
if (node->right)
nodeStack.push(node->right);
if (node->left)
nodeStack.push(node->left);
}
}

最佳答案

有了前序遍历,代码

  • 显示当前节点的数据
  • 遍历左子树
  • 遍历右子树

有了后序遍历,代码

  • 遍历左子树
  • 遍历右子树
  • 显示当前节点的数据

所以不同的是,在进行后序遍历时,数据需要入栈,这样才能最后打印出来。有几种不同的方法可以实现这一点。一种方法是更改​​堆栈实现以区分子指针和数据指针。

弹出子指针时, Action 是

  • 将当前节点作为数据指针推送
  • 将右节点作为子指针压入
  • 将左节点作为子指针压入

当一个数据指针被弹出时, Action 是

  • 显示节点的数据

然后通过将根节点作为子指针压入开始遍历。

关于c++ - 使用一个堆栈的后序遍历,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50359204/

49 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com