二叉树遍历算法总结

发表于   |   分类于   |     |   阅读次数

树

二叉树是一个非常重要的数据结构，其他的AVL，红黑树等都是基于此演变而来。对二叉树的常用的遍历方法有：前序、中序、后续和层序遍历。对于前三者，我们可以用递归来实现，简单又清晰，也可以用非递归，即用栈容器来模拟递归算法。本来递归的本质就是进栈出栈。而层序不同的地方在于它不是递归地执行的；它用到队列，而不使用递归所默认的栈。

二叉树结点类

实现几个构造方法，便于创建结点

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
/**
 * 二叉树结点定义
 * @author henry
 *
 */
public class TreeNode<T> {
	T data;
	TreeNode<T> left;
	TreeNode<T> right;
	
	public TreeNode(T data,TreeNode<T> left,TreeNode<T> right){
		this.data=data;
		this.left=left;
		this.right=right;
	}
	
	public TreeNode(T data){
		this.data=data;
		this.left=null;
		this.right=null;
	}
	
	public TreeNode(){
		this(null,null,null);
	}
	@Override
	public String toString(){
		return data.toString();
	}
}

前序遍历

递归实现

1
2
3
4
5
6
7
public <T> void recursivePreorder(TreeNode<T> root){
	if(root==null)
		return ;
	System.out.print(root.data.toString()+",");
	recursivePreorder(root.left);
	recursivePreorder(root.right);
}

非递归实现

根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。即对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子不为空，按相同规则访问它的左子树；当访问其左子树时，再访问它的右子树。因此其处理过程如下：
对于任意结点P：

  1. 访问结点P，并将结点P入栈;
  2. 判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1);若不为空，则将P的左孩子置为当前的结点P;
  3. 直到P为NULL并且栈为空，则遍历结束。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
   public <T> void preorder(TreeNode<T> root){
	Deque<TreeNode<T>> stack=new LinkedList<TreeNode<T>>();//模拟栈
	TreeNode<T> p=root;
	while(p!=null||!stack.isEmpty()){
		while(p!=null){
			System.out.print(p.data.toString()+",");
			stack.push(p);//左子树入栈
			p=p.left;
		}
		if(!stack.isEmpty()){
			p=stack.peek();
			stack.pop();
			p=p.right;
		}
	}
}

中序遍历

递归实现

1
2
3
4
5
6
7
public <T> void recursiveInorder(TreeNode<T> root){
	if(root==null)
		return ;
	recursiveInorder(root.left);
	System.out.print(root.data.toString()+",");
	recursiveInorder(root.right);
}

非递归实现

根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才进行访问，然后按相同的规则访问其右子树。因此其处理过程如下：
对于任一结点P：

  1. 若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；
  2. 若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；
  3. 直到P为NULL并且栈为空则遍历结束
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public <T> void inorder(TreeNode<T> root){
	Deque<TreeNode<T>> stack=new LinkedList<TreeNode<T>>();//栈存放结点
	TreeNode<T> p=root;
	while(p!=null||!stack.isEmpty()){
		while(p!=null){//一直找左边，并压入堆栈，直到左叶子
			stack.push(p);
			p=p.left;//
		}
		if(!stack.isEmpty()){
			p=stack.peek();
			System.out.print(p.data.toString()+",");
			stack.pop();
			p=p.right;
		}
	}
}

后续遍历

递归实现

1
2
3
4
5
6
7
   public <T> void recursivePostorder(TreeNode<T> root){
	if(root==null)
		return ;
	recursivePostorder(root.left);
	recursivePostorder(root.right);
	System.out.print(root.data.toString()+",");
}

非递归实现

后续遍历的非递归比较难，因为在后序遍历中，要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，这就为流程的控制带来了难题。
思路：要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
   public <T> void postorder(TreeNode<T> root){
	Deque<TreeNode<T>> stack=new LinkedList<TreeNode<T>>();
	TreeNode<T> p;
	TreeNode<T> pre=null;//前一次访问结点
	stack.push(root);//
	while(!stack.isEmpty()){
		p=stack.peek();
		//如果当前结点没有孩子结点，或者孩子结点都已经被访问过
		if((p.left==null&&p.right==null)||(pre!=null&&(pre==p.left||pre==p.right))){
			System.out.print(p.data.toString()+",");
			stack.pop();
			pre=p;
		}
		else{
			if(p.right!=null)
				stack.push(p.right);
			if(p.left!=null)
				stack.push(p.left);
		}
	}
}

后续遍历典型应用——树的高度

有时候我们需要先处理两个子树然后才能处理当前结点。例如，为了计算一个结点的高度，首先需要知道它的子树的高度。声明树叶的高度为零。

1
2
3
4
5
6
public <T> int height(TreeNode<T> root){
	if(root==null)
		return -1;
	else
		return 1+Math.max(height(root.left),height(root.right));
}

完整测试

测试结果

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
package algorithm;
/**
 * 二叉树遍历算法总结
 */
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class TraverseBinaryTree {
	public static void main(String[] args) {
		TraverseBinaryTree obj=new TraverseBinaryTree();
		TreeNode<String> root= obj.create();
		//前序遍历两种
		System.out.println("前序遍历——递归");
		long start=System.nanoTime();
		obj.recursivePreorder(root);
		long end=System.nanoTime();
		System.out.print("耗时：");
		System.out.println(end-start);
		
		System.out.println("前序遍历——非递归");
		start=System.nanoTime();
		obj.preorder(root);
		end=System.nanoTime();
		System.out.print("耗时：");
		System.out.println(end-start);
		//中序遍历两种
		System.out.println("中序遍历——递归");
		start=System.nanoTime();
		obj.recursiveInorder(root);
		end=System.nanoTime();
		System.out.print("耗时：");	
		System.out.println(end-start);
		
		System.out.println("中序遍历——非递归");
		start=System.nanoTime();
		obj.inorder(root);
		end=System.nanoTime();
		System.out.print("耗时：");
		System.out.println(end-start);
		
		//后续遍历
		System.out.println("后续遍历——递归");
		start=System.nanoTime();
		obj.recursivePostorder(root);
		end=System.nanoTime();
		System.out.print("耗时：");
		System.out.println(end-start);
		
		System.out.println("后续遍历——非递归");
		start=System.nanoTime();
		obj.postorder(root);
		end=System.nanoTime();
		System.out.print("耗时：");
		System.out.println(end-start);
		
		//层序遍历
		System.out.println("层序遍历");
		start=System.nanoTime();
		obj.Layerorder(root);
		end=System.nanoTime();
		System.out.print("耗时：");
		System.out.println(end-start);
		
		//树的高度
		System.out.println("该二叉树的高度="+obj.height(root));
	}
	
	
	/**
	 * 创建一个二叉树,形如
	 * 				A
	 * 			   / \
	 * 			  B	  D
	 * 			 /   / \
	 * 			C   E   F
	 * @return
	 */
	public TreeNode<String> create(){
		TreeNode<String> root=new TreeNode<String>("A");
		TreeNode<String> child_c=new TreeNode<String>("C");
		TreeNode<String> child_e=new TreeNode<String>("E");
		TreeNode<String> child_f=new TreeNode<String>("F");
		TreeNode<String> child_b=new TreeNode<String>("B",child_c,null);
		TreeNode<String> child_d=new TreeNode<String>("D",child_e,child_f);
		root.left=child_b;
		root.right=child_d;
		return root;
	}
	/**
	 * 前序遍历——递归
	 * @param root
	 */
	public <T> void recursivePreorder(TreeNode<T> root){
		if(root==null)
			return ;
		System.out.print(root.data.toString()+",");
		recursivePreorder(root.left);
		recursivePreorder(root.right);
	}
	
	/**
	 * 前序遍历——非递归
	 * 用一个堆栈来存储结点
	 * @param root
	 */
	public <T> void preorder(TreeNode<T> root){
		Deque<TreeNode<T>> stack=new LinkedList<TreeNode<T>>();//模拟栈
		TreeNode<T> p=root;
		while(p!=null||!stack.isEmpty()){
			while(p!=null){
				System.out.print(p.data.toString()+",");
				stack.push(p);//左子树入栈
				p=p.left;
			}
			if(!stack.isEmpty()){
				p=stack.peek();
				stack.pop();
				p=p.right;
			}
		}
	}
	
	/**
	 * 中序遍历——递归
	 * @param root
	 */
	public <T> void recursiveInorder(TreeNode<T> root){
		if(root==null)
			return ;
		recursiveInorder(root.left);
		System.out.print(root.data.toString()+",");
		recursiveInorder(root.right);
	}
	
	/**
	 * 中序遍历——非递归
	 * @param root
	 */
	public <T> void inorder(TreeNode<T> root){
		Deque<TreeNode<T>> stack=new LinkedList<TreeNode<T>>();//栈存放结点
		TreeNode<T> p=root;
		while(p!=null||!stack.isEmpty()){
			while(p!=null){//一直找左边，并压入堆栈，直到左叶子
				stack.push(p);
				p=p.left;//
			}
			if(!stack.isEmpty()){
				p=stack.peek();
				System.out.print(p.data.toString()+",");
				stack.pop();
				p=p.right;
			}
		}
	}
	
	/**
	 * 后续遍历——递归
	 * @param root
	 */
	public <T> void recursivePostorder(TreeNode<T> root){
		if(root==null)
			return ;
		recursivePostorder(root.left);
		recursivePostorder(root.right);
		System.out.print(root.data.toString()+",");
	}
	
	/**
	 * 后续遍历——非递归
	 * 这个较前两者难一些
	 * @param root
	 */
	public <T> void postorder(TreeNode<T> root){
		Deque<TreeNode<T>> stack=new LinkedList<TreeNode<T>>();
		if(root==null)//非空判定
			return;
		TreeNode<T> p;
		TreeNode<T> pre=null;//前一次访问结点
		stack.push(root);//
		while(!stack.isEmpty()){
			p=stack.peek();
			//如果当前结点没有孩子结点，或者孩子结点都已经被访问过
			if((p.left==null&&p.right==null)||(pre!=null&&(pre==p.left||pre==p.right))){
				System.out.print(p.data.toString()+",");
				stack.pop();
				pre=p;
			}
			else{
				if(p.right!=null)
					stack.push(p.right);
				if(p.left!=null)
					stack.push(p.left);
			}
		}
	}
	
	/**
	 * 层序遍历
	 * @param root
	 */
	public <T> void Layerorder(TreeNode<T> root){
		Queue<TreeNode<T>> queue=new LinkedList<TreeNode<T>>();//队列
		TreeNode<T> p=root;
		queue.add(p);
		while(!queue.isEmpty()){
			p=queue.peek();
			System.out.print(p.data.toString()+",");
			queue.poll();//把队首元素出列
			//依次把左子树，和右子树结点入队列
			if(p.left!=null)
				queue.add(p.left);
			if(p.right!=null)
				queue.add(p.right);
		}
	}
	
	/**
	 * 计算树的高度，注：树叶的高度为0
	 * @param root
	 * @return
	 */
	public <T> int height(TreeNode<T> root){
		if(root==null)
			return -1;
		else
			return 1+Math.max(height(root.left),height(root.right));
	}
}

热评文章