如何不使用递归算法遍历二叉树的后序遍历？
二叉树的后序遍历（不使用递归）
70
- Patrik Svensson
1
这里有一个很好的描述：http://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/ - user793623
30个回答
43
这是没有访问标记的一个栈版本:
private void postorder(Node head) {
if (head == null) {
return;
}
LinkedList<Node> stack = new LinkedList<Node>();
stack.push(head);
while (!stack.isEmpty()) {
Node next = stack.peek();
boolean finishedSubtrees = (next.right == head || next.left == head);
boolean isLeaf = (next.left == null && next.right == null);
if (finishedSubtrees || isLeaf) {
stack.pop();
System.out.println(next.value);
head = next;
}
else {
if (next.right != null) {
stack.push(next.right);
}
if (next.left != null) {
stack.push(next.left);
}
}
}
}
- tcb
3
1我也需要解释。next.left或next.right怎么可能等于head？这又如何表明你完成了子树？而“完成子树”又是什么意思？ - Nicolas
2该算法访问每个节点并将其子节点放入堆栈，直到到达叶节点。它打印叶节点并临时将“head”指向该节点。然后，一旦打印了叶子并弹出它们的堆栈，它返回到父节点并查看是否访问了任何子树。如果任何一个子节点是“head”，那意味着至少有一个子树已经完全打印。此外，由于父节点总是低于其子节点，因此所有子树都已访问。先序遍历来自于它首先打印叶节点，并优先左节点这一事实。 - vaughnkoch
将孩子们保存在数组或列表中也是一个不错的选择，这样你就可以执行以下操作：
finishedSubtrees = next.right == head and isLeaf = next.length == 0`。这种方法也适用于非二叉树。 - Ciro Santilli OurBigBook.com33
这里提供了两种解决方案，而不使用任何“已访问”标记。
https://leetcode.com/problems/binary-tree-postorder-traversal/
由于树中缺少父指针，显然这是一种基于栈的解决方案。（如果存在父指针，我们将不需要使用栈）。
我们首先将根节点推入堆栈。只要堆栈不为空，我们就从堆栈顶部推送节点的左子节点。如果左子节点不存在，则推送其右子节点。如果它是叶子节点，则处理该节点并将其从堆栈中弹出。
我们还使用一个变量来跟踪先前遍历的节点。目的是确定遍历是否沿着树下降/上升，以及我们还可以知道它是否从左/右上升。
如果我们从左侧上升树，则不希望再次将其左子节点推入堆栈，并且应继续沿树下降（如果其右子节点存在）。如果我们从右侧上升树，则应处理它并将其弹出堆栈。
在以下三种情况下，我们将处理节点并将其从堆栈中弹出：
- 节点是叶子节点（没有子节点）。
- 我们刚刚从左侧上升树，并且不存在右子节点。
- 我们刚刚从右侧上升树。
- 1337c0d3r
30
以下是一段来自维基百科的示例：
这里是维基百科上的一个示例：
nonRecursivePostorder(rootNode)
nodeStack.push(rootNode)
while (! nodeStack.empty())
currNode = nodeStack.peek()
if ((currNode.left != null) and (currNode.left.visited == false))
nodeStack.push(currNode.left)
else
if ((currNode.right != null) and (currNode.right.visited == false))
nodeStack.push(currNode.right)
else
print currNode.value
currNode.visited := true
nodeStack.pop()
- Nader Shirazie
1
1这个解决方案很容易理解。维基实现代码已更改。 ^_^。
https://en.wikipedia.org/wiki/Tree_traversal#Post-order - Charlie 木匠
6
这是我用于迭代后序遍历的方法。我喜欢这种方法，因为：
- 每个循环周期只处理一个转换，易于理解。
- 类似的解决方案适用于中序和前序遍历。
代码:
enum State {LEFT, RIGHT, UP, CURR}
public void iterativePostOrder(Node root) {
Deque<Node> parents = new ArrayDeque<>();
Node curr = root;
State state = State.LEFT;
while(!(curr == root && state == State.UP)) {
switch(state) {
case LEFT:
if(curr.left != null) {
parents.push(curr);
curr = curr.left;
} else {
state = RIGHT;
}
break;
case RIGHT:
if(curr.right != null) {
parents.push(curr);
curr = curr.right;
state = LEFT;
} else {
state = CURR;
}
break;
case CURR:
System.out.println(curr);
state = UP;
break;
case UP:
Node child = curr;
curr = parents.pop();
state = child == curr.left ? RIGHT : CURR;
break;
default:
throw new IllegalStateException();
}
}
}
解释:
你可以这样想象这些步骤：
- 尝试向左
- 如果左边的节点存在：再次尝试向左
- 如果左边的节点不存在：尝试向右
- 尝试向右
- 如果右边的节点存在：从那里开始尝试向左
- 如果没有右边的节点，那么你就到了叶子节点：尝试当前节点
- 尝试当前节点
- 打印当前节点
- 所有下面的节点都已经执行完毕（后序遍历）：尝试向上
- 尝试向上
- 如果节点是根节点，则没有向上的节点，所以退出
- 如果从左边上来，尝试向右
- 如果从右边上来，尝试当前节点
- bcorso
1
哇，这很容易理解并且灵活修改，不错！ - Samuel Li
3
以下是一种使用 C++ 实现的解决方案，不需要在树中进行任何存储。
相反，它使用两个堆栈。一个用于帮助我们遍历，另一个用于存储节点，以便我们可以对它们进行后序遍历。
std::stack<Node*> leftStack;
std::stack<Node*> rightStack;
Node* currentNode = m_root;
while( !leftStack.empty() || currentNode != NULL )
{
if( currentNode )
{
leftStack.push( currentNode );
currentNode = currentNode->m_left;
}
else
{
currentNode = leftStack.top();
leftStack.pop();
rightStack.push( currentNode );
currentNode = currentNode->m_right;
}
}
while( !rightStack.empty() )
{
currentNode = rightStack.top();
rightStack.pop();
std::cout << currentNode->m_value;
std::cout << "\n";
}
- Jens Agby
2
深度优先、后序遍历、非递归、无栈
当你有父节点时：
当你有父节点时：
node_t
{
left,
right
parent
}
traverse(node_t rootNode)
{
bool backthreading = false
node_t node = rootNode
while(node <> 0)
if (node->left <> 0) and backthreading = false then
node = node->left
continue
endif
>>> process node here <<<
if node->right <> 0 then
lNode = node->right
backthreading = false
else
node = node->parent
backthreading = true
endif
endwhile
- Tim
2
// 使用标志的Java版本
public static <T> void printWithFlag(TreeNode<T> root){
if(null == root) return;
Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();
stack.add(root);
while(stack.size() > 0){
if(stack.peek().isVisit()){
System.out.print(stack.pop().getValue() + " ");
}else{
TreeNode<T> tempNode = stack.peek();
if(tempNode.getRight()!=null){
stack.add(tempNode.getRight());
}
if(tempNode.getLeft() != null){
stack.add(tempNode.getLeft());
}
tempNode.setVisit(true);
}
}
}
- Jiaji Li
2
import java.util.Stack;
public class IterativePostOrderTraversal extends BinaryTree {
public static void iterativePostOrderTraversal(Node root){
Node cur = root;
Node pre = root;
Stack<Node> s = new Stack<Node>();
if(root!=null)
s.push(root);
System.out.println("sysout"+s.isEmpty());
while(!s.isEmpty()){
cur = s.peek();
if(cur==pre||cur==pre.left ||cur==pre.right){// we are traversing down the tree
if(cur.left!=null){
s.push(cur.left);
}
else if(cur.right!=null){
s.push(cur.right);
}
if(cur.left==null && cur.right==null){
System.out.println(s.pop().data);
}
}else if(pre==cur.left){// we are traversing up the tree from the left
if(cur.right!=null){
s.push(cur.right);
}else if(cur.right==null){
System.out.println(s.pop().data);
}
}else if(pre==cur.right){// we are traversing up the tree from the right
System.out.println(s.pop().data);
}
pre=cur;
}
}
public static void main(String args[]){
BinaryTree bt = new BinaryTree();
Node root = bt.generateTree();
iterativePostOrderTraversal(root);
}
}
- Anupam Gupta
1
不使用递归的后序遍历逻辑
在后序遍历中，处理顺序为左-右-根。因此，我们需要先访问左侧部分，然后再访问其他部分。对于树的每个节点，我们将尝试尽可能向左遍历下去。对于每个当前节点，如果右子节点存在，则在将当前节点推入堆栈之前将其推入堆栈。只要根不是NULL/None，就重复这个过程。现在从堆栈中弹出一个节点并检查该节点的右子节点是否存在。如果存在，则检查它是否与顶部元素相同。如果它们相同，则表示我们还没有处理完右部分，因此在处理当前节点之前，我们必须处理右部分，并将顶部元素（右子节点）弹出并将当前节点推回堆栈。每次弹出的元素都是头部。如果当前元素与顶部不同且头部不为NULL，则我们已经完成了左侧和右侧部分，现在可以处理当前节点。我们必须重复上述步骤，直到堆栈为空。
def Postorder_iterative(head):
if head is None:
return None
sta=stack()
while True:
while head is not None:
if head.r:
sta.push(head.r)
sta.push(head)
head=head.l
if sta.top is -1:
break
head = sta.pop()
if head.r is not None and sta.top is not -1 and head.r is sta.A[sta.top]:
x=sta.pop()
sta.push(head)
head=x
else:
print(head.val,end = ' ')
head=None
print()
- suvojit_007
0
这里也有 Python 版本：
class Node:
def __init__(self,data):
self.data = data
self.left = None
self.right = None
def postOrderIterative(root):
if root is None :
return
s1 = []
s2 = []
s1.append(root)
while(len(s1)>0):
node = s1.pop()
s2.append(node)
if(node.left!=None):
s1.append(node.left)
if(node.right!=None):
s1.append(node.right)
while(len(s2)>0):
node = s2.pop()
print(node.data)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
postOrderIterative(root)
这是输出结果 ::
- Akash Kandpal
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接