引入：
这里我们来复习下二叉树的基本操作，这里假定我们定义一个有序二叉树，就是对于任意的节点，其如果有左子节点，那么左子节点的值一定小于该节点，如果有右子节点，则右子节点的值一定大于该节点。我们这里还给出代码表明如何前序，中序，后序来遍历这个二叉树。
实践：
我们先定义一个二叉树节点的类：
|
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
|
package
com.charles.algo.binarytree;
/**
* 这个类定义了一个二叉树的节点
* @author charles.wang
*
*/
public
class
BinaryTreeNode {
//二叉树中当前节点的内容
private
Object data;
//二叉树的左子节点
private
BinaryTreeNode leftChild;
//二叉树的右子节点
private
BinaryTreeNode rightChild;
public
BinaryTreeNode(Object data,BinaryTreeNode leftChild,BinaryTreeNode rightChild){
this
.data =data;
this
.leftChild=leftChild;
this
.rightChild=rightChild;
}
public
Object getData() {
return
data;
}
public
void
setData(Object data) {
this
.data = data;
}
public
BinaryTreeNode getLeftChild() {
return
leftChild;
}
public
void
setLeftChild(BinaryTreeNode leftChild) {
this
.leftChild = leftChild;
}
public
BinaryTreeNode getRightChild() {
return
rightChild;
}
public
void
setRightChild(BinaryTreeNode rightChild) {
this
.rightChild = rightChild;
}
}
|
然后我们定义一个二叉树类，这个二叉树提供了插入节点，前序遍历，中序遍历，后序遍历的方法：
|
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
|
package
com.charles.algo.binarytree;
/**
* 这里定义了一个基本的有序二叉树的数据结构
* @author charles.wang
*
*/
public
class
OrderedBinaryTree<T> {
//用链表来实现排序二叉树的数据存储，这里放着根节点
private
BinaryTreeNode rootNode;
public
OrderedBinaryTree(){
rootNode =
null
;
}
/**
* 返回当前有序二叉树的最大高度
* @return
*/
public
int
getMaxHeight(){
return
getHeight(rootNode);
}
/**
* 基于当前树根节点确定子树的高度,这是一个递归的方法
* @return
*/
private
int
getHeight(BinaryTreeNode currentNode){
//如果当前树根节点为空，则返回 0
if
(currentNode==
null
)
return
0
;
//如果当前树根节点不为空，那么获取左子树高度和右字数高度的最大值
int
maxLeftTreeHeight = getHeight(currentNode.getLeftChild())+
1
;
int
maxRightTreeHeight = getHeight(currentNode.getRightChild())+
1
;
return
Math.max(maxLeftTreeHeight, maxRightTreeHeight);
}
/**
* 插入节点到当前的有序二叉树，
*/
public
OrderedBinaryTree insertNode(Object data ){
//如果有序二叉树中rootNode为空，那么就直接新建一个节点并且赋值给root
if
(rootNode==
null
){
BinaryTreeNode binaryTreeNode =
new
BinaryTreeNode(data,
null
,
null
);
rootNode=binaryTreeNode;
return
this
;
}
//如果有序二叉树的rootNode不为空，那么就调用递归方法进行插入
else
return
insertNode(data,rootNode);
}
/**
* 递归的插入一个节点到当前节点使得仍然保持 一个有序二叉树
*/
public
OrderedBinaryTree insertNode(Object data, BinaryTreeNode rootNode){
//创建一个代表当前待查数据的节点
BinaryTreeNode currentNode =
new
BinaryTreeNode(data,
null
,
null
);
//吧当前的数据和被插入的rootNode的大小进行比较
//如果当前数据小于被插入的rootNode,那么这个新的数据节点必定插在rootNode的左边
if
( (Integer)data< (Integer)rootNode.getData()){
//如果待插的rootNode的左节点为空，那么直接插入
if
(rootNode.getLeftChild()==
null
){
rootNode.setLeftChild(currentNode);
return
this
;
}
//如果待插的rotNode的左节点不为空，则递归的吧待插入点设为root的左节点，然后递归的调用方法插入
else
return
insertNode(data ,rootNode.getLeftChild());
}
//如果当前数据大于被插入的rootNode,那么这个新的数据节点必定插在rootNode的右边
else
{
//如果待插的rootNode的右边节点为空，那么直接插入
if
(rootNode.getRightChild()==
null
){
rootNode.setRightChild(currentNode);
return
this
;
}
//如果待插的rootNode的右边节点不为空，则赌鬼的吧所待插入点设为root的右节点，然后递归调用方法插入
else
return
insertNode(data,rootNode.getRightChild());
}
}
/**
* 前序遍历这个二叉树，并且打印出这个二叉树的各个节点
*/
public
void
preOrderFullBinaryTree(){
preOrder(rootNode);
}
/**
* 中序遍历这个二叉树，并且打印出这个二叉树的各个节点
*/
public
void
midOrderFullBinaryTree(){
midOrder(rootNode);
}
/**
* 后序遍历这个二叉树，并且打印出这个二叉树的各个节点
*/
public
void
postOrderFullBinaryTree(){
postOrder(rootNode);
}
/**
* 前序遍历某节点，它会先打印当前节点，然后打印出左边节点，然后打印出右边节点
*/
private
void
preOrder(BinaryTreeNode currentNode){
//当前的节点如果是null,则不打印出当前节点，并且退出递归
if
(currentNode!=
null
){
System.out.print(currentNode.getData()+
" "
);
//遍历左边子树
preOrder(currentNode.getLeftChild());
//遍历右边子树
preOrder(currentNode.getRightChild());
}
}
/**
* 中序遍历某节点，它会先打印左边节点，再打印当前节点，最后打印出右边节点
* @param args
*/
private
void
midOrder(BinaryTreeNode currentNode){
//当前节点如果是null,则不打印出当前节点，并且退出递归
if
(currentNode!=
null
){
midOrder(currentNode.getLeftChild());
System.out.print(currentNode.getData()+
" "
);
midOrder(currentNode.getRightChild());
}
}
/**
* 后序遍历某个节点，它会先打印出左边节点，再打印出右边节点，最后打印出当前节点
* @param args
*/
private
void
postOrder(BinaryTreeNode currentNode){
//如果当前的节点是null,则不打印出当前节点，并且退出递归
if
(currentNode!=
null
){
postOrder(currentNode.getLeftChild());
postOrder(currentNode.getRightChild());
System.out.print(currentNode.getData()+
" "
);
}
}
public
static
void
main(String[] args){
OrderedBinaryTree<Integer> fbt =
new
OrderedBinaryTree<Integer>();
fbt.insertNode(
12
).insertNode(
5
).insertNode(
9
).insertNode(
11
).insertNode(
8
).insertNode(
42
).insertNode(
4
);
//前序遍历所有的节点
System.out.println(
"前序的方式遍历二叉树的所有的节点:"
);
fbt.preOrderFullBinaryTree();
System.out.println();
//中序遍历所有的节点
System.out.println (
"中序的方式遍历二叉树的所有的节点:"
);
fbt.midOrderFullBinaryTree();
System.out.println();
//后序遍历所有的节点
System.out.println(
"后序的方式遍历二叉树的所有的节点:"
);
fbt.postOrderFullBinaryTree();
System.out.println();
}
}
|
其实由于考虑到二叉树定义的递归性，我们上述方法都是用递归实现的，比如插入就是比较当前元素，如果插入元素比当前元素少，那么就比较当前元素的左子元素，如果左子元素不存在，那么新插入的元素就作为左子元素，否则就以左子元素为根，递归的插入该元素到左子二叉树中。反过来也一样，如果插入元素比当前元素大，那么久比较当前元素的右子元素，如果右子元素不存在，那么新插元素就作为右子元素，否则就以右子元素为根，递归的插入到该元素到右子二叉树中。
前序，中序，后序遍历也是一样的。
验证结果：
最后我们来运行这个简单的例子，果然是期望的，比如我们分别插入了果然的不一样的数，那么遍历结果顺序是不一样的但是都遍历二叉树的所有节点。
本文转自 charles_wang888 51CTO博客，原文链接：http://blog.51cto.com/supercharles888/1350157，如需转载请自行联系原作者
