线索化二叉树
前言：
对于线索化二叉树来说，他的后序线索化二叉树的遍历是其最难的地方，需要很多的辅助节点
对于中序、前序线索化二叉树相对来说比较简单。
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
| public class Node {
public int id;
public String name;
public Node right;
public Node left;
public int l;
public int r;
public Node parent;
public void prefix(){
System.out.println(this);
if(this.left != null){
this.left.prefix();
}
if (this.right != null){
this.right.prefix();
}
}
public void infix(){
if(this.left != null){
this.left.infix();
}
System.out.println(this);
if (this.right != null){
this.right.infix();
}
}
public void suffix(){
if(this.left != null){
this.left.suffix();
}
if (this.right != null){
this.right.suffix();
}
System.out.println(this);
}
public Node(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public String toString() {
return "Node{" +
"id=" + id +
", name='" + name + '\'' +
", left节点是否为空=" + l +
", right节点是否为空=" + r +
'}';
}
}
|
前序线索化二叉树
思路：
线索化思路
首先判断当前节点是否为空，如果不为空再做处理。
- 左移至最左边，判定left为空时将临时节点指向当前node节点的左指针
- 处理右节点时是在下一次，此时node为下一个节点，而temp则指向上一轮的node节点。然后将temp指向的right节点连接到node（也就是当前节点）
- temp节点，让其始终跟在node节点的后面（node节点递归移动）
- 向左右分别递归移动当前节点
线索化遍历思路
根左右，所以从根节点开始，沿着左子树进行处理，当子节点的left指针类型是null时，给其left赋值，然后标注为此node的l= 1 说明到了最左子节点，然后处理子节点的right指针指向的节点，可能是右子树，也可能是后继节点，无论是哪种类型继续按照上面的方式（先沿着左子树处理，找到子树的最左子节点，然后处理right指针指向），以此类推，直到节点的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
|
public void prefixSearch(Node node){
if (node == null){
return;
}
if(node.left == null){
node.left = temp;
node.l = 1;
}
if(temp != null && temp.right == null){
temp.right = node;
temp.r = 1;
}
temp = node;
if(node.l == 0){
prefixSearch(node.left);
}
if(node.r == 0){
prefixSearch(node.right);
}
}
|
前序线索化的遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public void prefixLink(){
Node node = root;
while(node != null){
System.out.println(node);
while(node.l == 0){
node = node.left;
System.out.println(node);
}
while(node.r == 1){
node = node.right;
System.out.println(node);
}
node = node.right;
}
}
|
中序线索化二叉树
思路：
线索化思路
首先判断当前节点是否为空，如果不为空再做处理。
- 向左递归移动当前节点
- 判定left为空时将临时节点指向当前node节点的左指针
- 处理右节点时是在下一次，此时node为下一个节点，而temp则指向上一轮的node节点。然后将temp指向的right节点连接到node（也就是当前节点）
- temp节点，让其始终跟在node节点的后面（node节点递归移动）
- 向右递归移动当前节点
遍历思路
左根右，因此第一个节点一定是最左子节点，先找到最左子节点，依次沿着right指针指向进行处理（无论是指向子节点还是指向后继节点），直到节点的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
|
public void infixSearch(Node node){
if(node == null){
return;
}
infixSearch(node.left);
if (node.left == null){
node.left = temp;
node.l = 1;
}
if (temp!= null && temp.right == null){
temp.right = node;
temp.r = 1;
}
temp = node;
infixSearch(node.right);
}
|
中序线索化的遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public void infixLink(){
Node node = root;
while(node != null){
while(node.l == 0){
node = node.left;
}
System.out.println(node);
while(node.r == 1){
node = node.right;
System.out.println(node);
}
node = node.right;
}
}
|
后序线索化二叉树
思路：
线索化思路
首先判断当前节点是否为空，如果不为空再做处理。
- 向左递归移动当前节点
- 向右递归移动当前节点
- 判定left为空时将临时节点指向当前node节点的左指针
- 处理右节点时是在下一次，此时node为下一个节点，而temp则指向上一轮的node节点。然后将temp指向的right节点连接到node（也就是当前节点）
- temp节点，让其始终跟在node节点的后面（node节点递归移动）
线索化遍历思路
后序遍历线索化二叉树最为复杂，通用的二叉树数节点存储结构不能够满足后序线索化，因此我们扩展了节点的数据结构，增加了父节点的指针。后序的遍历顺序是：左右根，先找到最左子节点，沿着right后继指针处理，当right不是后继指针时，并且上一个处理节点是当前节点的右节点，则处理当前节点的右子树，遍历终止条件是：当前节点是root节点，并且上一个处理的节点是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
|
public void suffixSearch(Node node){
if (node == null){
return;
}
suffixSearch(node.left);
suffixSearch(node.right);
if(node.left == null){
node.left = temp;
node.l = 1;
}
if(temp != null && temp.right == null){
temp.right = node;
temp.r = 1;
}
temp = 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
|
public void suffixLink(){
Node node = root;
while(node.l == 0){
node = node.left;
}
Node pre = null;
while(node != null){
if (node.r == 1){
System.out.println(node);
pre = node;
node = node.right;
}else{
if(node.right == pre){
System.out.println(node);
if(node == root){
return;
}
pre = node;
node = node.parent;
}else{
node = node.right;
while (node != null && node.l == 0){
node = node.left;
}
}
}
}
}
|
