[toc]
数据结构之顺序储存二叉树
1. 顺序储存二叉树
1.1 顺序存储二叉树的概念
- 从数据存储来看，数组存储方式和树的存储方式可以相互转换，即 数组可以转换成树， 树也可以转换成数组。
1.2 顺序存储二叉树的特点
- 顺序二叉树通常只考虑完全二叉树
- 第 n 个元素的左子节点为
2 * n + 1
- 第 n 个元素的右子节点为
2 * n + 2
- 第 n 个元素的父节点为
(n-1) / 2
n : 表示二叉树中的第几个元素(按 0 开始编号如图所示)
1.3 顺序存储二叉树遍历
- 要求在遍历数组 arr 时，仍然可以以前序遍历，中序遍历和后序遍历的方式完成结点的遍历
- 给你一个数组
{1,2,3,4,5,6,7}，要求以二叉树前序遍历，中序遍历和后序遍历的方式进行遍历。
- 前序遍历的结果应当为
1,2,4,5,3,6,7
- 中序遍历的结果应当为
4 2 5 1 6 3 7
- 后序遍历的结果应当为
4 5 2 6 7 3 1
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
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
| public class ArrBinaryTreeDemo {
public static void main(String[] args) {
int[] arr = {1,2,3,4,5,6,7};
ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
System.out.println("顺序储存的二叉树的前序遍历：");
arrBinaryTree.preOrder();
System.out.println("顺序储存的二叉树的中序遍历：");
arrBinaryTree.infixOrder();
System.out.println("顺序储存的二叉树的后序遍历：");
arrBinaryTree.postOrder();
}
}
class ArrBinaryTree {
private int[] arr;
public ArrBinaryTree(int[] arr) {
this.arr = arr;
}
public void preOrder() {
this.preOrder(0);
}
public void infixOrder() {
this.infixOrder(0);
}
public void postOrder() {
this.postOrder(0);
}
public void preOrder(int index) {
if (arr == null || arr.length == 0) {
System.out.println("数组为空，不能按照二叉树的前序遍历");
}
System.out.println(arr[index]);
if ((index * 2 + 1) < arr.length) {
preOrder((index * 2 + 1));
}
if ((index * 2 + 2) < arr.length) {
preOrder((index * 2 + 2));
}
}
public void infixOrder(int index) {
if (arr == null || arr.length == 0) {
System.out.println("数组为空，不能按照二叉树的前序遍历");
}
if ((index * 2 + 1) < arr.length) {
infixOrder((index * 2 + 1));
}
System.out.println(arr[index]);
if ((index * 2 + 2) < arr.length) {
infixOrder((index * 2 + 2));
}
}
public void postOrder(int index) {
if (arr == null || arr.length == 0) {
System.out.println("数组为空，不能按照二叉树的前序遍历");
}
if ((index * 2 + 1) < arr.length) {
postOrder((index * 2 + 1));
}
if ((index * 2 + 2) < arr.length) {
postOrder((index * 2 + 2));
}
System.out.println(arr[index]);
}
}
|
2. 线索化二叉树
- n 个结点的二叉链表中含有
n+1 【公式 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为”线索”）
- 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为
线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
- 一个结点的前一个结点，称为 前驱结点
- 一个结点的后一个结点，称为后继结点
2.1 线索二叉树应用案例
将下面的二叉树，进行中序线索二叉树。中序遍历的数列为 {8, 3, 10, 1, 14, 6}
当线索化二叉树后，Node 节点的 属性 left 和 right ，有如下情况:
- left 指向的是左子树，也可能是指向的前驱节点.
- ① 节点 left 指向的左子树,
- ⑩ 节点的 left 指向De就是前驱节点
- right 指向的是右子树，也可能是指向后继节点。
- ① 节点 right 指向的是右子树
- ⑩ 节点的 right 指向的是后继节点
2.2 代码实现
2.2.1 HeroNode 部分
- 如果
leftType == 0 表示指向的是左子树，如果是1 表示指向的是前驱节点
- 如果
rightType == 0 表示指向是右子树, 如果 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
|
class HeroNode{
private int no;
private String name;
private HeroNode left;
private HeroNode right;
private int leftType;
private int rightType;
public HeroNode(int no, String name) {
super();
this.no = no;
this.name = name;
}
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + "]";
}
}
|
2.2.2 ThreadedBinaryTree 部分
public void threadedList();遍历线索化二叉树的方法
public void threadedNode();
public void threadedNode(HeroNode node);
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
|
class ThreadedBinaryTree{
private HeroNode root;
private HeroNode pre = null;
public HeroNode getRoot() {
return root;
}
public void setRoot(HeroNode root) {
this.root = root;
}
public HeroNode getPre() {
return pre;
}
public void setPre(HeroNode pre) {
this.pre = pre;
}
public void threadedList() {
HeroNode node = root;
while(node != null) {
while(node.getLeftType() == 0) {
node = node.getLeft();
}
System.out.println(node);
while(node.getRightType() == 1) {
node = node.getRight();
System.out.println(node);
}
node = node.getRight();
}
}
public void threadedNode() {
this.threadedNode(root);
}
public void threadedNode(HeroNode node) {
if(node == null) {
return;
}
threadedNode(node.getLeft());
if(node.getLeft() == null) {
node.setLeft(pre);
node.setLeftType(1);
}
if(pre != null && pre.getRight() == null) {
pre.setRight(node);
pre.setRightType(1);
}
pre = node;
threadedNode(node.getRight());
}
}
|
2.2.3 测试
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
| public class ThreadedBinaryTreeDemo {
public static void main(String[] args) {
HeroNode root = new HeroNode(1, "tom");
HeroNode node2 = new HeroNode(3, "jack");
HeroNode node3 = new HeroNode(6, "smith");
HeroNode node4 = new HeroNode(8, "mary");
HeroNode node5 = new HeroNode(10, "king");
HeroNode node6 = new HeroNode(14, "dim");
root.setLeft(node2);
root.setRight(node3);
node2.setLeft(node4);
node2.setRight(node5);
node3.setLeft(node6);
ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
threadedBinaryTree.setRoot(root);
threadedBinaryTree.threadedNode();
HeroNode leftNode = node5.getLeft();
HeroNode rightNode = node5.getRight();
System.out.println("10 号结点的前驱结点是 =" + leftNode);
System.out.println("10 号结点的后继结点是=" + rightNode);
System.out.println("使用线索化的方式遍历 线索化二叉树");
threadedBinaryTree.threadedList();
}
}
|
