线索二叉树-C语言实现
线索二叉树的定义
在二叉链表中, 具有 n 个结点的二叉链表有 n + 1 个空指针域. 由此, 可以利用这些空指针域来存放结点的直接前驱和直接后继的信息
结点的存储结构
lchild | ltag | data | rtag | rchild |
---|---|---|---|---|
左孩子结点 | 前驱结点标志域 | 数据域 | 后继结点标志域 | 右孩子结点 |
含义
当 ltag = 0 时, lchild 指向结点的左孩子;
当 ltag = 1 时, lchild 指向结点的直接前驱;
当 rtag = 0 时, rchild 指向结点的右孩子;
当 rtag = 1 时, rchild 指向结点的直接后继
二叉树的线索化图解
线索二叉树的实现
线索二叉树的定义
//定义一个线索二叉树
typedef enum { Linked, Thread } PointTag;
typedef struct Node {
char data;
struct Node* lchild;
struct Node* rchild;
PointTag ltag;
PointTag rtag;
}BitNode, *BiTree;
创建一个二叉树
//创建一个二叉树
void CreateBiTree(BiTree* T) {
char ch = 0;
scanf("%c", &ch);
if (ch == ' ') {
*T = NULL;
} else {
*T = (BiTree)malloc(sizeof(BitNode));
if (!(*T)) {
exit(-1);
}
(*T)->data = ch;
CreateBiTree(&((*T)->lchild));
CreateBiTree(&((*T)->rchild));
}
}
中序线索化二叉树
//中序线索二叉树
BiTree pre; //始终指向已经线索化的结点
void InThreading(BiTree T) {
if (T) {
InThreading(T->lchild);
if (!T->lchild) {
T->ltag = Thread;
T->lchild = pre;
} else {
T->ltag = Linked;
}
if (!pre->rchild) {
pre->rtag = Thread;
pre->rchild = T;
} else {
pre->rtag = Linked;
}
pre = T;
InThreading(T->rchild);
}
}
void InOrderThreading(BiTree* Thrt, BiTree T) {
if (!T) {
return;
}
//创建头结点
*Thrt = (BiTree)malloc(sizeof(BitNode));
if (!(*Thrt)) {
exit(-1);
}
//将头结点初始化
(*Thrt)->ltag = Linked;
(*Thrt)->rtag = Thread;
(*Thrt)->lchild = T;
(*Thrt)->rchild = *Thrt;
//始终指向已经线索化的结点
pre = *Thrt;
//进行中序线索化
InThreading(T);
//将最后一个结点线索化
pre->rtag = Thread;
pre->rchild = *Thrt;
(*Thrt)->rchild = pre;
}
中序遍历线索化二叉树
//中序遍历线索化二叉树
void InOrderTraverse(BiTree Thrt) {
//指向根结点
BiTree p = Thrt->lchild;
//p == Thrt 为循环一遍
while (p != Thrt) {
//找到每个子树的第一个结点
while (p->ltag == Linked) {
p = p->lchild;
}
printf("%2c", p->data);
//依次遍历直接后继, 直到转移到右子树或者遍历结束
while (p->rtag == Thread && p->rchild != Thrt) {
p = p->rchild;
printf("%2c", p->data);
}
//转移到右子树
p = p->rchild;
}
printf("\n");
}
寻找某个结点的直接前驱
//寻找某个结点的直接前驱
BiTree InOrderPre(BiTree T) {
if (T->ltag == Thread) {
return T->lchild;
}
//找到左子树
BiTree p = T->lchild;
//找到左子树中最后遍历的结点
while (p->rtag == Linked) {
p = p->rchild;
}
return p;
}
寻找某个结点的直接后继
//寻找某个结点的直接后继
BiTree InOrderNext(BiTree T) {
if (T->rtag == Thread) {
return T->rchild;
}
//找到右子树
BiTree p = T->rchild;
//找到右子树中最先遍历的结点
while (p->ltag == Linked) {
p = p->lchild;
}
return p;
}
销毁线索化二叉树
//销毁线索化二叉树
void Destroy(BiTree* Thrt) {
//p 指向根结点
BiTree p = (*Thrt)->lchild;
BiTree adjust = p;
while (p != *Thrt) { //p 指向头结点代表遍历结束
//找到中序遍历的第一个结点
while (p->ltag == Linked) {
p = p->lchild;
}
//调整指针adjust指向p指向的结点
//p指向直接后继(即子树的根结点)
//释放掉adjust结点(左孩子)的内存空间
while (p->rtag == Thread && p->rchild != *Thrt) {
adjust = p;
p = p->rchild;
free(adjust);
}
//更新adjust
adjust = p;
//p最后再指向右孩子
p = p->rchild;
//释放掉adjust(子树根结点)的内存空间
free(adjust);
}
//最后释放头结点
free(*Thrt);
//给野指针赋值
*Thrt = NULL;
adjust = p = NULL;
}
测试
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <windows.h>
int main() {
BiTree T1, Thrt;
CreateBiTree(&T1);
InOrderThreading(&Thrt, T1);
printf("**************************\n");
InOrderTraverse(Thrt);
Destroy(&Thrt);
printf("**************************\n");
if (!Thrt) {
printf("OK\n");
}
system("pause");
return 0;
}
效果图
希望本片文章能对大家有所帮助
欢迎大家的评论和建议