在不使用递归的情况下对二叉树进行后序遍历的算法是什么？
问问题
107546 次
30 回答
41
这是具有一个堆栈且没有访问标志的版本：
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);
}
}
}
}
于 2013-04-18T20:21:24.933 回答
33
这是一个链接，它提供了另外两个解决方案，而不使用任何访问过的标志。
https://leetcode.com/problems/binary-tree-postorder-traversal/
由于树中缺少父指针，这显然是基于堆栈的解决方案。（如果有父指针，我们就不需要堆栈）。
我们首先将根节点推入堆栈。当堆栈不为空时，我们继续从堆栈顶部推送节点的左子节点。如果左孩子不存在，我们推它的右孩子。如果它是叶节点，我们处理该节点并将其从堆栈中弹出。
我们还使用变量来跟踪先前遍历的节点。目的是判断遍历是从树的下降/上升，我们也可以知道它是从左/右上升。
如果我们从左边向上提升树，我们不想再次将它的左孩子推入堆栈，如果它的右孩子存在，我们应该继续沿着树向下提升。如果我们从右边提升树，我们应该处理它并将它从堆栈中弹出。
在这 3 种情况下，我们将处理节点并将其从堆栈中弹出：
- 该节点是叶节点（无子节点）
- 我们只是从左边遍历树，不存在右孩子。
- 我们只是从右边遍历树。
于 2010-10-28T17:55:55.650 回答
29
这是来自维基百科的示例：
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()
于 2009-08-18T15:41:54.720 回答
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();
}
}
}
解释：
你可以考虑这样的步骤：
- 尝试向左
- 如果左节点存在：再次尝试 LEFT
- 如果左节点不存在：尝试 RIGHT
- 尝试正确
- 如果存在正确的节点：从那里尝试 LEFT
- 如果不存在权利，那么你就在一片叶子上：试试 CURR
- 试试 CURR
- 打印当前节点
- 以下所有节点均已执行（订单后）：Try UP
- 试试看
- 如果节点是root，则没有UP，所以EXIT
- 如果从左边上来，试试右边
- 如果从右边上来，试试 CURR
于 2015-07-27T00:34:41.560 回答
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);
}
}
于 2012-03-31T15:41:32.373 回答
2
这是 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";
}
于 2012-09-07T23:37:08.680 回答
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);
}
}
}
于 2012-12-24T05:40:21.420 回答
1
深度优先，后序，非递归，无栈
当你有父母时：
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
于 2015-05-20T13:16:30.367 回答
1
不使用 Recursion 的 Post 顺序遍历逻辑
中Postorder traversal，处理顺序为left-right-current. 所以我们需要先访问左侧部分，然后再访问其他部分。对于树的每个节点，我们将尝试尽可能地向下遍历树。对于每个当前节点，如果存在右子节点，则将其推入堆栈，然后再推入当前节点，而 root 不是 NULL/None。现在从堆栈中弹出一个节点并检查该节点的右孩子是否存在。如果存在，则检查它是否与顶部元素相同。如果它们相同，则表明我们还没有完成正确的部分，所以在处理当前节点之前，我们必须处理正确的部分，然后弹出顶部元素（右子元素）并将当前节点推回堆栈. 每次我们的头都是弹出的元素。如果当前元素与顶部不同，并且 head 不为 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()
于 2018-07-29T18:23:29.157 回答
0
void postorder_stack(Node * root){
stack ms;
ms.top = -1;
if(root == NULL) return ;
Node * temp ;
push(&ms,root);
Node * prev = NULL;
while(!is_empty(ms)){
temp = peek(ms);
/* case 1. We are nmoving down the tree. */
if(prev == NULL || prev->left == temp || prev->right == temp){
if(temp->left)
push(&ms,temp->left);
else if(temp->right)
push(&ms,temp->right);
else {
/* If node is leaf node */
printf("%d ", temp->value);
pop(&ms);
}
}
/* case 2. We are moving up the tree from left child */
if(temp->left == prev){
if(temp->right)
push(&ms,temp->right);
else
printf("%d ", temp->value);
}
/* case 3. We are moving up the tree from right child */
if(temp->right == prev){
printf("%d ", temp->value);
pop(&ms);
}
prev = temp;
}
}
于 2014-02-09T06:44:41.087 回答
0
请参阅这个完整的 Java 实现。只需复制代码并粘贴到您的编译器中。它会正常工作。
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
class Node
{
Node left;
String data;
Node right;
Node(Node left, String data, Node right)
{
this.left = left;
this.right = right;
this.data = data;
}
public String getData()
{
return data;
}
}
class Tree
{
Node node;
//insert
public void insert(String data)
{
if(node == null)
node = new Node(null,data,null);
else
{
Queue<Node> q = new LinkedList<Node>();
q.add(node);
while(q.peek() != null)
{
Node temp = q.remove();
if(temp.left == null)
{
temp.left = new Node(null,data,null);
break;
}
else
{
q.add(temp.left);
}
if(temp.right == null)
{
temp.right = new Node(null,data,null);
break;
}
else
{
q.add(temp.right);
}
}
}
}
public void postorder(Node node)
{
if(node == null)
return;
postorder(node.left);
postorder(node.right);
System.out.print(node.getData()+" --> ");
}
public void iterative(Node node)
{
Stack<Node> s = new Stack<Node>();
while(true)
{
while(node != null)
{
s.push(node);
node = node.left;
}
if(s.peek().right == null)
{
node = s.pop();
System.out.print(node.getData()+" --> ");
if(node == s.peek().right)
{
System.out.print(s.peek().getData()+" --> ");
s.pop();
}
}
if(s.isEmpty())
break;
if(s.peek() != null)
{
node = s.peek().right;
}
else
{
node = null;
}
}
}
}
class Main
{
public static void main(String[] args)
{
Tree t = new Tree();
t.insert("A");
t.insert("B");
t.insert("C");
t.insert("D");
t.insert("E");
t.postorder(t.node);
System.out.println();
t.iterative(t.node);
System.out.println();
}
}
于 2014-03-10T16:39:01.247 回答
0
这里我在c#（.net）中粘贴不同的版本以供参考：（对于in-order iterative traversal你可以参考：Help me understand Inorder Traversal without using recursion）
- 维基（http://en.wikipedia.org/wiki/Post-order%5Ftraversal#Implementations）（优雅）
- 单栈的另一个版本（#1 和 #2：基本上使用了这样一个事实，即在后序遍历中，在访问实际节点之前访问了右子节点 - 所以，我们只需检查栈顶的右子节点是否确实是上次访问过的订单遍历节点-我在下面的代码片段中添加了注释以获取详细信息）
- 使用两个堆栈版本（参考：http ://www.geeksforgeeks.org/iterative-postorder-traversal/ ）（更简单：基本上后序遍历反向只不过是前序遍历，只需先访问正确的节点，然后然后左节点）
- 使用访客标志（简单）
- 单元测试
~
public string PostOrderIterative_WikiVersion()
{
List<int> nodes = new List<int>();
if (null != this._root)
{
BinaryTreeNode lastPostOrderTraversalNode = null;
BinaryTreeNode iterativeNode = this._root;
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
while ((stack.Count > 0)//stack is not empty
|| (iterativeNode != null))
{
if (iterativeNode != null)
{
stack.Push(iterativeNode);
iterativeNode = iterativeNode.Left;
}
else
{
var stackTop = stack.Peek();
if((stackTop.Right != null)
&& (stackTop.Right != lastPostOrderTraversalNode))
{
//i.e. last traversal node is not right element, so right sub tree is not
//yet, traversed. so we need to start iterating over right tree
//(note left tree is by default traversed by above case)
iterativeNode = stackTop.Right;
}
else
{
//if either the iterative node is child node (right and left are null)
//or, stackTop's right element is nothing but the last traversal node
//(i.e; the element can be popped as the right sub tree have been traversed)
var top = stack.Pop();
Debug.Assert(top == stackTop);
nodes.Add(top.Element);
lastPostOrderTraversalNode = top;
}
}
}
}
return this.ListToString(nodes);
}
这是一个堆栈的后序遍历（我的版本）
public string PostOrderIterative()
{
List<int> nodes = new List<int>();
if (null != this._root)
{
BinaryTreeNode lastPostOrderTraversalNode = null;
BinaryTreeNode iterativeNode = null;
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
stack.Push(this._root);
while(stack.Count > 0)
{
iterativeNode = stack.Pop();
if ((iterativeNode.Left == null)
&& (iterativeNode.Right == null))
{
nodes.Add(iterativeNode.Element);
lastPostOrderTraversalNode = iterativeNode;
//make sure the stack is not empty as we need to peek at the top
//for ex, a tree with just root node doesn't have to enter loop
//and also node Peek() will throw invalidoperationexception
//if it is performed if the stack is empty
//so, it handles both of them.
while(stack.Count > 0)
{
var stackTop = stack.Peek();
bool removeTop = false;
if ((stackTop.Right != null) &&
//i.e. last post order traversal node is nothing but right node of
//stacktop. so, all the elements in the right subtree have been visted
//So, we can pop the top element
(stackTop.Right == lastPostOrderTraversalNode))
{
//in other words, we can pop the top if whole right subtree is
//traversed. i.e. last traversal node should be the right node
//as the right node will be traverse once all the subtrees of
//right node has been traversed
removeTop = true;
}
else if(
//right subtree is null
(stackTop.Right == null)
&& (stackTop.Left != null)
//last traversal node is nothing but the root of left sub tree node
&& (stackTop.Left == lastPostOrderTraversalNode))
{
//in other words, we can pop the top of stack if right subtree is null,
//and whole left subtree has been traversed
removeTop = true;
}
else
{
break;
}
if(removeTop)
{
var top = stack.Pop();
Debug.Assert(stackTop == top);
lastPostOrderTraversalNode = top;
nodes.Add(top.Element);
}
}
}
else
{
stack.Push(iterativeNode);
if(iterativeNode.Right != null)
{
stack.Push(iterativeNode.Right);
}
if(iterativeNode.Left != null)
{
stack.Push(iterativeNode.Left);
}
}
}
}
return this.ListToString(nodes);
}
使用两个堆栈
public string PostOrderIterative_TwoStacksVersion()
{
List<int> nodes = new List<int>();
if (null != this._root)
{
Stack<BinaryTreeNode> postOrderStack = new Stack<BinaryTreeNode>();
Stack<BinaryTreeNode> rightLeftPreOrderStack = new Stack<BinaryTreeNode>();
rightLeftPreOrderStack.Push(this._root);
while(rightLeftPreOrderStack.Count > 0)
{
var top = rightLeftPreOrderStack.Pop();
postOrderStack.Push(top);
if(top.Left != null)
{
rightLeftPreOrderStack.Push(top.Left);
}
if(top.Right != null)
{
rightLeftPreOrderStack.Push(top.Right);
}
}
while(postOrderStack.Count > 0)
{
var top = postOrderStack.Pop();
nodes.Add(top.Element);
}
}
return this.ListToString(nodes);
}
在 C# (.net) 中使用访问标志：
public string PostOrderIterative()
{
List<int> nodes = new List<int>();
if (null != this._root)
{
BinaryTreeNode iterativeNode = null;
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
stack.Push(this._root);
while(stack.Count > 0)
{
iterativeNode = stack.Pop();
if(iterativeNode.visted)
{
//reset the flag, for further traversals
iterativeNode.visted = false;
nodes.Add(iterativeNode.Element);
}
else
{
iterativeNode.visted = true;
stack.Push(iterativeNode);
if(iterativeNode.Right != null)
{
stack.Push(iterativeNode.Right);
}
if(iterativeNode.Left != null)
{
stack.Push(iterativeNode.Left);
}
}
}
}
return this.ListToString(nodes);
}
定义：
class BinaryTreeNode
{
public int Element;
public BinaryTreeNode Left;
public BinaryTreeNode Right;
public bool visted;
}
string ListToString(List<int> list)
{
string s = string.Join(", ", list);
return s;
}
单元测试
[TestMethod]
public void PostOrderTests()
{
int[] a = { 13, 2, 18, 1, 5, 17, 20, 3, 6, 16, 21, 4, 14, 15, 25, 22, 24 };
BinarySearchTree bst = new BinarySearchTree();
foreach (int e in a)
{
string s1 = bst.PostOrderRecursive();
string s2 = bst.PostOrderIterativeWithVistedFlag();
string s3 = bst.PostOrderIterative();
string s4 = bst.PostOrderIterative_WikiVersion();
string s5 = bst.PostOrderIterative_TwoStacksVersion();
Assert.AreEqual(s1, s2);
Assert.AreEqual(s2, s3);
Assert.AreEqual(s3, s4);
Assert.AreEqual(s4, s5);
bst.Add(e);
bst.Delete(e);
bst.Add(e);
s1 = bst.PostOrderRecursive();
s2 = bst.PostOrderIterativeWithVistedFlag();
s3 = bst.PostOrderIterative();
s4 = bst.PostOrderIterative_WikiVersion();
s5 = bst.PostOrderIterative_TwoStacksVersion();
Assert.AreEqual(s1, s2);
Assert.AreEqual(s2, s3);
Assert.AreEqual(s3, s4);
Assert.AreEqual(s4, s5);
}
Debug.WriteLine(string.Format("PostOrderIterative: {0}", bst.PostOrderIterative()));
Debug.WriteLine(string.Format("PostOrderIterative_WikiVersion: {0}", bst.PostOrderIterative_WikiVersion()));
Debug.WriteLine(string.Format("PostOrderIterative_TwoStacksVersion: {0}", bst.PostOrderIterative_TwoStacksVersion()));
Debug.WriteLine(string.Format("PostOrderIterativeWithVistedFlag: {0}", bst.PostOrderIterativeWithVistedFlag()));
Debug.WriteLine(string.Format("PostOrderRecursive: {0}", bst.PostOrderRecursive()));
}
于 2014-07-13T05:16:09.280 回答
0
具有 1 个堆栈且没有标志的 Python：
def postorderTraversal(self, root):
ret = []
if not root:
return ret
stack = [root]
current = None
while stack:
previous = current
current = stack.pop()
if previous and ((previous is current) or (previous is current.left) or (previous is current.right)):
ret.append(current.val)
else:
stack.append(current)
if current.right:
stack.append(current.right)
if current.left:
stack.append(current.left)
return ret
更好的是使用类似的语句，以便遍历也有效
def inorderTraversal(self, root):
ret = []
if not root:
return ret
stack = [root]
current = None
while stack:
previous = current
current = stack.pop()
if None == previous or previous.left is current or previous.right is current:
if current.right:
stack.append(current.right)
stack.append(current)
if current.left:
stack.append(current.left)
else:
ret.append(current.val)
return ret
于 2015-01-06T01:03:17.157 回答
0
我没有添加节点类，因为它不是特别相关或任何测试用例，将这些作为练习留给读者等。
void postOrderTraversal(node* root)
{
if(root == NULL)
return;
stack<node*> st;
st.push(root);
//store most recent 'visited' node
node* prev=root;
while(st.size() > 0)
{
node* top = st.top();
if((top->left == NULL && top->right == NULL))
{
prev = top;
cerr<<top->val<<" ";
st.pop();
continue;
}
else
{
//we can check if we are going back up the tree if the current
//node has a left or right child that was previously outputted
if((top->left == prev) || (top->right== prev))
{
prev = top;
cerr<<top->val<<" ";
st.pop();
continue;
}
if(top->right != NULL)
st.push(top->right);
if(top->left != NULL)
st.push(top->left);
}
}
cerr<<endl;
}
运行时间 O(n) - 需要访问所有节点和空间 O(n) - 对于堆栈，最坏情况树是单行链表
于 2015-01-15T22:11:36.253 回答
0
很高兴看到这么多精力充沛的方法来解决这个问题。确实很励志！
我遇到了这个主题，寻找一个简单的迭代解决方案来删除我的二叉树实现中的所有节点。我尝试了其中一些，并尝试了在网上其他地方找到的类似的东西，但没有一个是我真正喜欢的。
问题是，我正在为一个非常特定的目的（比特币区块链索引）开发一个数据库索引模块，我的数据存储在磁盘上，而不是 RAM 中。我根据需要交换页面，进行自己的内存管理。它速度较慢，但速度足够快，并且存储在磁盘上而不是 RAM 上，我对浪费空间没有宗教意义（硬盘很便宜）。
出于这个原因，我的二叉树中的节点具有父指针。这就是我所说的（全部）额外空间。我需要父母，因为出于各种目的，我需要遍历树的上升和下降。
考虑到这一点，我很快写下了一段关于如何完成的伪代码，即后序遍历动态删除节点。它已经实施和测试，并成为我解决方案的一部分。而且速度也很快。
问题是：当节点具有父指针时，它变得非常非常简单，而且因为我可以取消父节点到“刚刚离开”节点的链接。
这是迭代后订单删除的伪代码：
Node current = root;
while (current)
{
if (current.left) current = current.left; // Dive down left
else if (current.right) current = current.right; // Dive down right
else
{
// Node "current" is a leaf, i.e. no left or right child
Node parent = current.parent; // assuming root.parent == null
if (parent)
{
// Null out the parent's link to the just departing node
if (parent.left == current) parent.left = null;
else parent.right = null;
}
delete current;
current = parent;
}
}
root = null;
如果您对编码复杂集合的更理论方法感兴趣（例如我的二叉树，它实际上是一个自平衡的红黑树），请查看以下链接：
http://opendatastructures.org/versions/edition-0.1e/ods-java/6_2_BinarySearchTree_Unbala.html http://opendatastructures.org/versions/edition-0.1e/ods-java/9_2_RedBlackTree_Simulated_.html https://www。 cs.auckland.ac.nz/software/AlgAnim/red_black.html
快乐编码:-)
Søren 雾 http://iprotus.eu/
于 2015-04-05T20:28:06.800 回答
0
1.1 创建一个空栈
2.1 在 root 不为 NULL 时执行以下操作
a) Push root's right child and then root to stack.
b) Set root as root's left child.
2.2 从堆栈中弹出一个项目并将其设置为root。
a) If the popped item has a right child and the right child
is at top of stack, then remove the right child from stack,
push the root back and set root as root's right child.
b) Else print root's data and set root as NULL.
2.3 当堆栈不为空时重复步骤 2.1 和 2.2。
于 2015-10-08T17:26:47.590 回答
0
这是具有两个堆栈的 Java 实现
public static <T> List<T> iPostOrder(BinaryTreeNode<T> root) {
if (root == null) {
return Collections.emptyList();
}
List<T> result = new ArrayList<T>();
Deque<BinaryTreeNode<T>> firstLevel = new LinkedList<BinaryTreeNode<T>>();
Deque<BinaryTreeNode<T>> secondLevel = new LinkedList<BinaryTreeNode<T>>();
firstLevel.push(root);
while (!firstLevel.isEmpty()) {
BinaryTreeNode<T> node = firstLevel.pop();
secondLevel.push(node);
if (node.hasLeftChild()) {
firstLevel.push(node.getLeft());
}
if (node.hasRightChild()) {
firstLevel.push(node.getRight());
}
}
while (!secondLevel.isEmpty()) {
result.add(secondLevel.pop().getData());
}
return result;
}
这是单元测试
@Test
public void iterativePostOrderTest() {
BinaryTreeNode<Integer> bst = BinaryTreeUtil.<Integer>fromInAndPostOrder(new Integer[]{4,2,5,1,6,3,7}, new Integer[]{4,5,2,6,7,3,1});
assertThat(BinaryTreeUtil.iPostOrder(bst).toArray(new Integer[0]), equalTo(new Integer[]{4,5,2,6,7,3,1}));
}
于 2016-04-06T15:38:43.740 回答
0
/**
* This code will ensure holding of chain(links) of nodes from the root to till the level of the tree.
* The number of extra nodes in the memory (other than tree) is height of the tree.
* I haven't used java stack instead used this ParentChain.
* This parent chain is the link for any node from the top(root node) to till its immediate parent.
* This code will not require any altering of existing BinaryTree (NO flag/parent on all the nodes).
*
* while visiting the Node 11; ParentChain will be holding the nodes 9 -> 8 -> 7 -> 1 where (-> is parent)
*
* 1
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
2 7
/ \ /
/ \ /
/ \ /
/ \ /
3 6 8
/ \ /
/ \ /
4 5 9
/ \
10 11
*
* @author ksugumar
*
*/
public class InOrderTraversalIterative {
public static void main(String[] args) {
BTNode<String> rt;
String[] dataArray = {"1","2","3","4",null,null,"5",null,null,"6",null,null,"7","8","9","10",null,null,"11",null,null,null,null};
rt = BTNode.buildBTWithPreOrder(dataArray, new Counter(0));
BTDisplay.printTreeNode(rt);
inOrderTravesal(rt);
}
public static void postOrderTravesal(BTNode<String> root) {
ParentChain rootChain = new ParentChain(root);
rootChain.Parent = new ParentChain(null);
while (root != null) {
//Going back to parent
if(rootChain.leftVisited && rootChain.rightVisited) {
System.out.println(root.data); //Visit the node.
ParentChain parentChain = rootChain.Parent;
rootChain.Parent = null; //Avoid the leak
rootChain = parentChain;
root = rootChain.root;
continue;
}
//Traverse Left
if(!rootChain.leftVisited) {
rootChain.leftVisited = true;
if (root.left != null) {
ParentChain local = new ParentChain(root.left); //It is better to use pool to reuse the instances.
local.Parent = rootChain;
rootChain = local;
root = root.left;
continue;
}
}
//Traverse RIGHT
if(!rootChain.rightVisited) {
rootChain.rightVisited = true;
if (root.right != null) {
ParentChain local = new ParentChain(root.right); //It is better to use pool to reuse the instances.
local.Parent = rootChain;
rootChain = local;
root = root.right;
continue;
}
}
}
}
class ParentChain {
BTNode<String> root;
ParentChain Parent;
boolean leftVisited = false;
boolean rightVisited = false;
public ParentChain(BTNode<String> node) {
this.root = node;
}
@Override
public String toString() {
return root.toString();
}
}
于 2016-04-18T13:22:09.167 回答
0
void display_without_recursion(struct btree **b)
{
deque< struct btree* > dtree;
if(*b)
dtree.push_back(*b);
while(!dtree.empty() )
{
struct btree* t = dtree.front();
cout << t->nodedata << " " ;
dtree.pop_front();
if(t->right)
dtree.push_front(t->right);
if(t->left)
dtree.push_front(t->left);
}
cout << endl;
}
于 2016-04-23T22:55:01.437 回答
0
import java.util.Stack;
class Practice
{
public static void main(String arr[])
{
Practice prc = new Practice();
TreeNode node1 = (prc).new TreeNode(1);
TreeNode node2 = (prc).new TreeNode(2);
TreeNode node3 = (prc).new TreeNode(3);
TreeNode node4 = (prc).new TreeNode(4);
TreeNode node5 = (prc).new TreeNode(5);
TreeNode node6 = (prc).new TreeNode(6);
TreeNode node7 = (prc).new TreeNode(7);
node1.left = node2;
node1.right = node3;
node2.left = node4;
node2.right = node5;
node3.left = node6;
node3.right = node7;
postOrderIteratively(node1);
}
public static void postOrderIteratively(TreeNode root)
{
Stack<Entry> stack = new Stack<Entry>();
Practice prc = new Practice();
stack.push((prc).new Entry(root, false));
while (!stack.isEmpty())
{
Entry entry = stack.pop();
TreeNode node = entry.node;
if (entry.flag == false)
{
if (node.right == null && node.left == null)
{
System.out.println(node.data);
} else
{
stack.push((prc).new Entry(node, true));
if (node.right != null)
{
stack.push((prc).new Entry(node.right, false));
}
if (node.left != null)
{
stack.push((prc).new Entry(node.left, false));
}
}
} else
{
System.out.println(node.data);
}
}
}
class TreeNode
{
int data;
int leafCount;
TreeNode left;
TreeNode right;
public TreeNode(int data)
{
this.data = data;
}
public int getLeafCount()
{
return leafCount;
}
public void setLeafCount(int leafCount)
{
this.leafCount = leafCount;
}
public TreeNode getLeft()
{
return left;
}
public void setLeft(TreeNode left)
{
this.left = left;
}
public TreeNode getRight()
{
return right;
}
public void setRight(TreeNode right)
{
this.right = right;
}
@Override
public String toString()
{
return "" + this.data;
}
}
class Entry
{
Entry(TreeNode node, boolean flag)
{
this.node = node;
this.flag = flag;
}
TreeNode node;
boolean flag;
@Override
public String toString()
{
return node.toString();
}
}
}
于 2016-08-22T04:29:59.673 回答
0
我一直在寻找一个性能良好且易于定制的代码片段。线程树并不“简单”。双栈解决方案需要 O(n) 内存。LeetCode 解决方案和tcb解决方案有额外的检查和推送...
这是一种翻译成 C 的经典算法，对我有用：
void postorder_traversal(TreeNode *p, void (*visit)(TreeNode *))
{
TreeNode *stack[40]; // simple C stack, no overflow check
TreeNode **sp = stack;
TreeNode *last_visited = NULL;
for (; p != NULL; p = p->left)
*sp++ = p;
while (sp != stack) {
p = sp[-1];
if (p->right == NULL || p->right == last_visited) {
visit(p);
last_visited = p;
sp--;
} else {
for (p = p->right; p != NULL; p = p->left)
*sp++ = p;
}
}
}
恕我直言，该算法比执行良好且可读的 wikipedia.org / Tree_traversal 伪代码更容易遵循。有关详细信息，请参阅 Knuth 的第 1 卷中二叉树练习的答案。
于 2017-12-25T06:42:45.903 回答
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)
这是输出::
于 2018-01-16T06:50:55.137 回答
0
因此，您可以使用一个堆栈来进行后序遍历。
private void PostOrderTraversal(Node pos) {
Stack<Node> stack = new Stack<Node>();
do {
if (pos==null && (pos=stack.peek().right)==null) {
for (visit(stack.peek()); stack.pop()==(stack.isEmpty()?null:stack.peek().right); visit(stack.peek())) {}
} else if(pos!=null) {
stack.push(pos);
pos=pos.left;
}
} while (!stack.isEmpty());
}
于 2018-06-30T04:49:58.410 回答
0
无递归执行后序遍历的两种方法：
1. 使用访问节点的一个 HashSet 和一个堆栈进行回溯：
private void postOrderWithoutRecursion(TreeNode root) {
if (root == null || root.left == null && root.right == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
Set<TreeNode> visited = new HashSet<>();
while (!stack.empty() || root != null) {
if (root != null) {
stack.push(root);
visited.add(root);
root = root.left;
} else {
root = stack.peek();
if (root.right == null || visited.contains(root.right)) {
System.out.print(root.val+" ");
stack.pop();
root = null;
} else {
root = root.right;
}
}
}
}
时间复杂度：O(n)
空间复杂度：O(2n)
2. 使用 Tree Altering 方法：
private void postOrderWithoutRecursionAlteringTree(TreeNode root) {
if (root == null || root.left == null && root.right == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
while (!stack.empty() || root != null) {
if (root != null) {
stack.push(root);
root = root.left;
} else {
root = stack.peek();
if (root.right == null) {
System.out.print(root.val+" ");
stack.pop();
root = null;
} else {
TreeNode temp = root.right;
root.right = null;
root = temp;
}
}
}
}
时间复杂度：O(n)
空间复杂度：O(n)
树节点类：
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) {
val = x;
}
}
于 2018-11-26T06:48:13.867 回答
0
这是一个简短的（步行者是 3 行）版本，我需要用 Python 编写一个通用树。当然，也适用于更有限的二叉树。树是节点和子节点列表的元组。它只有一个堆栈。示例用法显示。
def postorder(tree):
def do_something(x): # Your function here
print(x),
def walk_helper(root_node, calls_to_perform):
calls_to_perform.append(partial(do_something, root_node[0]))
for child in root_node[1]:
calls_to_perform.append(partial(walk_helper, child, calls_to_perform))
calls_to_perform = []
calls_to_perform.append(partial(walk_helper, tree, calls_to_perform))
while calls_to_perform:
calls_to_perform.pop()()
postorder(('a', [('b', [('c', []), ('d', [])])]))
d c b a
于 2019-02-14T20:05:17.643 回答
0
最简单的解决方案，它可能看起来不是最好的答案，但很容易理解。而且我相信，如果您了解解决方案，那么您可以对其进行修改以提供最佳解决方案
// 使用两个栈
public List<Integer> postorderTraversal(TreeNode root){
Stack<TreeNode> st=new Stack<>();
Stack<TreeNode> st2=new Stack<>();
ArrayList<Integer> al = new ArrayList<Integer>();
if(root==null)
return al;
st.push(root); //push the root to 1st stack
while(!st.isEmpty())
{
TreeNode curr=st.pop();
st2.push(curr);
if(curr.left!=null)
st.push(curr.left);
if(curr.right!=null)
st.push(curr.right);
}
while(!st2.isEmpty())
al.add(st2.pop().val);
//this ArrayList contains the postorder traversal
return al;
}
于 2019-07-04T06:08:12.480 回答
0
python中简单直观的解决方案。
while stack:
node = stack.pop()
if node:
if isinstance(node,TreeNode):
stack.append(node.val)
stack.append(node.right)
stack.append(node.left)
else:
post.append(node)
return post
于 2019-11-30T19:00:37.073 回答
0
这就是我想出的后订单迭代器：
class PostOrderIterator
implements Iterator<T> {
private Stack<Node<T>> stack;
private Node<T> prev;
PostOrderIterator(Node<T> root) {
this.stack = new Stack<>();
recurse(root);
this.prev = this.stack.peek();
}
private void recurse(Node<T> node) {
if(node == null) {
return;
}
while(node != null) {
stack.push(node);
node = node.left;
}
recurse(stack.peek().right);
}
@Override
public boolean hasNext() {
return !stack.isEmpty();
}
@Override
public T next() {
if(stack.peek().right != this.prev) {
recurse(stack.peek().right);
}
Node<T> next = stack.pop();
this.prev = next;
return next.value;
}
}
基本上，主要思想是您应该考虑初始化过程如何将第一个要打印的项目放在堆栈顶部，而堆栈的其余部分则跟随递归所触及的节点。其余的将变得更容易钉牢。
此外，从设计的角度来看，PostOrderIterator它是一个内部类，通过树类的一些工厂方法公开为Iterator<T>.
于 2020-08-08T14:39:20.847 回答
0
在后序遍历中，首先访问节点的左孩子，然后是其右孩子，最后是节点本身。这种树遍历方法类似于图的深度优先搜索（DFS）遍历。
时间复杂度：O(n)
空间复杂度：O(n)
下面是python中后序遍历的迭代实现：
class Node:
def __init__(self, data=None, left=None, right=None):
self.data = data
self.left = left
self.right = right
def post_order(node):
if node is None:
return []
stack = []
nodes = []
last_node_visited = None
while stack or node:
if node:
stack.append(node)
node = node.left
else:
peek_node = stack[-1]
if peek_node.right and last_node_visited != peek_node.right:
node = peek_node.right
else:
nodes.append(peek_node.data)
last_node_visited = stack.pop()
return nodes
def main():
'''
Construct the below binary tree:
15
/ \
/ \
/ \
10 20
/ \ / \
8 12 16 25
'''
root = Node(15)
root.left = Node(10)
root.right = Node(20)
root.left.left = Node(8)
root.left.right = Node(12)
root.right.left = Node(16)
root.right.right = Node(25)
print(post_order(root))
if __name__ == '__main__':
main()
于 2020-11-02T22:58:39.250 回答
0
为了编写这些递归方法的迭代等价物，我们可以首先了解递归方法本身是如何在程序的堆栈上执行的。假设节点没有父指针，我们需要为迭代变体管理我们自己的“堆栈”。
开始的一种方法是查看递归方法并标记调用将“恢复”的位置（新的初始调用，或递归调用返回之后）。下面这些标记为“RP 0”、“RP 1”等（“恢复点”）。对于后序遍历的情况：
void post(node *x)
{
/* RP 0 */
if(x->lc) post(x->lc);
/* RP 1 */
if(x->rc) post(x->rc);
/* RP 2 */
process(x);
}
它的迭代变体：
void post_i(node *root)
{
node *stack[1000];
int top;
node *popped;
stack[0] = root;
top = 0;
popped = NULL;
#define POPPED_A_CHILD() \
(popped && (popped == curr->lc || popped == curr->rc))
while(top >= 0)
{
node *curr = stack[top];
if(!POPPED_A_CHILD())
{
/* type (x: 0) */
if(curr->rc || curr->lc)
{
if(curr->rc) stack[++top] = curr->rc;
if(curr->lc) stack[++top] = curr->lc;
popped = NULL;
continue;
}
}
/* type (x: 2) */
process(curr);
top--;
popped = curr;
}
}
代码注释与(x: 0)递归(x: 2)方法中的“RP 0”和“RP 2”恢复点相对应。
通过将lc和rc指针放在一起，我们不再需要在完成执行post(x)时将调用保持在恢复点 1 。post(x->lc)也就是说，我们可以直接将节点转移到“RP 2”，绕过“RP 1”。因此，在“RP 1”阶段没有节点保留在堆栈中。
该POPPED_A_CHILD宏帮助我们推断出两个恢复点之一（“RP 0”或“RP 2”）。
于 2021-01-13T17:17:37.937 回答