数据结构之二叉树篇卷三 -- 二叉树非递归遍历（With Java)

Nonrecursive Traversal of Binary Tree

First I wanna talk about why should we use <code>Stack</code> to implement this algorithm. I think it is due to the FILO feature of Stack, and that really matters and makes sense when you get around with tree stuff. Cause in nonrecursive way we have to remember where we came from, which means we must figure out how should we go back to the root node as we finish visiting the whole subtree. The key to understand and get good command of nonrecursive traversal of binary tree is to demostrate the whole process by your hand. Don't be lazy. :)

I. Preorder Nonrecursive Traversal

1.1 Algorithm

In recursive way it is easy and simple to go back to the root when we finish handling or visiting the subtree. But it seems more tricky while you're using nonrecursive way, which means you need to find some auxiliary data structure to help you implement those algorithm. So there we go.

In preorder way of traversing binary tree, we should visit the root first, then go to visit left subtree and visit the right subtree at last. So the most important thing is to bear the visiting order in mind.

• a. visit the node and push it into stack as you go down along the left subtree untill it reaches the deepest bottom left node. 
• b. pop a node from the top of stack and check whether it owns a right node, and go right if does.
• c. loop a ~ b until the stack is empty

Noticing that when to visit the node may help you interpret this algorithm better.

1.2 Code

Talk is cheap, show me the code!    -- Linus Benedict Torvalds

 1 public class Node<E> {
 2     public E data;
 3     public Node<E> lnode;
 4     public Node<E> rnode;
 5 
 6     public Node(){}
 7     public Node(E data) {
 8         this.data = data;
 9     }
10 }

 1     /**
 2      * preorder nonrecursive traversal with stack
 3      * @param node
 4      * @author sheepcore
 5      */
 6     public void preOrderStk(Node<E> node) {
 7         if(node == null)
 8             return;
 9         Node<E> root = node;
10         Stack<Node<E>> stack = new Stack<>();
11         while (root != null || !stack.isEmpty()){
12             while (root != null){
13                 visit(root);    //visit the root node first then go to left subtree
14                 stack.push(root);   //push left node into stack to go back
15                 root = root.lnode;
16             }
17             if(!stack.isEmpty()){
18                 root = stack.pop();
19                 if(root.rnode != null) {
20                     root = root.rnode;  //visit the right subtree
21                 } else {
22                     root = null;    //clear root when it is return from right subtree
23                 }
24             }
25         }
26     }

II. Inorder Nonrecursive Traversal

2.1 Algorithm

• a. push the node into stack as you go down along the left subtree untill it reaches the deepest bottom left node. 
• b. pop a node from the top of stack and visit it. Then check whether it owns a right node, go right if does.
• c. loop a ~ b until the stack is empty

2.2 Code

 1     /**
 2      * inorder non recursive traversal with stack
 3      * @param node
 4      * @author sheepcore
 5      */
 6     public void inOrderStk(Node<E> node) {
 7         if(node == null)
 8             return;
 9         Node<E> root = node;
10         Stack<Node<E>> stack = new Stack<>();
11         while (root != null || !stack.isEmpty()){
12             while (root != null){
13                 stack.push(root);   //go the left bottom of the tree
14                 root = root.lnode;
15             }
16             if(!stack.isEmpty()){
17                 root = stack.pop();
18                 visit(root);        //visit it
19                 if(root.rnode != null) {
20                     root = root.rnode;
21                 } else {
22                     root = null;    //clear root when it is return from right subtree
23                 }
24             }
25         }
26     }

III. Postorder Nonrecursive Traversal

3.1 Algorithm

It is more tricky and tougher while traversing in postorder way than in preorder or inorder way. Cause we have no idea where it comes from when we go back to the root node. Therefore we got two common solutions: using tags or using two stacks.

Using tags for each node can help us find out whether it comes from left subtree or right. Tag the node as "LEFT" while visiting the left subtree and change it to "RIGHT" as we finish. Then go right and go back the root and visit it.

Using two stacks is prolly like this https://www.geeksforgeeks.org/iterative-postorder-traversal/ and check it out :).

3.2 Code

1.Using tags

 1     /**
 2      * postorder nonrecursive traversal of binary tree
 3   
 4      * The key to understand and get good command of this algorithm is to demonstrate the whole processes
 5      * of each step and figure out how the nodes' status changed and for what that will make sense
 6      * to you to permanently beat the algorithm. And you must know that each nodes should be pushed into
 7      * stack twice which seems to be sort of time-consuming, so we can also check whether the nodes has
 8      * right node when we go down alongside the left subtree and that could make the performance better. :)
 9      * @param node
10      * @author sheepcore
11      */
12     public void postOrderStk(Node<E> node){
13         if(root == null)
14             return;
15         Node<E> root = node;
16         stkNode<E> s;
17         Stack<stkNode<E>> stack = new Stack<>();
18         do {
19             while (root != null){       //go down along the left branches of the bitree
20                 s = new stkNode<>();
21                 s.node = root;
22                 s.tag = tag.L;
23                 stack.push(s);
24                 root = root.lnode;
25             }//while-root
26             boolean continual = true;   //flag for continue
27             while (continual && !stack.isEmpty()) {
28                 s = stack.pop();
29                 root = s.node;
30                 switch (s.tag){
31                     case L: s.tag = tag.R;      //return from left subtree
32                             stack.push(s);
33                             continual = false;
34                             root = root.rnode;
35                             break;
36                     case R: visit(root); break;  //return from right subtree
37                 }
38             }//while-continual-stack
39         }while (!stack.isEmpty());
40     }

　　2.Using two stacks

 1     /**
 2      * post-order nonrecursive traversal with two stacks
 3      * @param node
 4      */
 5     public void postOrderStk2(Node<E> node){
 6         if(root == null)
 7             return;
 8         Node<E> root = node;
 9         Stack<Node<E>> s1 = new Stack<>();
10         Stack<Node<E>> s2 = new Stack<>();
11         s1.push(root);
12         while (!s1.isEmpty()){
13             root = s1.pop();
14             s2.push(root);
15             if (root.lnode != null) { s1.push(root.lnode); }
16             if (root.rnode != null) { s1.push(root.rnode); }
17         }
18         while (!s2.isEmpty()){
19             visit(s2.pop());
20         }
21         System.out.println();
22     }

IV. Levelorder Nonrecursive Traversal

4.1 Algorithm

In levelorder you need to visit the nodes from left to right and from top to bottom of the tree. Using a queue to implement the algorithm is way more simple as you think.

4.2 Code

 1    /**
 2      * level order traversal using queue
 3      * 1. check and visit the root node remove from the queue
 4      * 2. add its left and right nodes if does
 5      * 3. loop 1 ~ 2 while queue is empty
 6      * @param root
 7      * @author sheepcore
 8      */
 9     public void levelOrder(Node<E> root){
10         if(root == null)
11             return;
12         LinkedList<Node<E>> q = new LinkedList<>();
13         Node<E> cur;
14         q.addLast(root);
15         while (!q.isEmpty()) {
16             cur = q.removeFirst();
17             visit(cur);
18             if(cur.lnode != null) {
19                 q.addLast(cur.lnode);
20             }
21             if(cur.rnode != null){
22                 q.addLast(cur.rnode);
23             }
24         }
25     }

V. Summary

哈哈，自己的第一篇全英文博客，最近因为考试在练英文写作，所以干脆就趁热打铁一下。总结一下，这四种二叉树遍历的非递归方法其实总体逻辑不算难，需要自己多在纸上演算推导，感受推导逻辑之后，才能把它转化为代码逻辑，这样写出的代码会更加印象深刻的。其中后序非递归遍历稍微麻烦一点，需要考虑当回溯到根节点时，是从左子树来的呢？还是从右子树呢？因为这两种情况对根节点将执行不同的操作，所以需要特别处理。其实方法还有很多，这里自己只是简单实现了两种最常见的方法：标志位法和双堆栈法。好啦！我得滚去学习了，因为落后就要挨打了！！！

Sometimes people call you an idiot when you do something stupid, keep doing that until you change that stupid things to glory things. And then you can stare at those people's eyes and say, "I made it bitch!".