主题:中序遍历线索二叉树,得不到正确的输出?大侠们帮着看看
#include <stdio.h>
#include <malloc.h>
#define OK 1
#define ERROR 0
#define NULL 0
typedef int ElemType;
typedef int Status;
typedef struct BiThrNode
{ElemType data;
struct BiThrNode *lchild,*rchild;
int ltag,rtag;
}BiThrNode,*BiThrTree;
BiThrTree pre=NULL;
Status CreateBiThrTree(BiThrTree &T)
{//创建二叉链表
char ch;
scanf("%c",&ch); getchar();
if(ch==' ') T=NULL;
else
{T=(BiThrTree)malloc(sizeof(BiThrNode));
if(!T) return ERROR;
T->data=ch;
printf("%c的左结点为:",ch);
CreateBiThrTree(T->lchild);
printf("%c的右结点为:",ch);
CreateBiThrTree(T->rchild);
}
return OK;
}
void InThreading(BiThrTree p)
{if(p)
{InThreading(p->lchild);
if(!p->lchild){p->ltag=1;p->lchild=pre;}
if(!pre->rchild) {pre->rtag=1;pre->rchild=p;}
printf("当前访问的结点为:%c\n",p->data);
pre=p;
InThreading(p->rchild);}
}
Status InOrderThreading(BiThrTree &Thrt,BiThrTree T)
{//对带头结点的二叉链表进行中序线索化
Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
if(!Thrt) return ERROR;
Thrt->ltag=0; Thrt->rtag=1;
Thrt->rchild=Thrt;
if(!T) Thrt->lchild=Thrt;
else
{Thrt->lchild=T; pre=Thrt;
InThreading(T);
pre->rchild=Thrt; pre->rtag=1;
Thrt->rchild=pre;
}
return OK;
}
Status InOrderTraverse_Thr(BiThrTree Thrt)
{//中序遍历线索二叉树非递归算法
BiThrTree p;
p=Thrt->lchild;
while(p!=Thrt)
{while(p->ltag==0) p=p->lchild;
printf("%2c",p->data);
while(p->rtag==1 && p->rchild!=Thrt)
{p=p->rchild;printf("%2d",p->data);}
p=p->rchild;
}
return OK;
}
main()
{BiThrTree T,Thrt;
printf("---------创建二叉树--------------\n");
printf("输入第一个结点:\n");
CreateBiThrTree(T);
printf("---------中序线索化二叉树---------------------\n");
InOrderThreading(Thrt,T);
printf("\n");
InOrderTraverse_Thr(Thrt);
printf("\n");
}
#include <malloc.h>
#define OK 1
#define ERROR 0
#define NULL 0
typedef int ElemType;
typedef int Status;
typedef struct BiThrNode
{ElemType data;
struct BiThrNode *lchild,*rchild;
int ltag,rtag;
}BiThrNode,*BiThrTree;
BiThrTree pre=NULL;
Status CreateBiThrTree(BiThrTree &T)
{//创建二叉链表
char ch;
scanf("%c",&ch); getchar();
if(ch==' ') T=NULL;
else
{T=(BiThrTree)malloc(sizeof(BiThrNode));
if(!T) return ERROR;
T->data=ch;
printf("%c的左结点为:",ch);
CreateBiThrTree(T->lchild);
printf("%c的右结点为:",ch);
CreateBiThrTree(T->rchild);
}
return OK;
}
void InThreading(BiThrTree p)
{if(p)
{InThreading(p->lchild);
if(!p->lchild){p->ltag=1;p->lchild=pre;}
if(!pre->rchild) {pre->rtag=1;pre->rchild=p;}
printf("当前访问的结点为:%c\n",p->data);
pre=p;
InThreading(p->rchild);}
}
Status InOrderThreading(BiThrTree &Thrt,BiThrTree T)
{//对带头结点的二叉链表进行中序线索化
Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
if(!Thrt) return ERROR;
Thrt->ltag=0; Thrt->rtag=1;
Thrt->rchild=Thrt;
if(!T) Thrt->lchild=Thrt;
else
{Thrt->lchild=T; pre=Thrt;
InThreading(T);
pre->rchild=Thrt; pre->rtag=1;
Thrt->rchild=pre;
}
return OK;
}
Status InOrderTraverse_Thr(BiThrTree Thrt)
{//中序遍历线索二叉树非递归算法
BiThrTree p;
p=Thrt->lchild;
while(p!=Thrt)
{while(p->ltag==0) p=p->lchild;
printf("%2c",p->data);
while(p->rtag==1 && p->rchild!=Thrt)
{p=p->rchild;printf("%2d",p->data);}
p=p->rchild;
}
return OK;
}
main()
{BiThrTree T,Thrt;
printf("---------创建二叉树--------------\n");
printf("输入第一个结点:\n");
CreateBiThrTree(T);
printf("---------中序线索化二叉树---------------------\n");
InOrderThreading(Thrt,T);
printf("\n");
InOrderTraverse_Thr(Thrt);
printf("\n");
}