递归 非递归 遍历二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
package tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class BinTree {
	
	public int[] array = {1,2,3,4,5,6,7,8,9};
	public List<Node> nodelist = null;
	
	public  class Node {
		Node leftChild;
		Node rightChild;
		int data;
		
		Node(int data) {
			this.data = data;
			this.leftChild = null;
			this.rightChild = null;
		}
	}
	
	public void createBinTree() {
		nodelist = new ArrayList<Node>();
		for(int index=0; index<array.length; index++) {
			nodelist.add(new Node(array[index]));
		}
		
		//此数组长度为9,父节点有(9/2-1=3)个。先对前n-1个父节点建立子节点
		for(int parentIndex=0; parentIndex<array.length/2 - 1; parentIndex++) {
			nodelist.get(parentIndex).leftChild = nodelist.get(parentIndex*2 + 1);
			nodelist.get(parentIndex).rightChild = nodelist.get(parentIndex*2 + 2);
		}
		//最后一个父节点有可能没有右孩子。只有数组长度为奇数的时候才有右孩子
		int lastParent = array.length / 2 - 1;
		nodelist.get(lastParent).leftChild = nodelist.get(lastParent*2 + 1);
		if(array.length % 2 == 1) {
			nodelist.get(lastParent).rightChild = nodelist.get(lastParent*2 + 2);
		}
	}
	
	public void preOrderTraverse(Node node) {
		if(node == null) {
			return;
		}
		System.out.print(node.data + " ");
		preOrderTraverse(node.leftChild);
		preOrderTraverse(node.rightChild);
	}
	
	public void inOrderTraverse(Node node) {
		if(node == null) {
			return;
		}
		inOrderTraverse(node.leftChild);
		System.out.print(node.data + " ");
		inOrderTraverse(node.rightChild);
	}
	
	public void lastOrderTraverse(Node node) {
		if (node == null) {
			return;
		}
		lastOrderTraverse(node.leftChild);
		lastOrderTraverse(node.rightChild);
		System.out.print(node.data + " ");
		
	}
	
	public void norecursivePre(Node node) {
		/*
		 * 用栈模拟递归的方式
		 */
		Stack<Node> stack = new Stack<Node>();
		if(node != null) {
			stack.push(node);
			while(!stack.empty()) {
				node = stack.pop();
				System.out.print(node.data + " ");
				if (node.rightChild != null) {
					stack.push(node.rightChild);
				}
				if(node.leftChild != null) {
					stack.push(node.leftChild);
				}
			}
		}
	}
	
	public void norecursiveIn(Node node) {
		if (node == null) {
			return;
		}
		Stack<Node> stack = new Stack<Node>();
		stack.push(node);
		
		while(!stack.isEmpty()) {
			while(stack.peek() != null) {
				stack.push(stack.peek().leftChild);
			}
			Node p = stack.pop();
			
			if(!stack.isEmpty()) {
				System.out.print(stack.peek().data + " ");
				p = stack.pop();
				stack.push(p.rightChild);
			}
		}
	}
	

	public static void main(String[] args) {
		BinTree tree = new BinTree();
		tree.createBinTree();
		Node root = tree.nodelist.get(0);
		
		tree.preOrderTraverse(root);
		System.out.println();
		tree.norecursivePre(root);
		System.out.println();
		
		System.out.println();
		tree.inOrderTraverse(root);
		System.out.println();
		tree.norecursiveIn(root);
		System.out.println();
		
		System.out.println();
		tree.lastOrderTraverse(root);
		
	}
}

1
2
3
4
5
6
7
8
1 2 4 8 9 5 3 6 7 
1 2 4 8 9 5 3 6 7 

8 4 9 2 5 1 6 3 7 
8 4 9 2 5 1 6 3 7 

8 9 4 5 2 6 7 3 1