二叉树前、中、后线索化及遍历程序,没报错,但没结果,求解释!!!!
#include "stdio.h"#include "stdlib.h"
#define NULL 0
typedef char TElemType;
typedef int status;
typedef enum{Link,Thread}PointTag;
typedef struct BiThrNode{
TElemType data;
struct BiThrNode *lchild,*rchild;
PointTag LTag,RTag;
}BiThrNode,*BiThrTree;
BiThrTree pre,p;
status CreateBiTree(BiThrTree *T)
{
char ch;
fflush(stdin);//加入清空缓冲
ch=getchar();
if(ch=='#')
(*T)=NULL;
else{
(*T)=(BiThrTree)malloc(sizeof(BiThrNode));
(*T)->data=ch;
(*T)->LTag=(*T)->RTag=Link;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
return 1;
}
/*void preThreading(BiThrTree p){
if (p)
{
if (p->lchild==NULL)
{
p->LTag=Thread;
p->lchild=pre;
}
if (p->rchild==NULL)
{
p->RTag=Thread;
p->rchild=pre;
}
pre=p;
preThreading(p->lchild);
preThreading(p->rchild);
}
}
void InThreading(BiThrTree p){
if (p)
{
InThreading(p->lchild);
if (p->lchild==NULL)
{
p->LTag=Thread;
p->lchild=pre;
}
if (pre->rchild==NULL)
{
pre->RTag=Thread;
pre->rchild=p;
}
pre=p;
InThreading(p->rchild);
}
}
void postThreading(BiThrTree p){
if (p)
{
postThreading(p->lchild);
postThreading(p->rchild);
if (p->lchild==NULL)
{
p->LTag=Thread;
p->lchild=pre;
}
if (p->rchild==NULL)
{
p->RTag=Thread;
p->rchild=pre;
}
pre=p;
}
}
status PreorderThreading(BiThrTree *Thrt,BiThrTree T)
{
(*Thrt)=(BiThrTree)malloc(sizeof(BiThrNode));
(*Thrt)->LTag=Link;
(*Thrt)->RTag=Thread;
(*Thrt)->rchild=(*Thrt);
if(T==NULL)
(*Thrt)->lchild=(*Thrt);
else{
preThreading(T);
(*Thrt)->lchild=T;
pre=(*Thrt);
pre->RTag=Thread;
(*Thrt)->rchild=pre;
}
return 1;
}
status InorderThreading(BiThrTree *Thrt,BiThrTree T)
{
(*Thrt)=(BiThrTree)malloc(sizeof(BiThrNode));
(*Thrt)->LTag=Link;
(*Thrt)->RTag=Thread;
(*Thrt)->rchild=(*Thrt);
if(T==NULL)
(*Thrt)->lchild=(*Thrt);
else{
(*Thrt)->lchild=T;
pre=(*Thrt);
InThreading(T);
pre->rchild=(*Thrt);
pre->RTag=Thread;
(*Thrt)->rchild=pre;
}
return 1;
}
status postorderThreading(BiThrTree *Thrt,BiThrTree T)
{
(*Thrt)=(BiThrTree)malloc(sizeof(BiThrNode));
(*Thrt)->LTag=Link;
(*Thrt)->RTag=Thread;
(*Thrt)->rchild=(*Thrt);
if(T==NULL)
(*Thrt)->lchild=(*Thrt);
else{
(*Thrt)->lchild=T;
pre=(*Thrt);
pre->rchild=(*Thrt);
pre->RTag=Thread;
InThreading(T);
(*Thrt)->rchild=pre;
}
return 1;
}
status preorderTraverse(BiThrTree Thrt)
{
BiThrTree p;
p=Thrt->lchild;
while (p!=Thrt)
{
printf("%2c\n",p->data);
while(p->LTag==Link) p->lchild;
printf("%2c\n",p->data);
while (p->RTag==Thread&&p->rchild!=Thrt)
{
p=p->rchild;
printf("%2C",p->data);
}
if(p->LTag==Link)p = p->lchild;
else p=p->rchild;
}
return 1;
}
status InorderTraverse(BiThrTree Thrt)
{
BiThrTree p;
p=Thrt->lchild;
while (p!=Thrt)
{
while(p->LTag==Link) p->lchild;
printf("%2c\n",p->data);
while (p->RTag==Thread&&p->rchild!=Thrt)
{
p=p->rchild;
printf("%2C",p->data);
}
p=p->rchild;
}
return 1;
}
BiThrTree parent(BiThrTree thrt,BiThrTree p)
{
BiThrTree temp;
temp=thrt;
if(temp->lchild==p)
return temp; //父节点是头结点
else {
temp=temp->lchild;
while( temp->lchild!=p && temp->rchild!=p )
{
if(Link==temp->RTag)
temp=temp->rchild; //如果节点有右节点,那么往右
else
temp=temp->lchild; //如果节点没有右孩子,那么去左孩子,没有左孩子,去前驱,也是走往左
}
return temp;
}
}
void postorderTraverse(BiThrTree thrt)
{
BiThrTree p;
BiThrTree par;
p=thrt->lchild;
while(1)
{
while(Link==p->LTag)
p=p->lchild;
if(Link==p->RTag)
p=p->rchild;
else break; //p指向第一个被访问的节点
}
while(p!=thrt)
{
printf("%2C",p->data);
par=parent(thrt,p); //parent是p的双亲:
if(thrt==par) //1.若parent是thrt,即p是根节点,则无后继
p=thrt;
else if(p==par->rchild || Thread==par->RTag) //2.若p是双亲的右孩子,或者是独生左孩子,则后继为双亲
p=par;
else {
while(par->RTag==Link) //3.若p是有兄弟的左孩子,则后继为双亲的右子树上按照后续遍历访问的第一个节点。
{
par=par->rchild;
while(par->LTag==Link)
{
par=par->lchild;
}
}
p=par;
}
}
}
void main()
{
BiThrTree T=NULL,Thrt=NULL;
printf("\nCreat a Thread Binary Tree\n");
CreateBiTree(&T);
InorderThreading(&Thrt,T);
InorderTraverse(Thrt);
PreorderThreading(&Thrt,T);
preorderTraverse(Thrt);
postorderThreading(&Thrt,T);
postorderTraverse(Thrt);
}