树结构之线索二叉树的介绍和代码实现
1 线索二叉树
1.1 介绍
- 由于二叉树的叶子结点的指针没有任何指向，只能空着，就提出了线索化二叉树的概念
- n个节点的二叉树中含有n+1
【2*n - (n-1) == n+1】：有n个节点，就有2*n个指针域，除了根节点外，每一个节点都会被一个指针引用，即（n-1）个，所以才2*n-(n-1)空指针域个空指针域
- 线索二叉树（Threaded BinaryTree）：利用二叉树中空指针域，用来指定该节点在某种遍历次序下的前驱和后继节点的指针。根据线索性质的不同，线索二叉树可以分为前序线索二叉树，中序线索二叉树，后续线索二叉树
- 一个节点的前一个节点，称为前驱节点。反之称为后继节点
1.2 图解
- 上面的二叉树中序遍历结果为：4 -> 2 -> 5 -> 1 -> 6 -> 3
- 通过遍历结果，来对多余的空指针进行指向，左指针用于指向前驱节点，右指针用于指向后继节点
- 产生问题：一个节点的左右指针有可能是指向左右节点，也有可能是指向前驱/后继节点。所以节点需要额外的属性来标志该左右指针是指向什么内容
1.3 代码
- （1）代码实现
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
94public class ThreadBinaryTree {
//子类 --- 树节点
private class Node {
public int weight; //权重
public Object data; //数据
public Node left; //左子节点
public Node right; //右子节点
//额外的属性来表示节点类型，0是指向左右子树，1是指向前驱后继节点（默认0）
public int leftType; //左子节点类型
public int rightType; //右子节点类型
public Node(int weight, Object data) {
this.weight = weight;
this.data = data;
}
public String toString() {
return "Node{" + weight + ": " + data + '}';
}
}
//---------------------------------------------------------------------------
private Node root; //根节点
private Node preNode; //前驱节点
public ThreadBinaryTree() {
//因为没有具体的规则，二叉树通过手动创建
root = new Node(1, "A");
root.left = new Node(2, "B");
root.right = new Node(3, "C");
root.left.left = new Node(4, "D");
root.left.right = new Node(5, "E");
root.right.left = new Node(6, "F");
}
/**
* 中序线索化树
*/
public void midThreadedTree() {
if (root == null) {
System.out.println("树为空！");
}
//递归中序线索化节点
midThread(root);
//清除前驱节点记录
preNode = null;
}
/**
* 中序线索化节点 -- 递归本体
* @param node 树节点
*/
public void midThread(Node node) {
//递归中序线索化左子树
if (node.left != null) {
midThread(node.left);
}
//线索化节点
//处理左节点
if (node.left == null) {
node.left = preNode; //左子节点指向前驱节点
node.leftType = 1; //修改结点内向为前驱节点
}
//处理右节点
//因为当前节点是无法获取后继节点，所以在遍历到新节点时，通过前驱节点的右空子节点来指定新节点，来实现指向后继节点
if (preNode != null && preNode.right == null) {
preNode.right = node;
preNode.rightType = 1;
}
//处理完毕，将当前节点作为下一个节点的前驱节点
preNode = node;
//递归中序线索化右子树
if (node.right != null) {
midThread(node.right);
}
}
//测试是否线索化成功
public void test() {
//调用叶子节点的左右子节点是否有数据
//本应该是空指针域，变成有数据则线索化成功
//测试数据是：5号节点，前驱节点为2号节点，后继节点为1号节点
System.out.println("前驱节点为：" + root.left.right.left);
System.out.println("后继节点为：" + root.left.right.right);
}
}
- （2）测试
1
2
3
4
5
6
7
8
public void threadBinaryTreeTest() {
ThreadBinaryTree threadBinaryTree = new ThreadBinaryTree();
threadBinaryTree.midThreadedTree(); //中序线索化树
//因为Node为私有类，写一个方法来查看Node内容
threadBinaryTree.test();
}
1.4 遍历线索二叉树
- 因为二叉树的结构发生了变化，所以原来遍历二叉树的方法不再生效，会变成死递归
- 但因为二叉树的结构发生变化，原本利用递归来实现的回溯，可以通过后继节点来实现，变成线性遍历，提高了遍历的效率
- （1）代码实现
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/**
* 中序遍历
*/
public void midPrint() {
//每个线索化二叉树会有其特定的规律，所以需要根据实际情况调整规律
//以下是中序线索二叉树的遍历规律
if (root == null) {
System.out.println("树为空！");
}
Node node = root;
while (node != null) {
//优先寻找左节点为叶子节点的数，特征为节点类型为1
while (node.leftType != 1) {
node = node.left;
}
System.out.println(node);
//通过后继节点，回溯到父节点，直至父节点存在右子树
while (node.rightType == 1) {
node = node.right;
System.out.println(node);
}
//切换节点到父节点的右子树，进行下一轮遍历
node = node.right;
}
}
- （2）测试
1
2
3
4
5
6
7public void threadBinaryTreeTest() {
ThreadBinaryTree threadBinaryTree = new ThreadBinaryTree();
threadBinaryTree.midThreadedTree(); //中序线索化树
//中序遍历
threadBinaryTree.midPrint();
}
