无recursion二叉树的后序遍历

没有使用recursion做二叉树的后序遍历的algorithm是什么？

Answer 1

这里有一个链接提供了另外两个解决scheme，而不使用任何访问标志。

http://www.leetcode.com/2010/10/binary-tree-post-order-traversal.html

这显然是基于堆栈的解决scheme，因为树中缺less父指针。 （如果有父指针，我们不需要堆栈）。

我们首先将根节点推入堆栈。 虽然堆栈不是空的，但我们继续从栈顶推动节点的左侧子节点。 如果左边的孩子不存在，我们推它的右边的孩子。 如果是叶节点，我们处理该节点并将其从堆栈中popup。

我们还使用一个variables来跟踪以前遍历的节点。 目的是确定遍历是否正在升/降树，我们也可以知道它是否从左/右上升。

如果我们从左边上升树，我们不想再把左边的孩子推到堆栈上，如果它的右边的孩子存在，我们应该继续爬下树。 如果我们从右侧上升树，我们应该处理它，并从堆栈中popup。

在这三种情况下，我们将处理节点并将其从堆栈中popup：

1. 该节点是一个叶节点（没有孩子）
2. 我们只是从左边往上走，没有右边的小孩。
3. 我们只是从右边往上走。

Answer 2

这是一个堆栈，没有访问标志的版本：

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); } } } } 

Answer 3

以下是维基百科的一个示例：

 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() 

Answer 4

 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); } } 

Answer 5

/ /标志的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); } } } 

Answer 6

这里是C ++中的一个解决scheme，它不需要任何存储在树中的logging。
相反，它使用两个堆栈。 一个帮助我们遍历，另一个存储节点，所以我们可以对它们进行遍历。

 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"; } 

Answer 7

这是我用于迭代，后序遍历的方法。 我喜欢这种方法，因为：

1. 它只处理每个循环的单个转换，所以很容易遵循。
2. 类似的解决scheme适用于有序和预定义遍历

码：

 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(); } } } 

说明：

你可以考虑这样的步骤：

1. 尝试左
   • 如果左节点存在：再次尝试LEFT
   • 如果左节点不存在：请尝试右键
2. 尝试正确的
   • 如果存在正确的节点：从那里尝试左
   • 如果没有权利存在，你在叶：尝试CURR
3. 试试CURR
   • 打印当前节点
   • 下面的所有节点都已经被执行（后期）：试用
4. 试试吧
   • 如果节点是root，那么没有UP，所以EXIT
   • 如果从左边出来，试试右边
   • 如果从右侧出现，请尝试CURR

Answer 8

 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; } } 

Answer 9

在这里，我粘贴不同版本的c＃（.net）作为参考:(对于按顺序迭代遍历，你可以参考： 帮助我理解不使用recursion遍历 ）

1. wiki（ http://en.wikipedia.org/wiki/Post-order%5Ftraversal#Implementations ）（优雅）
2. 单一堆栈的另一个版本（＃1和＃2：基本上使用的事实是，在后序遍历中，在访问实际节点之前访问正确的子节点 – 所以，我们简单地依靠检查，如果堆栈顶部的右孩子确实是最后发布的命令遍历节点已被访问 – 我已经在下面的代码片段添加注释的细节）
3. 使用两个堆栈版本（参考： http ： //www.geeksforgeeks.org/iterative-postorder-traversal/ ）（更简单：基本上是顺序遍历逆向只不过是预览遍历与一个简单的调整，右节点首先访问，然后左节点）
4. 使用访客标志（简单）
5. unit testing

〜

 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)) { //ie 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 //(ie; 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) && //ie 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. ie 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; } 

unit testing

 [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())); } 

Answer 10

与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 

Answer 11

我没有添加节点类作为它不是特别相关的或任何testing用例，留给那些作为读者的练习。

 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） – 对于堆栈，最坏情况树是单行链表

Answer 12

看到这个问题有如此多的热情的方法是非常好的。 确实鼓舞人心！

我碰到这个话题，寻找一个简单的迭代解决scheme，删除我的二叉树实现中的所有节点。 我尝试了其中的一些，我尝试了类似在网上其他地方find的东西，但没有一个真正符合我的喜好。

事情是，我正在开发一个数据库索引模块，用于特定目的（比特币区块链索引），我的数据存储在磁盘上，而不是RAM中。 我根据需要交换页面，做我自己的内存pipe理。 速度较慢，但​​是速度足够快，而且在磁盘上而不是内存上存储，我没有对浪费空间的任何宗教信仰（硬盘很便宜）。

出于这个原因，我的二叉树中的节点有父指针。 这就是我所谈论的额外空间。 我需要父母，因为我需要为了各种目的迭代树中的升序和降序。

在我脑海中，我迅速地写下了一小段关于如何完成的伪代码，也就是一个后台遍历删除节点。 这是实施和testing，并成为我的解决scheme的一部分。 而且速度也非常快。

事情是：当节点有父指针时，真的很简单，而且因为我可以将父节点的链接清空到“刚刚离开”节点。

这里是迭代后序删除的伪代码：

 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, ie 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/

Answer 13

深度第一，邮政顺序，非recursion，没有堆栈

当你有父母：

  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 

Answer 14

1.1创build一个空的堆栈

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从堆栈中popup一个项目并将其设置为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。

Answer 15

这是两个堆栈的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; } 

这里是unit testing

 @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})); } 

Answer 16

 /** * 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(); } } 

Answer 17

 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; } 

Answer 18

  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(); } } } 

Answer 19

请看这个完整的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(); } }