测试结果:
创建二叉树,输入先序扩展序列:ABC##DE#G##F###
中序(递归法):C B E G D F A [用于对比测试]
中序(线索化):C B E G D F A
A
/ \
B #
/ \
C D
/ \ / \
# # E F
/ \ / \
# G # #
/ \
# #
#include
#include
#define ERROR 0
#define OVERFLOW -2
#define OK 1
typedef char SElemType;
typedef enum PointerTag{Link,Thread};
typedef struct BiTNode
{
SElemType data;
struct BiTNode *lchild, *rchild;
PointerTag LTag,RTag;
}BiTNode,*Bitree;
typedef int Status;
Bitree pre;
Status CreateBiTree(Bitree *T)
{
char ch;
scanf("%c",&ch);
//原代码if(ch==' ') //也可以用空格表示空指针
if(ch=='#') //符号#表示空指针
{
(*T)=NULL;
}
else
{
if(!((*T)=(Bitree)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
(*T)->data=ch;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
return OK;
}
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);
}
}
Status InOrderThreading(Bitree & Thrt,Bitree T)
{
if(!(Thrt=(Bitree)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
Thrt->LTag=Link;
Thrt->RTag=Thread;
Thrt->rchild=Thrt;
if(!T)
Thrt->lchild=Thrt;
else
{
Thrt->lchild=T;
pre=Thrt;
InThreading(T);
pre->rchild=Thrt;
pre->RTag=Thread;
Thrt->rchild=pre;
}
return OK;
}
Status InOrderTraverse_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;
}
return OK;
}
void inOrder(Bitree T)
{
if(T!=NULL)
{
inOrder(T->lchild);
printf("%c ",T->data);
inOrder(T->rchild);
}
}
int main()
{
Bitree T;
Bitree temp;
CreateBiTree(&T);
printf("中序(递归法):");
inOrder(T);
printf("\n");
InOrderThreading(temp,T);
//原代码InOrderTraverse_Thr( T);
printf("中序(线索化):");
InOrderTraverse_Thr(temp); //将输入参数 T 改为 temp
printf("\n");
return 0;
}