数据结构

今天复习到数据结构中的二叉树，就把二叉树的遍历（非递归） 实现了一下，感觉记录下来还是很必要的，希望每天能进步一点点。  

二叉树遍历：  

前序遍历：根左右（栈实现）；

中序遍历：左根右（栈实现）；

后序遍历：左右根（栈实现）；

层次遍历：从上往下遍历（队列实现）；

首先，先定义一个二叉树。

[java] view plain copy

1. //树节点  
2. public class BinaryTreeNode {  
3.     private int  element;  
4.     private BinaryTreeNode left;  
5.     private BinaryTreeNode right;  
6.       
7.     public BinaryTreeNode(int element) {  
8.         //super();  
9.         this.element = element;  
10.     }  
11.       
12.     public BinaryTreeNode(int element, BinaryTreeNode left, BinaryTreeNode right) {  
13.         //super();  
14.         this.element = element;  
15.         this.left = left;  
16.         this.right = right;  
17.     }  
18.       
19.     public int getElement() {  
20.         return element;  
21.     }  
22.       
23.     public void setElement(int element) {  
24.         this.element = element;  
25.     }  
26.       
27.     public BinaryTreeNode getLeft() {  
28.         return left;  
29.     }  
30.       
31.     public void setLeft(BinaryTreeNode left) {  
32.         this.left = left;  
33.     }  
34.       
35.     public BinaryTreeNode getRight() {  
36.         return right;  
37.     }  
38.       
39.     public void setRight(BinaryTreeNode right) {  
40.         this.right = right;  
41.     }  
42.       
43.       
44.       
45.       
46. }  

以下分别介绍介绍二叉树的四种遍历方法

1.前序遍历

[java] view plain copy

1. public static void preOrder(BinaryTreeNode bt){  
2.     Stack<BinaryTreeNode> stack=new Stack<BinaryTreeNode>();  
3.     if(bt!=null){  
4.         stack.push(bt);  
5.         while(!stack.empty()){  
6.             BinaryTreeNode t=stack.pop();  
7.             System.out.print(t.getElement()+",");  
8.             if(t.getRight()!=null)  
9.             {     
10.                 stack.push(t.getRight());  
11.             }  
12.             if(t.getLeft()!=null){  
13.                       
14.                 stack.push(t.getLeft());  
15.             }  
16.         }  
17.     }     
18.       
19. }  

2.中序遍历

[java] view plain copy

1. public static void InOrder(BinaryTreeNode bt){  
2.     Stack<BinaryTreeNode> stack=new Stack<BinaryTreeNode>();  
3.     BinaryTreeNode cur=bt;  
4.     while(cur!=null||stack.size()>0){  
5.         while(cur!=null){  
6.             stack.push(cur);  
7.             cur=cur.getLeft();  
8.         }  
9.               
10.         if(stack.size()>0){  
11.             cur=stack.pop();  
12.             System.out.print(cur.getElement()+" ");  
13.             cur=cur.getRight();  
14.               
15.                   
16.         }  
17.     }  
18.           
19.           
20. }  

3.后续遍历

[java] view plain copy

1. public static void postOrder(BinaryTreeNode bt){  
2.     Stack<BinaryTreeNode> stack=new Stack<>();  
3.     BinaryTreeNode t=bt;  
4.     BinaryTreeNode prev=bt;  
5.     while(t!=null||stack.size()>0){  
6.         while(t!=null){  
7.             stack.push(t);  
8.             t=t.getLeft();  
9.         }  
10.               
11.               
12.         if(stack.size()>0){  
13.             BinaryTreeNode temp=stack.peek().getRight();  
14.             if(temp==null||temp==prev){  
15.                 t=stack.pop();  
16.                 System.out.print(t.getElement()+" ");  
17.                 prev=t;  
18.                 t=null;  
19.             }  
20.             else{  
21.                 t=temp;  
22.             }  
23.         }  
24.     }  
25. }  
26.       

4.层次遍历

[java] view plain copy

1. public static void levelOrder(BinaryTreeNode bt){  
2.     Queue<BinaryTreeNode> queue=new LinkedList<BinaryTreeNode>();  
3.     BinaryTreeNode t=bt;  
4.     if(t!=null)  
5.         queue.offer(t);  
6.     while(queue.size()>0){  
7.         BinaryTreeNode s=queue.poll();  
8.         System.out.print(s.getElement()+" ");  
9.         if(s.getLeft()!=null)  
10.             queue.offer(s.getLeft());  
11.         if(s.getRight()!=null)  
12.             queue.offer(s.getRight());  
13.     }  
14. }