Fork me on GitHub

数据结构之———树和二叉树

树定义

树(tree)是由n(n>=0)个结点组成的有限集合(树中元素通常称为结点)。n=0的数称为空树;n>0的树T由以下两个条件约定构成:

  • 有一个特殊的结点称为根(root)节点,它只有后继结点,没有前驱结点。
  • 除根节点之外的其他结点分为m(m>=0)个互不相交的集合T0,T1,…,Tm-1;其中每个集合Ti(0<=i<m)本身又是一棵树,称为根的子树(subtree)

树是递归定义的。树是由结点组成的、结点之间具有层次关系的非线性结构。

树图解

树的术语

父母、孩子与兄弟结点

结点的前驱结点称为其父母(parent)结点,结点的后继结点称为其孩子(child)结点。一棵树中,只有根节点没有父母结点,其他结点有且仅有一个父母结点。
例如:图6-2(c)中的根节点A没有父母结点,A是B、C、D的父母结点,B、C、D是A的孩子结点。
兄弟结点:拥有同一个父母结点的多个结点之间称为兄弟(sibling)结点。例如图6-2(c)中B、C、D是兄弟结点;但F、G不是兄弟结点。
结点的祖先是指其父母结点,以及父母的父母结点等,直至根结点;结点的后代(子孙)是指其所有的孩子结点以及孩子的孩子结点等。

结点的度(degree)是结点所拥有子树的棵树。例如图6-2(c)中A的度是3,E的度是0;
度为0的结点称为叶子(leaf)结点,又称为终端结点
树的度指的是树中各节点的度的最大值。

结点层次、树的高度

结点的层次(level)属性反映结点处于树中的层次位置。根节点的层次为1,其他结点的层次是其父母结点的层次加1。
树的高度(height)或深度(depth)是树中结点的最大层次树;

边、路径

例如图6-2(c)中A结点是B结点的父母结点,有序对(A,B)称为连接这两个结点的分支,也称为边(edge)
路径长度(path length)为路径上的边数。例如图6-2(c)中从A到E的路径是(A,B,E),路径长度为2。

无序树、有序树

无序树:结点的子树T0,T1…,Tm-1之间没有次序,可以交换位置,称为无序树,简称树。
有序树:结点的子树T0,T1…,Tm-1从左至右是有次序的,不能交换位置,则称该树为有序树(ordered tree)。
注:有序树不是要排序,而是:不能交换位置。

森林

森林(forest)是m(m>=0)棵互不相交的树的集合。给森林加上一个根节点就变成一棵树,将树的根节点删除就变成森林。

树的表示法:

  • 图示法:图6-2(c)
  • 横向凹入表示法:
  • 广义表表示法:A(B(E,F),C(G),D(H,I,J))。

    二叉树

    二叉树是n(n>=0)个结点组成的有限集合,n=0时称为空二叉树;n>0的二叉树由一个根结点和两棵互不相交的、分别称为左子树和右子树的子二叉树构成。二叉树也是递归定义的。在树中定义的度,层次等术语,同样适用于二叉树。
    二叉树的结点最多只有两棵子树,所以二叉树的度最多为2。二叉树的子树有左右之分,即使只有一个子树也要区分是左子树还是右子树。

    二叉树的基本形态(5种)

  • 空二叉树
  • 只有一个根节点的二叉树
  • 由根节点、非空的子左树和空的右子树组成的二叉树
  • 由根节点、空的子左树和非空的右子树组成的二叉树
  • 由根节点、非空的子左树和非空的右子树组成的二叉树

二叉树不是度为2的有序树

二叉树的性质

  • 若根节点的层次为1,则二叉树第i层最多有2^(i-1)个结点(i>=1)
  • 在高度为h的二叉树中,最多有2^h -1个结点(h>=0)
  • 设一棵二叉树的叶子结点数为n0,2度结点树为n2,则n0=n2 + 1
    证明:设二叉树结点树为n,1度结点树为n1,则:n = n0 + n1 + n2;
    因1度结点有1个子女,2度结点有2个子女,叶子结点没有子女,根结点不是任何结点的子女,二叉树的结点总数可以表示为:n=0n0 + 1n1 + 2n2 +1
    综合上述两式可得:*n0 = n2 +1
    ;

满二叉树与完全二叉树

满二叉树:一棵高度为h的满二叉树是具有2^h -1个结点(h>=0)的二叉树。满二叉树中每一层的结点数目都达到最大值
完全二叉树:一棵具有n个结点高度为h的二叉树,如果它的每个结点都与高度为h的满二叉树中序号为0~n-1的结点一一对应,则称这棵二叉树为完全二叉树。
满二叉树是完全二叉树,而完全二叉树不一定是满二叉树。完全二叉树的第1~h-1层是满二叉树。

二叉树的遍历规则

二叉树的遍历规则有孩子优先兄弟优先(每个结点仅被访问一次)

孩子优先的遍历规则

  • 先根次序:访问根结点,遍历左子树,遍历右子树。
  • 中根次序:遍历左子树,访问根节点,遍历右子树。
  • 后根次序:遍历左子树,遍历右子树,访问根节点。

    兄弟优先的遍历规则

    二叉树的层次遍历是按层次次序进行的。遍历过程是从根结点开始,逐层深入,从左至右依次访问完当前层的所有结点,再访问下一层。
    二叉树层次遍历的特点是兄弟优先(对于任意一个结点,其兄弟结点在其孩子结点之前访问)。

    二叉树的表示和实现

    二叉树的存储结构

    二叉树主要采用链式存储结构,顺序存储结构仅适用于完全二叉树和满二叉树。
    二叉树的顺序存储结构
    二叉树的顺序存储结构仅适用于完全二叉树和满二叉树

    将完全二叉树的结点按次序进行编号,实际上是对完全二叉树的一次层次遍历。
    二叉树的链式存储结构
    二叉树通常采用链式存储结构,每个结点至少要有两条链分别连接左、右孩子结点,才能表达二叉树的层次关系。二叉树的链式存储结构主要有二叉链表和三叉链表。

    二叉树的二叉链表实现

    BinaryNode类:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    package binarytree;
    public class BinaryNode<T> {
    public T data; //数据域,存储数据元素
    public BinaryNode<T> left,right; //链域,分别指向左、右孩子结点
    //构造结点,参数分别指定元素和左、右孩子结点
    public BinaryNode(T data,BinaryNode<T> left,BinaryNode<T> right){
    this.data = data;
    this.left = left;
    this.right = right;
    }
    //构造指定值得叶子结点
    public BinaryNode(T data){
    this(data,null,null);
    }
    public BinaryNode(){
    this(null,null,null);
    }
    }

BinaryTree类:

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
package binarytree;
public class BinaryTree<T> {
private int i = 0;
public BinaryNode<T> root; // 根结点,结点结构为二叉链表
public BinaryTree() {
this.root = null;
} // 构造空二叉树
// 以先根和中根次序遍历序列构造二叉树
public BinaryTree(T[] prelist, T[] inlist) {
this.root = create(prelist, inlist, 0, 0, prelist.length);
}
// 标明空子树的先根序列构造一棵二叉树
public BinaryTree(T[] prelist) {
this.root = create(prelist);
}
/**
* 以先根和中根序列创建一棵子树,子树根结点值是prelist[preStart],n指定子序列长度,返回所创建子树的根结点
*
* @param prelist
* @param inlist
* @param preStart
* @param inStart
* @param n
* @return
*/
private BinaryNode<T> create(T[] prelist, T[] inlist, int preStart,
int inStart, int n) {
if (n <= 0)
return null;
T elem = prelist[preStart]; // 根结点值
BinaryNode<T> p = new BinaryNode<T>(elem); // 创建叶子结点
int i = 0;
while (i < n && !elem.equals(inlist[inStart + i]))
i++;
p.left = create(prelist, inlist, preStart + 1, inStart, i); // 创建左子树
p.right = create(prelist, inlist, preStart + i + 1, inStart + i + 1, n
- 1 - i); // 创建右子树
return p;
}
/**
* 以标明空子树的先根序列构造一棵子二叉树,子树的根值是prelist[i],返回所创建子树的根结点
*
* @param prelist
* @return
*/
private BinaryNode<T> create(T[] prelist) {
BinaryNode<T> p = null;
if (i < prelist.length) {
T elem = prelist[i];
i++;
if (elem != null) {
p = new BinaryNode<T>(elem); // 创建叶子结点
p.left = create(prelist); // 创建p的子左树
p.right = create(prelist); // 创建p的右子树
}
}
return p;
}
public boolean isEmpty() {
return this.root == null;
} // 判断二叉树是否空
/**
* 先根次序遍历二叉树
*/
public void preOrder() {
System.out.print("先根次序遍历二叉树: ");
preOrder(root); // 调用先根次序遍历二叉树的递归方法
System.out.println();
}
/**
* 先根次序遍历以p结点为根的子二叉树,递归方法
*
* @param p
*/
private void preOrder(BinaryNode<T> p) {
if (p != null) {
System.out.print(p.data.toString() + ""); // 访问当前结点
preOrder(p.left); // 按先根次序遍历当前结点的左子树,递归调用
preOrder(p.right); // 按先根次序遍历当前结点的右子树,递归调用
}
}
/**
* 中根次序遍历二叉树
*/
public void inOrder() {
System.out.print("中根次序遍历二叉树: ");
inOrder(root);
System.out.println();
}
/**
* 中根次序遍历以p结点为根的子二叉树,递归方法
*
* @param p
*/
private void inOrder(BinaryNode<T> p) {
if (p != null) {
inOrder(p.left); // 中跟次序遍历左子树,递归调用
System.out.print(p.data.toString() + "");
inOrder(p.right); // 中跟次序遍历右子树,递归调用
}
}
/**
* 后根次序遍历二叉树
*/
public void postOrder() {
System.out.print("后根次序遍历二叉树: ");
postOrder(root);
System.out.println();
}
/**
* 后根次序遍历以p结点为根的子二叉树,递归方法
*
* @param p
*/
private void postOrder(BinaryNode<T> p) {
if (p != null) {
postOrder(p.left); // 后跟次序遍历左子树,递归调用
postOrder(p.right); // 后跟次序遍历右子树,递归调用
System.out.print(p.data.toString() + "");
}
}
/**
* 返回二叉树的结点个数
*/
public int count() {
return count(root);
}
/**
* 返回以p结点为根的子树的结点个数
*
* @param p
* @return
*/
private int count(BinaryNode<T> p) {
if (p == null)
return 0;
return 1 + count(p.left) + count(p.right);
}
/**
* 返回二叉树的高度
*/
public int height() {
return height(root);
}
private int height(BinaryNode<T> p) {
if (p == null)
return 0;
int lh = height(p.left);
int rh = height(p.right);
return (lh >= rh) ? lh + 1 : rh + 1;
}
/**
* 查找并返回首次出现的关键字为key元素结点
*/
public BinaryNode<T> search(T key) {
return search(root, key);
}
private BinaryNode<T> search(BinaryNode<T> p, T key) {
if (p == null || key == null)
return null;
if (p.data.equals(key))
return p;
BinaryNode<T> find = search(p.left, key);
if (find == null)
find = search(p.right, key);
return find;
}
/**
* 获得父母结点
*/
public BinaryNode<T> getParent(BinaryNode<T> node) {
if (root == null || node == null || node == root)
return null;
return getParent(root, node);
}
private BinaryNode<T> getParent(BinaryNode<T> p, BinaryNode<T> node) {
if (p == null)
return null;
if (p.left == node || p.right == node)
return p;
BinaryNode<T> find = getParent(p.left, node);
if (find == null)
find = getParent(p.right, node);
return find;
}
}

构造并遍历二叉树

构造图6-11(a)中所示二叉树,以先根、中根、后根三种次序遍历二叉树
BinaryTree_test类:

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
package binarytree;
import org.junit.Test;
public class BinaryTree_test {
public BinaryTree<String> make() {
BinaryTree<String> bitree = new BinaryTree<String>();
BinaryNode<String> child_b, child_c, child_d;
child_d = new BinaryNode<String>("D", new BinaryNode<String>("H"), null);
child_b = new BinaryNode<String>("B", child_d, new BinaryNode<String>(
"E"));
child_c = new BinaryNode<String>("C", new BinaryNode<String>("F"),
new BinaryNode<String>("G"));
bitree.root = new BinaryNode<String>("A", child_b, child_c);
return bitree;
}
/**
* 遍历二叉树
*/
@Test
public void foreach() {
BinaryTree<String> bitree = make();
bitree.preOrder(); // 先根次序遍历二叉树
bitree.inOrder(); // 中根次序遍历二叉树
bitree.postOrder(); // 后根次序遍历二叉树
}
/**
* 构造二叉树
*/
@Test
public void createTree() {
String[] prelist = { "A", "B", "D", "G", "C", "E", "F", "H" }; // 先根序列
String[] inlist = { "D", "G", "B", "A", "E", "C", "H", "F" }; // 中根序列
BinaryTree<String> bitree = new BinaryTree<String>(prelist, inlist);
bitree.preOrder();
bitree.inOrder();
}
/**
* 构造空二叉排序树,并查找
*/
@Test
public void BinarySortTree_ex() {
// 构造空二叉排序树
BinarySortTree<Integer> bstree = new BinarySortTree<Integer>();
int[] values = { 54, 18, 66, 87, 36, 12, 54, 81, 15, 76, 57, 6, 40, 99,
85, 99 };
for (int i = 0; i < values.length; i++)
bstree.insert(new Integer(values[i])); // 插入二叉排序树
bstree.inOrder(); // 中根次序遍历二叉排序树,得到按关键字升序排序的数据元素序列
Integer key = new Integer(values[values.length - 1]); // 查找数组中最后一个数
System.out.println("查找" + key + ","
+ (bstree.search(key) != null ? "" : "不") + "成功");
}
}

foreach()输出结果:
先根次序遍历二叉树: ABDHECFG
中根次序遍历二叉树: HDBEAFCG
后根次序遍历二叉树: HDEBFGCA

构造二叉树

唯一确定一棵二叉树的方法有三种

  • 先根和中根序列表示
    已知二叉树的先根和中根两种次序的遍历序列,可以唯一确定一棵二叉树。(见BinaryTree类和BinaryTree_make类)
  • 标明空子树的先根序列表示
  • 广义表表示

二叉排序树和平衡二叉树

二叉排序树是一种既支持排序、又支持高效的查找、插入、删除操作的数据组织方案,它的查找等操作效率可达到O(log2 n)。

二叉排序树

定义

二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:

  • 每个结点都有一个作为查找依据的关键字,所有结点的关键字互不相同
  • 若一个结点的左子树不空,则左子树上所有结点的关键字均小于这个结点的关键字;若一个结点的右子树不空,则右子树上所有结点的关键字均大于这个结点的关键字
  • 每个结点的左右子树也分别为二叉排序树

一棵二叉排序树如图8-15所示。对该二叉排序树按中根次序遍历,得到按关键字升序排列的数据元素序列为{6,12,18,36,54,57,66,76,81,87,99}。

查找

在一棵二叉排序树中,查找关键字为key元素结点,算法描述如下:

  • 从根结点开始,设p指向根结点
  • 将p结点的关键字与key比较,若两者相等,则查找成功;若key较小,则在p的左子树中继续查找;若key较大,则在p的右子树中继续查找。
  • 重复执行上一步,直到查找成功或p为空。若p为空,则查找不成功。
    在图8-15所示的二叉排序树中,查找76的路径是(54,66,87,76),到达结点76,查找成功;查找40的路径是(54,18,36),经过叶子结点36,查找不成功。由此可知,在二叉排序树中,一次查找经过从根结点到某结点的一条路径而不需要遍历整棵树,若查找成功则到达指定结点,否则经过某个叶子结点。因此,二叉排序树能够提供快速查找功能。二叉排序树又称为二叉查找树。

插入

一棵二叉排序树,插入一个结点之后必须仍然是二叉排序树。每插入一个结点,首先需要找到该结点在二叉排序树中的插入位置,若具有相同关键字的结点已经在二叉排序树中,则不插入;否则将新结点作为叶子结点链接在其查找不成功时的一条路径之尾,该路径从根结点到某个原叶子结点。因此,给定一棵二叉排序树,一个结点的插入位置是唯一的。
在图8-15的二叉排序树中,欲插入40,查找40的路径是(54,18,36),查找不成功,将结点40作为原叶子结点36的右孩子插入到该棵二叉排序树中。

删除

在二叉排序树中删除一个结点,首先查找该结点,若存在,则根据结点的度对二叉排序树进行不同程度的调整,使删除结点后的二叉树仍然是二叉排序树。

由于删除和插入的规则不同,若删除一个非叶结点,再将其立即插入,则删除前和删除后的二叉排序树不一定相同。

查找和插入代码:
构造空二叉排序树,并查找的代码在上面的BinaryTree_test类中
BinarySortTree类:

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
package binarytree;
public class BinarySortTree<T extends Comparable<T>> extends BinaryTree<T> {
// 构造空二叉排序树
public BinarySortTree() {
super();
} // 调用父类的默认构造方法
// 将values数组元素依次插入构造一棵二叉排序树
public BinarySortTree(T[] values) {
super();
for (int i = 0; i < values.length; i++)
this.insert(values[i]); // 将元素插入到当前的二叉排序树中
}
//查找并返回首次出现的关键字为key元素结点,若查找不成功,则返回null,非递归算法
public BinaryNode<T> search(T key) {
if (key == null)
return null;
BinaryNode<T> p = this.root;
while (p != null && p.data.compareTo(key) != 0)
if (p.data.compareTo(key) > 0) // 若key较小
p = p.left; // 进入左子树
else
p = p.right; // 进入右子树
return p;
}
// 插入元素x结点,不插入关键字重复元素和空对象
public void insert(T x) {
if (x == null)
return; // 不能插入空对象
if (root == null)
root = new BinaryNode<T>(x); // 建立根结点
else { // 插入x到以root为根的二叉排序树中
BinaryNode<T> p = this.root, parent = null;
while (p != null) {
parent = p;
if (x.compareTo(p.data) == 0)
return; // 不插入关键字重复的元素
if (x.compareTo(p.data) < 0)
p = p.left;
else
p = p.right;
}
p = new BinaryNode<T>(x); // 建立叶子结点p
if (x.compareTo(parent.data) < 0)
parent.left = p; // p作为parent的左孩子
else
parent.right = p; // p作为parent的右孩子
}
}
//删除元素为x的结点,返回删除结点,若没删除,返回null
public BinaryNode<T> remove(T x){
if(root == null || x == null)
return null;
return remove(x,root,null); //在以root为根的二叉排序树中删除值为x的结点
}
//在以p为根的子树中删除元素为x的结点,parent是p的父母结点,返回删除结点,递归算法
private BinaryNode<T> remove(T x, BinaryNode<T> p, BinaryNode<T> parent) {
if(p == null)
return null;
if(x.compareTo(p.data)<0)
return remove(x,p.left,p); //在p的左子树中删除x,递归调用
if(x.compareTo(p.data)>0)
return remove(x,p.right,p); //在p的右子树中删除x,递归调用
if(p.left!=null && p.right!= null){ //找到待删除结点p,p是2度结点
BinaryNode<T> insucc = p.right; //寻找p在中根次序下的后继结点insucc
while(insucc.left!= null)
insucc = insucc.left;
p.data = insucc.data; //以后继结点值替换
return remove(p.data,p.right,p);
}
if(parent==null){ //p是一度或叶子结点,删除根结点,即p==root
if(p.left!=null)
root = p.left;
else root = p.right;
return p; //返回删除结点p
}
if(p == parent.left) //p是1度或叶子结点,p是parent的左孩子
if(p.left!=null)
parent.left = p.left; //以p的左子树填补
else parent.left = p.right;
else //p是parent的右孩子
if(p.left!=null)
parent.right=p.left;
else parent.right=p.right;
return p;
}
}

二叉排序树的查找性能分析

由于二叉排序树的插入和删除操作花费时间的主要部分是查找操作,所以二叉排序树的各操作性能由查找效率决定。
二叉排序树的平均查找长度为O(log2 n)~O(n)。
二叉排序树的查找效率与二叉树的高度有关,高度越低,查找效率越高。因此提高二叉排序树查找效率的办法是尽量降低二叉排序树的高度。

平衡二叉树

定义

平衡二叉树或者是一棵空二叉树,或者是具有下列性质的二叉排序树:

  • 它的左子树和右子树都是平衡二叉树
  • 左子树与右子树的高度只差的绝对值不超过1

结点的平衡因子 = 右子树的高度 - 左子树的高度
在平衡二叉树中,插入或删除一个结点可能破坏二叉树的平衡性,因此,在插入或删除时都要调整二叉树,使之始终保持平衡状态。

平衡二叉树的插入

在一棵平衡二叉树中插入一个结点,如果插入后破坏了二叉树的平衡性,则需要调整一棵最小不平衡子树,在保证排序树特性的前提下,调整最小不平衡子树中各节点的连接关系,以达到新的平衡。
最小不平衡子树:离插入结点最近,且以平衡因子绝对值大于1的结点为根的子树。
设关键字序列为{54,36,12,87,95,66,18},依次插入结点构造一棵平衡二叉树的过程如图8-23所示:

调整平衡的模式

4种:LL、RR、LR、RL

LL型调整

当在A的左孩子(L)的左子树(L)上插入结点

RR型调整

当在A的右孩子(R)的右子树(R)上插入结点

LR型调整

当在A的左孩子B(L)的右子树(R)上插入结点

RL型调整

当在A的右孩子B(R)的左子树(L)上插入结点

项目地址

项目地址在这里

「真诚赞赏,手留余香」