数据结构之树-线索二叉树(二)-学习笔记-57

引入

上一节,我们试着解决了树在存储时空间浪费和没法找到双亲结点的问题,这一节,我们着重看一下如何用代码实现。这篇难度有一点大,请务必沉住气,认真仔细。

思路拆解

我们一步一步的拆解代码来看看。

创建树结构体

我们首先声明我们重新设计的线索二叉树结点

  • char data 存放结点数据
  • 左孩子、右孩子这个不用细说了吧,
  • Ltag 和 Rtag 主要是判断左孩子和右孩子究竟是指向左右孩子还是前驱后继
  • 我们定义结构体的时候,使用了 typedef
  • 后面所有的 BiTNode 你可以理解为 struct BiTNode,代表该结构体
  • 后面所有的 BiTree 你可以理解为 struct BiTNode *,代表结构体指针
  • 注意上面有个星号哈!
1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof(struct BiTNode)

typedef enum{link,thread} NodeState;
typedef struct BiTNode{
char data;
struct BiTNode *Lchild;
struct BiTNode *Rchild;
NodeState Ltag;
NodeState Rtag;
}BiTNode,*BiTree;

创建二叉树

我们刚才重新设计了结点,现在开始生成树,首先接收数据

  • 重点:我们这里的形参,是 BiTree *tempTree
  • BiTree *tempTree 你可以理解为 struct BiTNode **tempTree
  • 就是一个指向二叉树结点的结构体的指针的指针。
  • 然后 tempC 是用来存放输入的结点 data 的
  • 我们使用 scanf 来接收数据

然后我们判断 scanf 中的数据

  • 如果输入的是 # 号,表示结点为空,我们就把结点设置为 NULL
  • 这里注意,我们是将*tempTree设置为 NULL,不是** tempTree
  • 是1个星号的,1个星号表示的是结点结构体的指针

如果scanf 中接受的不是#号

  • 先创建动态存储空间,1个星号表示的是结点结构体的指针
  • 所以给1个星号表示的是结点结构体的指针创建动态存储空间
  • (*tempTree)这里为什么加括号呢?学过指针都知道!
  • *tempTree 表示的是 tempTree 中地址指向的数据
  • 既然 tempTree 存储的是指针的指针,所以把 tempTree 加一个星号
  • 表示 tempTree 中结点的地址,也就是结点结构体的开始地址
  • 我们先给 data 赋值为 tempC
  • 然后默认左右 tag 是 Link,也就是链接状态
  • 后面如果遇到子树为空,我们会修正 tag 的内容
  • 然后利用递归,创建左子树和右子树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Create(BiTree *tempTree){
char tempC;
scanf("%c",&tempC);
if(tempC=='#'){
*tempTree=NULL;
}else{
*tempTree=(BiTree)malloc(LEN);
(*tempTree)->data=tempC;
(*tempTree)->Ltag=link;
(*tempTree)->Rtag=link;
Create(&(*tempTree)->Lchild);
Create(&(*tempTree)->Rchild);
}
}

给二叉树添加线索

我们生成了一个二叉树,这棵二叉树的每个结点都有 Ltag 和 Rtag,该如何利用呢

  • 我们这一步就是给哪些没有前驱、后继的结点,修改 Ltag 和 Rtag 状态。
  • pre 是一个结点结构体指针的全局变量,保存根的前驱
  • 然后我们传入二叉树,给二叉树添加线索
  • 利用中序遍历,左中右的方式,递归遍历这棵树。

判断根节点左子树的情况

  • 在根节点时,判断根节点左右子树的状态,记住有右必有左
  • 先判断左子树,如果为空,那么这个结点的 Lchild 改为前序的地址
  • Ltag 改为 thread,表示这个 Lchild 是线索
  • 这里的 Lchild 是 pre,pre 等下会存储每个结点的前驱。

判断根节点右子树的情况

  • 怎么判断右子树呢?如果只有左没有右呢?
  • 所以判断 pre 的右子树,只要当前结点的前一结点的右子树为空
  • 那么就改变 Rtag 状态为线索
  • Rchild 右孩子为当前结点
  • 也就是当前结点前驱没有右子树,那么前驱的右孩子指向当前结点。
  • 记得最后把当前的地址个 pre,这样指针才能向后走,pre 才能保存前驱结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
BiTree pre;

void Inthread(BiTree t){
if(t){
Inthread(t->Lchild);

if(!t->Lchild){
t->Ltag=thread;
t->Lchild=pre;
}

if(!pre->Rchild){
pre->Rtag=thread;
pre->Rchild=t;
}

pre=t;

Inthread(t->Rchild);
}
}

根结点的前驱

我们知道,根结点是没有双亲的,那么怎么获得根结点的前驱呢?

  • 创建一个 p ,模拟根的前驱,让根的前驱指向这个 p
  • 先创建一个 p,星号的道理和创建树的时候相同,就不解释了。
  • Rtag 因为指向自己,所以为 thread 线索
  • Ltag 因为等下要指向树本身,所以为 link
  • 然后让 Rchild 指向子集
  • 判断树是不是空的,如果是空的,那没得玩,左右子树都指向 p 自己
  • 如果不是空的,那就让左子树指向树根
  • pre 就能获取根的前驱了,就是 p
  • 然后从这里调用给二叉树加线索的函数
  • 因为给二叉树加线索,需要用到根的前驱。

记得收尾

  • 最后,我们让这棵树连成圈
  • 让 pre,也就是最后一个结点的前驱的右孩子指向 P,也就是根的前驱
  • 让后 p 的右孩子指向 pre
  • 这样,就连起来了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void Inorderthread(BiTree t , BiTree *p){
*p=(BiTree)malloc(LEN);
(*p)->Rtag=thread;
(*p)->Ltag=link;
(*p)->Rchild=*p;
if(!t){
(*p)->Lchild=*p;
}else{
(*p)->Lchild=t;
pre=*p;
Inthread(t);

pre->Rtag=thread;
pre->Rchild=*p;
(*p)->Rchild=pre;
}
}

两种遍历方式

用递归的时候注意,要在加线索之前使用,否则树都连起来就会出错。

###递归中序遍历,不多说了,需要的话看前面

1
2
3
4
5
6
7
8

void Inthreading(BiTree t){
if(t){
Inthreading(t->Lchild);
printf("%c",t->data);
Inthreading(t->Rchild);
}
}

迭代中序遍历,就是利用 while 循环遍历

同样是左中右

  • 如果 p=t->Lchild,那就证明转了一圈了。
  • 然后判断最左边的结点,输出
  • 判断右边结点是否是叶子,也输出
  • p 向右孩子移动一位
  • 直到转完所有的结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Inorderthreading(BiTree t){
BiTree p;
p=t->Lchild;
while(p!=t){
while(p->Ltag==link){
p=p->Lchild;
}
printf("%c",p->data);
while(p->Rtag==thread && p->Rchild!=t){
p=p->Rchild;
printf("%c",p->data);
}
p=p->Rchild;
}
}

主调函数

这个其实没什么好讲的,就是星号和顺序的问题

  • 星号请注意,因为传过去的是指针的地址,所以要加&符号
  • 顺序请注意,先使用递归输出,再增加线索,最后用迭代循环输出
  • 原因是增加线索后,树连起来了,递归没法结束。
1
2
3
4
5
6
7
8
9
10
11
12
13
int main(){
BiTree t,p;
printf("请输入结点:\n");
Create(&t);
printf("递归-中序遍历是:");
Inthreading(t);
printf("\n");
printf("迭代-中序遍历是:");
Inorderthread(t,&p);
Inorderthreading(p);
printf("\n");
return 0;
}

主要问题

这个也绕了我好久,主要问题是

  • 指向指针的指针,出了问题!
  • 递归增加线索,出了问题!

总代码

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

#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof(struct BiTNode)

typedef enum{link,thread} NodeState;
typedef struct BiTNode{
char data;
struct BiTNode *Lchild;
struct BiTNode *Rchild;
NodeState Ltag;
NodeState Rtag;
}BiTNode,*BiTree;

BiTree pre;

void Create(BiTree *tempTree){
char tempC;
scanf("%c",&tempC);
if(tempC=='#'){
*tempTree=NULL;
}else{
*tempTree=(BiTree)malloc(LEN);
(*tempTree)->data=tempC;
(*tempTree)->Ltag=link;
(*tempTree)->Rtag=link;
Create(&(*tempTree)->Lchild);
Create(&(*tempTree)->Rchild);
}
}

void Inthread(BiTree t){
if(t){
Inthread(t->Lchild);

if(!t->Lchild){
t->Ltag=thread;
t->Lchild=pre;
}

if(!pre->Rchild){
pre->Rtag=thread;
pre->Rchild=t;
}

pre=t;

Inthread(t->Rchild);
}
}

void Inorderthread(BiTree t , BiTree *p){
*p=(BiTree)malloc(LEN);
(*p)->Rtag=thread;
(*p)->Ltag=link;
(*p)->Rchild=*p;
if(!t){
(*p)->Lchild=*p;
}else{
(*p)->Lchild=t;
pre=*p;
Inthread(t);

pre->Rtag=thread;
pre->Rchild=*p;
(*p)->Rchild=pre;
}
}

void Inthreading(BiTree t){
if(t){
Inthreading(t->Lchild);
printf("%c",t->data);
Inthreading(t->Rchild);
}
}

void Inorderthreading(BiTree t){
BiTree p;
p=t->Lchild;
while(p!=t){
while(p->Ltag==link){
p=p->Lchild;
}
printf("%c",p->data);
while(p->Rtag==thread && p->Rchild!=t){
p=p->Rchild;
printf("%c",p->data);
}
p=p->Rchild;
}
}


int main(){
BiTree t,p;
printf("请输入结点:\n");
Create(&t);
printf("递归-中序遍历是:");
Inthreading(t);
printf("\n");
printf("迭代-中序遍历是:");
Inorderthread(t,&p);
Inorderthreading(p);
printf("\n");
return 0;
}

输出结果:
请输入结点:
ABDH##I##E#J##CF#K##G##
递归-中序遍历是:HDIBEJAFKCG
迭代-中序遍历是:HDIBEJAFKCG

遍历的是上面这棵树。

带注释的总代码

我第二天一早又写了一遍,加了一些注释

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
#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof(struct BiTNode)

typedef enum{link,thread} Nodestate; //着重看一下
typedef struct BiTNode{
char data;
struct BiTNode *Lchild;
struct BiTNode *Rchild;
Nodestate Ltag;
Nodestate Rtag;
}BiTNode,*BiTree;

BiTree pre;

void Create(BiTree *tempt){
char tempc;
scanf("%c",&tempc);

if(tempc=='#'){
*tempt=NULL; //因为 *temp 才是结点
}else{
*tempt=(BiTree)malloc(LEN);
//先赋值
(*tempt)->data=tempc;
//左右孩子的默认状态是链接的
(*tempt)->Ltag=link;
(*tempt)->Rtag=link;
//接着用递归的方式先输入左子树再输入右子树,这种前序遍历
Create(&(*tempt)->Lchild);
Create(&(*tempt)->Rchild);
}
}


//给上面的二叉树创建线索
void Inthread(BiTree t){
if(t){
//因为是用中序给树增加线索,所以先递归左孩子
Inthread(t->Lchild);

if(!t->Lchild){
//如果中间根结点左孩子为空,状态改变
t->Ltag=thread;
t->Lchild=pre; //这里的 pre 记录的是 t 的前驱结点
}

if(!pre->Rchild){
//因为没法用该结点判断右孩子,所以用前驱判断,如果右孩子为空
pre->Rtag=thread;
pre->Rchild=t; //如果前驱的右孩子为空,那么前驱的左右都指向当前结点
}

pre=t; //让前驱向后移动一位

Inthread(t->Rchild); //完成左中右的遍历过程
}
}

//创建根的 pre

void Inorderthread(BiTree t , BiTree *p){
*p=(BiTree)malloc(LEN);
//右孩子等于 thread,并且指向自己
(*p)->Rchild=*p;
(*p)->Rtag=thread;
//左孩子为连通,等下指向树的根
(*p)->Ltag=link;

if(!t){
(*p)->Lchild=*p;
}else{
//把 p 的左子树指向 t 树的根
(*p)->Lchild=t;
pre=*p; //pre 就是这个指向根的结点
Inthread(t); //有了 pre,开始给树增加线索

//收尾,此时 pre 是最后一个结点
pre->Rtag=thread;
pre->Rchild=*p;
(*p)->Rchild=pre;
}
}

//开始递归中序遍历
void Invisit(BiTree t){
if(t){
Invisit(t->Lchild);
printf("%c",t->data);
Invisit(t->Rchild);
}
}

//开始迭代中序遍历
void Inthreading(BiTree t){
BiTree p;
p=t->Lchild;
//如果转到 t,那么证明指回根节点了,转了一圈了
while(p!=t){
//如果左边是连通的,那么向下
while(p->Ltag==link){
p=p->Lchild;
}

printf("%c",p->data);

while(p->Rtag==thread && p->Rchild!=t){
p=p->Rchild;
printf("%c",p->data);
}

p=p->Rchild;
}
}

int main(){
BiTree t,p;
printf("请输入结点:\n");
Create(&t);
printf("递归-中序遍历:");
Invisit(t);
printf("\n");
printf("迭代-中序遍历:");
Inorderthread(t,&p);
Inthreading(p);
printf("\n");
}

尾巴

这是我的个人学习笔记,主要是应付考研复习使用,充斥着一些吐槽和个人观点,并不严谨,欢迎大家参考、指正。


-------------The End-------------
欢迎请我喝咖啡哦~!