中序线索二叉树
/* 线索二叉树 */
#include "stdio.h"
#include "stdlib.h"
typedef char Datatype;
typedef struct BinThrNode{
Datatype data;
unsigned ltag,rtag;
struct BinThrNode *lchild, *rchild;
}BinThrTree,*PBinThrTree;
PBinThrTree pre=NULL;
PBinThrTree CreatBinTNode(){ /* 建立二叉树 */
PBinThrTree T;
Datatype ch;
scanf("%c",&ch);
if(ch=='@') {T=NULL;return T;}
else
{
T=(PBinThrTree)malloc(sizeof(BinThrTree) );
T->data=ch;
T->lchild=CreatBinTNode();
if(T->lchild) T->ltag=0;
T->rchild=CreatBinTNode();
if(T->rchild) T->rtag=0;
}
return T;
}
void InThreading(PBinThrTree p) // 中序遍历递归线索化算法
{
if(p!=NULL)
{
InThreading(p->lchild); //左子树线索化
if(p->lchild==NULL){ //左孩子为空时 前驱线索
p->ltag=1;
p->lchild=pre;
}
if(!pre->rchild){ //右孩子为空时 后继线索
pre->rtag=1;
pre->rchild=p;
}
pre=p; //保证pre是处理当前结点的前驱
InThreading(p->rchild); //右子树线索化
}
}
PBinThrTree InOrderThr(PBinThrTree T){ // 中序遍历递归线索化
PBinThrTree head;
head=(PBinThrTree)malloc(sizeof(BinThrTree));
head->ltag=0;
head->rtag=1;
head->rchild=head; //右指针回指
if(T){ //二叉树非空，进行线索化
head->lchild=T; //头结点指向树的根
pre=head;
InThreading(T); //从树的根开始线索化
pre->rchild=head; //二叉树的最后一个结点的后继结点指向head
pre->rtag=1;
head->rchild=pre; //head的右孩子指向二叉树的最后一个结点
}
else
head->lchild=head;
return head;
}
PBinThrTree InPreNode(PBinThrTree p){ //在中序线索二叉树上寻找结点p的中序前驱结点
if(p->ltag==1)
return pre=p->lchild;
else{ //p的左孩子存在找左孩子为根结点的子树的最右下结点
p=p->lchild;
while(p->rtag==0) //找到rtag==1时为止
p=p->rchild;
}
return pre=p;
}
PBinThrTree SuccNode(PBinThrTree p){ //在中序线索二叉树上寻找结点p的中序后继结点
if(p->rtag==1) //p的右孩子指针是线索
return p->rchild;
p=p->rchild;
while(p->ltag==0) //p的右孩子存在 没右子树的左指针向下找，找到结点的ltag==1为止
p=p->lchild;
return p;
}
void InOrder(PBinThrTree root) // 中序遍历
{
if(root!=NULL)
{
InOrder(root->lchild);
printf("%c ",root->data);
InOrder(root->rchild);
}
}
void InOrderTraversalThr(PBinThrTree T){ //中序线索二叉树遍历
PBinThrTree p;
p=T->lchild; //p指向树的垠
while(p->ltag==0)
p=p->lchild;
while(p!=T)
{
printf("%c ",p->data);
p=SuccNode(p);
}
}
void main()
{
PBinThrTree T,L,p;
printf("用先序遍历建立二叉树，空的用@补全：\n");
T=CreatBinTNode();
printf("二
叉树的中序遍历为 :");
InOrder(T);
printf("\n二叉树的中序线索遍历为 :");
L=InOrderThr(T);
InOrderTraversalThr(L);
p=InPreNode(T);
printf("\n%c的前驱是%c ",T->data,p->data);
p=SuccNode(T);
printf("\n%c的后继是%c ",T->data,p->data);
}