一 概述
1
2
| 1.中序正/反向遍历双向线索二叉树
2.示例代码
|
二 中序正/反向遍历双向线索二叉树
2.1 中序正反向遍历双向线索二叉树
说明
1
2
| 双向线索二叉树遍历时，如果正向遍历，就从树的根结点开始。
整个遍历过程结束的标志是：当从头结点出发，遍历回头结点时，表示遍历结束。
|
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| //中序正向遍历双向线索二叉树
void InOrderThraverse_Thr(BiThrTree h) {
BiThrTree p;
p = h->lchild; //p 指向根结点
while(p != h) {
while(p->Ltag == Link) { //当 ltag = 0 时循环到中序序列的第一个结点
p = p->lchild;
}
printf("%c ", p->data); //显示结点数据，可以更改为其他对结点的操作
while(p->Rtag == Thread && p->rchild != h) {
p = p->rchild;
printf("%c ", p->data);
}
p = p->rchild; //p 进入其右子树
}
}
|
2.2 中序反向遍历双向线索二叉树
说明
1
| 逆向遍历线索二叉树的过程即从头结点的右指针指向的结点出发，逐个寻找直接前趋结点，结束标志同正向遍历一样：
|
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| //中序逆方向遍历线索二叉树
void InOrderThraverse_Thr(BiThrTree h) {
BiThrTree p;
p=h->rchild;
while (p!=h) {
while (p->Rtag==Link) {
p=p->rchild;
}
printf("%c",p->data);
//如果 lchild 为线索，直接使用，输出
while (p->Ltag==Thread && p->lchild !=h) {
p=p->lchild;
printf("%c",p->data);
}
p=p->lchild;
}
}
|
三 示例代码
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
| include <stdio.h>
#include <stdlib.h>
#define TElemType char//宏定义，结点中数据域的类型
//枚举，Link 为 0，Thread 为 1
typedef enum {
Link,
Thread
} PointerTag;
//结点结构构造
typedef struct BiThrNode {
TElemType data;//数据域
struct BiThrNode* lchild,*rchild;//左孩子，右孩子指针域
PointerTag Ltag,Rtag;//标志域，枚举类型
} BiThrNode,*BiThrTree;
BiThrTree pre=NULL;
//采用前序初始化二叉树
//中序和后序只需改变赋值语句的位置即可
void CreateTree(BiThrTree * tree) {
char data;
scanf("%c",&data);
if (data!='#') {
if (!((*tree)=(BiThrNode*)malloc(sizeof(BiThrNode)))) {
printf("申请结点空间失败");
return;
} else {
(*tree)->data=data;//采用前序遍历方式初始化二叉树
CreateTree(&((*tree)->lchild));//初始化左子树
CreateTree(&((*tree)->rchild));//初始化右子树
}
} else {
*tree=NULL;
}
}
//中序对二叉树进行线索化
void InThreading(BiThrTree p) {
//如果当前结点存在
if (p) {
InThreading(p->lchild);//递归当前结点的左子树，进行线索化
//如果当前结点没有左孩子，左标志位设为 1，左指针域指向上一结点 pre
if (!p->lchild) {
p->Ltag=Thread;
p->lchild=pre;
}
//如果 pre 没有右孩子，右标志位设为 1，右指针域指向当前结点。
if (pre&&!pre->rchild) {
pre->Rtag=Thread;
pre->rchild=p;
}
pre=p;//pre 指向当前结点
InThreading(p->rchild);//递归右子树进行线索化
}
}
//建立双向线索链表
void InOrderThread_Head(BiThrTree *h, BiThrTree t) {
//初始化头结点
(*h) = (BiThrTree)malloc(sizeof(BiThrNode));
if((*h) == NULL) {
printf("申请内存失败");
return ;
}
(*h)->rchild = *h;
(*h)->Rtag = Link;
//如果树本身是空树
if(!t) {
(*h)->lchild = *h;
(*h)->Ltag = Link;
} else {
pre = *h;//pre 指向头结点
(*h)->lchild = t;//头结点左孩子设为树根结点
(*h)->Ltag = Link;
InThreading(t);//线索化二叉树，pre 结点作为全局变量，线索化结束后，pre 结点指向中序序列中最后一个结点
pre->rchild = *h;
pre->Rtag = Thread;
(*h)->rchild = pre;
}
}
//中序正向遍历双向线索二叉树
void InOrderThraverse_Thr(BiThrTree h) {
BiThrTree p;
p = h->lchild; //p 指向根结点
while(p != h) {
while(p->Ltag == Link) { //当 ltag = 0 时循环到中序序列的第一个结点
p = p->lchild;
}
printf("%c ", p->data); //显示结点数据，可以更改为其他对结点的操作
while(p->Rtag == Thread && p->rchild != h) {
p = p->rchild;
printf("%c ", p->data);
}
p = p->rchild; //p 进入其右子树
}
}
int main() {
BiThrTree t;
BiThrTree h;
printf("输入前序二叉树:\n");
CreateTree(&t);
InOrderThread_Head(&h, t);
printf("输出中序序列:\n");
InOrderThraverse_Thr(h);
return 0;
}
|
运行结果：
1
2
3
4
| 输入前序二叉树:
124###35##6##
输出中序序列:
4 2 1 5 3 6
|
程序中只调用了正向遍历线索二叉树的代码，如果逆向遍历，直接替换逆向遍历的函数代码到程序中即可。
四 参考