线索二叉树
/*作者邮箱地址:[email protected]*/ 线索二叉树定义:n 个结点的二叉链表中含有n+1(2n-(n-1)=n+1)个空指针域。利用二叉链表中的空指针域,存放指向结点在某种遍历次序下的前趋和后继结点的指针(这种附加的指针称为" 线索" )。 构建:
建立线索二叉树,或者说对二叉树线索化,实质上就是遍历一颗二叉树。在遍历过程中,访问结点的操作是检查当前的左,右指针域是否为空,将它们改为指向前驱结点或后续结点的线索。为实现这一过程,设指针pre 始终指向刚刚访问的结点,即若指针p 指向当前结点,则pre 指向它的前驱,以便设线索。
#include "stdio.h"
#include "stdlib.h"
typedef enum//枚举类型
{
Link,//默认值为0
Thread//默认值为1
}PointerTag;
typedef struct BitNode//树的结点结构
{
char data;
struct BitNode *lchild,*rchild;
PointerTag ltag;//用于标识该结点是否线索,若是,值为Link, 否则值为Thread PointerTag rtag;
}BitNode,*BiTree;
BitNode * pre;//全局变量,用来存储上一个访问的结点地址
void CreateTree(BiTree *t)//利用递归原理创建二叉树
{
char ch;
scanf("%c",&ch);
if(ch==' ')
*t=NULL;
else
{
*t=(BiTree)malloc(sizeof(BitNode));
if(!(*t))
exit(0);
(*t)->data=ch;
(*t)->ltag=(*t)->rtag=Link;//先将所有标志赋值为Link
CreateTree(&(*t)->lchild);
CreateTree(&(*t)->rchild);
}
}
void InThreading(BiTree p)//中序线索二叉树
{
if(p)
{
InThreading(p->lchild);//利用递归原理,跟遍历二叉树原理差不多 if(!p->lchild)
{
p->ltag=Thread;
p->lchild=pre;
}
if(!pre->rchild)
{
pre->rtag=Thread;
pre->rchild=p;
}
pre=p;//把当前访问结点代替访问前一个结点
InThreading(p->rchild);
}
}
void InOrderThread_Head(BiTree *h,BiTree t)/*为二叉树创建头结点,头结点左指针指向二叉树的根,右指针暂且指向本身*/
{
(*h)=(BiTree)malloc(sizeof(BitNode));
if(*h==NULL)
exit(0);
(*h)->rtag=Link;
(*h)->rchild=*h;
if(!t)//如果二叉树为空
{
(*h)->lchild=*h;
(*h)->ltag=Link;
}
else
{
pre=*h;//把存储访问前一个结点变量赋予初始值
(*h)->lchild=t;//头结点指向二叉树的根
(*h)->ltag=Link;
InThreading(t);//中序线索二叉树
pre->rchild=*h;
pre->rtag=Thread;/*把中序线索二叉树得到的序列最好一个结点的右指针指向头结点*/
(*h)->rchild=pre;
}
}
void InOrderThraverse_Thr(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;//指向二叉树根结点
BiTree temp;//指向头结点
printf("请输入二叉树的内容:");
CreateTree(&t);//前序遍历创建二叉树
InOrderThread_Head(&temp,t);//为二叉树创建头结点
printf("输出中序二叉树的内容:");
InOrderThraverse_Thr(temp);//中序遍历输出二叉树
printf("\n");
return 0;
}