二叉树遍历（Java实现）

二叉树遍历（Java实现） 

 

主要是二叉树的遍历，包括递归遍历和非递归遍历

1. import java.util.ArrayDeque;  
2. import java.util.ArrayList;  
3. import java.util.List;  
4. import java.util.Queue;  
5.   
6. public class BinaryNode<T> {  
7.     /**  
8.      * 泛型BinaryNode类  
9.      */  
10.     public T item;  
11.       
12.     public BinaryNode<T> left,right;//左右子树  
13.       
14.     public BinaryNode(T item)  
15.     {  
16.         this.item = item;  
17.         left = right = null;  
18.     }     
19.     public BinaryNode (T item, BinaryNode<T> left, BinaryNode<T> right)  
20.     {  
21.         this.item = item;  
22.         this.left = left;  
23.         this.right = right;  
24.     }  
25.   
26.     public T getNodeValue() {  
27.         return item;  
28.     }  
29.     public void setNodeValue(T item) {  
30.         this.item = item;  
31.     }  
32.     public BinaryNode<T> getLeft() {  
33.         return left;  
34.     }  
35.     public void setLeft(BinaryNode<T> left) {  
36.         this.left = left;  
37.     }  
38.     public BinaryNode<T> getRight() {  
39.         return right;  
40.     }  
41.     public void setRight(BinaryNode<T> right) {  
42.         this.right = right;  
43.     }  
44.       
45.     //判断是否为叶子  
46.     public boolean isLeaf(){  
47.         return (left==null)&&(right==null);  
48.     }  
49.       
50.     //前序遍历二叉树(递归)  
51.     public List<BinaryNode<T>> toStringPreorder(BinaryNode<T> node){  
52.         List<BinaryNode<T>> list=new ArrayList<BinaryNode<T>>();  
53.         list.add(node);  
54.         if (node.left!=null) {  
55.             list.addAll(toStringPreorder(node.left));  
56.         }  
57.         if (node.right!=null) {  
58.             list.addAll(toStringPreorder(node.right));  
59.         }  
60.         return list;  
61.     }  
62.     //前序遍历二叉树(非递归)  
63.     public List<BinaryNode<T>> toStringPreorderNoRec(BinaryNode<T> node){  
64.         List<BinaryNode<T>> list=new ArrayList<BinaryNode<T>>();  
65.         ArrayDeque<BinaryNode<T>> stack=new ArrayDeque<BinaryNode<T>>();  
66.         while ((node!=null)||!stack.isEmpty()) {  
67.             if (node!=null) {  
68.                 list.add(node);  
69.                 stack.push(node);  
70.                 node=node.left;  
71.             } else {  
72.                 node=stack.peek();            
73.                 stack.pop();  
74.                 node=node.right;  
75.             }  
76.         }         
77.         return list;  
78.     }  
79.       
80.     //中序遍历二叉树  
81.     public List<BinaryNode<T>> toStringInorder(BinaryNode<T> node){  
82.         List<BinaryNode<T>> list=new ArrayList<BinaryNode<T>>();  
83.         if (node.left!=null) {  
84.             list.addAll(toStringPreorder(node.left));  
85.         }  
86.         list.add(node);  
87.         if (node.right!=null) {  
88.             list.addAll(toStringPreorder(node.right));  
89.         }  
90.         return list;  
91.     }  
92.     //中序遍历二叉树(非递归)  
93.     public List<BinaryNode<T>> toStringInorderNoRec(BinaryNode<T> node){  
94.         List<BinaryNode<T>> list=new ArrayList<BinaryNode<T>>();  
95.         ArrayDeque<BinaryNode<T>> stack=new ArrayDeque<BinaryNode<T>>();  
96.         while ((node!=null)||!stack.isEmpty()) {  
97.             if (node!=null) {                 
98.                 stack.push(node);  
99.                 node=node.left;  
100.             } else {  
101.                 node=stack.peek();  
102.                 list.add(node);  
103.                 stack.pop();  
104.                 node=node.right;  
105.             }  
106.         }         
107.         return list;  
108.     }  
109.       
110.     //后序遍历二叉树  
111.     public String toStringPostorder(){  
112.         String result="";  
113.         if (left!=null) {  
114.             result += left.toStringPostorder();  
115.         }         
116.         if (right!=null) {  
117.             result += right.toStringPostorder();  
118.         }  
119.         result += item;  
120.         return result;  
121.     }  
122.     //后序遍历二叉树(非递归)  
123.     /**  
124.      * 先遍历树的逆后序遍历(根、右、左),在翻转逆后序遍历就是后序遍历二叉树(左、右、根)  
125.      * @return result栈  
126.      */  
127.     public ArrayDeque<BinaryNode<T>> toStringPostorderNoRec(BinaryNode<T> node){  
128.         ArrayDeque<BinaryNode<T>> stack=new ArrayDeque<BinaryNode<T>>();  
129.         ArrayDeque<BinaryNode<T>> result=new ArrayDeque<BinaryNode<T>>();  
130.         while ((node!=null)||!stack.isEmpty()) {  
131.             if (node!=null) {  
132.                 result.push(node);  
133.                 stack.push(node);  
134.                 node=node.right;  
135.             } else {  
136.                 node=stack.peek();  
137.                 stack.pop();  
138.                 node=node.left;  
139.             }  
140.         }         
141.         return result;  
142.     }  
143.     //后序遍历二叉树2(非递归)  
144.     /**  
145.      * 要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；  
146.      * 或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，  
147.      * 则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。  
148.      * @return result栈  
149.      */  
150.     public ArrayList<BinaryNode<T>> toStringPostorderNoRec2(BinaryNode<T> root){  
151.         ArrayDeque<BinaryNode<T>> stack=new ArrayDeque<BinaryNode<T>>();  
152.         ArrayList<BinaryNode<T>> result=new ArrayList<BinaryNode<T>>();  
153.         BinaryNode<T> curr;//当前栈顶指针  
154.         BinaryNode<T> pre=null;//前一次访问节点  
155.         stack.push(root);  
156.         while (!stack.isEmpty()) {  
157.             curr=stack.peek();  
158.             if ((curr.left==null&&curr.right==null)||(pre!=null&&(pre==curr.left||pre==curr.right))) {  
159.                 result.add(curr);//输出结果  
160.                 stack.pop();  
161.                 pre=curr;  
162.             } else {  
163.                 if (curr.right!=null) {  
164.                     stack.push(curr.right);  
165.                 }   
166.                 if (curr.left!=null) {  
167.                     stack.push(curr.left);  
168.                 }  
169.             }  
170.         }         
171.         return result;  
172.     }  
173.       
174.     //层序遍历(广度优先遍历)  
175.     public List<BinaryNode<T>> toStringLevelOrder(){  
176.         List<BinaryNode<T>> list=new ArrayList<BinaryNode<T>>();  
177.         Queue<BinaryNode<T>> queue=new ArrayDeque<BinaryNode<T>>();  
178.         queue.offer(this);//root  
179.         while (!(queue.isEmpty())) {  
180.             list.add(queue.peek());  
181.             BinaryNode<T> node=queue.poll();            
182.             if (node.left != null) {  
183.                 queue.offer(node.left);  
184.             }  
185.             if (node.right != null) {  
186.                 queue.offer(node.right);  
187.             }  
188.         }  
189.         return list;  
190.     }  
191.       
192. }