首页 / 算法 / 线索二叉树的实现（C语言）
线索二叉树的实现（C语言）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了线索二叉树的实现（C语言），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5170字，纯文字阅读大概需要8分钟。
内容图文
线索二叉树的实现（C语言）
明天就要五一去重庆了，今天在坚持一下把这篇博文写完，也能减轻不少玩的负罪感啦。
线索二叉树
鉴于普通二叉树使用过程中会出现空间的浪费，后人对在在二叉树的的基础上做了改进，利用它的空指针域存放在某种遍历次序下指向它的前驱结点，和后继结点的指针。这些指针称为线索，相应的二叉树就成了线索二叉树。
我们就充分利用二叉链表的空闲结点进行操作，使之充分利用。
也就是在定义结构时外加两个标志域，若结点有左子树，则Lchild指向左孩子，否则指向前驱；若结点有右子树，则Lchild指向右孩子，否则指向后驱。
操作
线索二叉树的建立
///线索二叉树的建立
ThreadTree InitThreadTree(){
char ch;
ThreadTree T;
scanf("%c", &ch);
if(ch == '#') T = NULL;
else{
T = (ThreadTree)malloc(sizeof(ThreadNode));
T->data = ch;
T->lchild = InitThreadTree();
T->rchild = InitThreadTree();
}
return T;
}
线索二叉树的线索化
///线索二叉树的线索化
/*
* 首先如果根节点的lchild为null，那么根节点的lchild为pre为null
* 第二个if的时候，pre不为null的时候才执行，第一次是不执行的
* 根节点的左孩子线索完毕之后，pre就指向了根节点了，然后递归
* 递归之后，指针pre每次都会指向刚刚访问过的节点
* 中序遍历，如果左孩子不为空，就会一直继续处理左孩子知道左孩子为空，然后处理右孩子
*/
void InThread(ThreadTree p,ThreadTree pre){
if(p != NULL){ //p是当前节点，pre是刚访问的节点
InThread(p->lchild, pre); //递归，优化左子树
if(p->lchild == NULL){ //左子树为空，建立前驱线索
p->lchild = pre;
p->ltag = 1;
}
if(pre != NULL && pre->rchild == NULL){
pre->rchild = p; //右子树为空，就建立前驱节点的后及线索
pre->rtag = 1;
}
pre = p; //p刚刚访问过了，则pre = p
InThread(p->rchild, pre); //递归，优化右子树
}
}
void CreateInThread(ThreadTree T){
ThreadTree pre = NULL;
if(T != NULL){
InThread(T, pre);
pre->rchild = NULL; //处理遍历的最后一个节点
pre->rtag = 1;
}
}
线索二叉树的遍历
///线索二叉树的遍历
/*
firstnode是中序遍历下面的第一个访问的节点
nextnode是这个结点在中序遍历下面访问的下一个节点
如果有右子树的链接，则下一个节点就是rchild
如果没有，表示存在右子树，由中序遍历的递归思想，下一个节点就相当于以这个结点的右节点为根节点在中序遍历下面的首节点
nextNode = firstNode(p->rchild);
*/
ThreadTree FirstNode(ThreadTree p){
while(p->ltag == 0) p = p->lchild;
return p;
}
ThreadTree NextNode(ThreadTree p){
if(p->rtag == 0) return FirstNode(p->rchild);
//有右节点，访问以右节点为根的树的第一个节点
else return p->rchild; //rtag为1时候，rchild总是指向下一个
}
void Visit(ThreadTree T){
printf("%c ", T->data);
}
void InOrder(ThreadTree T){
for(ThreadTree p = FirstNode(T); p != NULL; p = NextNode(p))
Visit(p);
}
总体
#include<stdio.h>
#include<stdlib.h>
typedef struct ThreadNode{
char data;
struct ThreadNode * lchild, * rchild;
int ltag, rtag;//0为不建立前驱或后驱，1为建立
}ThreadNode, * ThreadTree;
ThreadTree InitThreadTree();
void InThread(ThreadTree p,ThreadTree pre); //通过中序遍历对二叉树线索化
void CreateInThread(ThreadTree T); //通过中序遍历建立中序二叉树
ThreadTree FirstNode(ThreadTree p); //求中序遍历下的第一个节点
ThreadTree NextNode(ThreadTree p); //求节点p在中序序列下的后一个节点
void Visit(ThreadTree T);
void InOrder(ThreadTree T); //中序遍历
///线索二叉树的建立
ThreadTree InitThreadTree(){
char ch;
ThreadTree T;
scanf("%c", &ch);
if(ch == '#') T = NULL;
else{
T = (ThreadTree)malloc(sizeof(ThreadNode));
T->data = ch;
T->lchild = InitThreadTree();
T->rchild = InitThreadTree();
}
return T;
}
///线索二叉树的线索化
/*
* 首先如果根节点的lchild为null，那么根节点的lchild为pre为null
* 第二个if的时候，pre不为null的时候才执行，第一次是不执行的
* 根节点的左孩子线索完毕之后，pre就指向了根节点了，然后递归
* 递归之后，指针pre每次都会指向刚刚访问过的节点
* 中序遍历，如果左孩子不为空，就会一直继续处理左孩子知道左孩子为空，然后处理右孩子
*/
void InThread(ThreadTree p,ThreadTree pre){
if(p != NULL){ //p是当前节点，pre是刚访问的节点
InThread(p->lchild, pre); //递归，优化左子树
if(p->lchild == NULL){ //左子树为空，建立前驱线索
p->lchild = pre;
p->ltag = 1;
}
if(pre != NULL && pre->rchild == NULL){
pre->rchild = p; //右子树为空，就建立前驱节点的后及线索
pre->rtag = 1;
}
pre = p; //p刚刚访问过了，则pre = p
InThread(p->rchild, pre); //递归，优化右子树
}
}
void CreateInThread(ThreadTree T){
ThreadTree pre = NULL;
if(T != NULL){
InThread(T, pre);
pre->rchild = NULL; //处理遍历的最后一个节点
pre->rtag = 1;
}
}
///线索二叉树的遍历
/*
firstnode是中序遍历下面的第一个访问的节点
nextnode是这个结点在中序遍历下面访问的下一个节点
如果有右子树的链接，则下一个节点就是rchild
如果没有，表示存在右子树，由中序遍历的递归思想，下一个节点就相当于以这个结点的右节点为根节点在中序遍历下面的首节点
nextNode = firstNode(p->rchild);
*/
ThreadTree FirstNode(ThreadTree p){
while(p->ltag == 0) p = p->lchild;
return p;
}
ThreadTree NextNode(ThreadTree p){
if(p->rtag == 0) return FirstNode(p->rchild);
//有右节点，访问以右节点为根的树的第一个节点
else return p->rchild; //rtag为1时候，rchild总是指向下一个
}
void Visit(ThreadTree T){
printf("%c ", T->data);
}
void InOrder(ThreadTree T){
for(ThreadTree p = FirstNode(T); p != NULL; p = NextNode(p))
Visit(p);
}
int main()
{
ThreadNode *T=(ThreadNode*)malloc(sizeof(ThreadNode));
T=InitThreadTree();
InThread(T,NULL);
InOrder(T);
return 0;
}
内容总结
以上是互联网集市为您收集整理的线索二叉树的实现（C语言）全部内容，希望文章能够帮你解决线索二叉树的实现（C语言）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】