求助，中序线索化二叉树问题
#include<stdio.h>#include<stdlib.h>
#define MAX_SIZE 100
#define Link 0
#define Thread 1
typedef struct BiThrTreeNode
{
char info;
struct BiThrTreeNode *l_link;
struct BiThrTreeNode *r_link;
int LTag,RTag;
}BiThrTreeNode,*BiThrTree;
typedef struct SeqStack
{
BiThrTree s[MAX_SIZE];
int t;
}*PSeqStack;
PSeqStack createEmptyStack_seq(void)
{
PSeqStack p_stack;
p_stack=(PSeqStack)malloc(sizeof(struct SeqStack));
if(NULL==p_stack)
{
printf("\n out of space!\n");
exit(-1);
}
else
{
p_stack->t=-1;//表示以满堆栈的方式存放数据
}
return p_stack;
}
bool isEmptyStack_seq(PSeqStack p_stack)
{
return p_stack->t==-1;
}
void push_seq(PSeqStack p_stack,BiThrTree bt)
{
if(p_stack->t>=MAX_SIZE-1)
{
printf("\tOverflow!\n");
exit(-1);
++p_stack->t;
p_stack->s[p_stack->t]=bt;
}
}
void pop_seq(PSeqStack p_stack)
{
if(p_stack->t==-1)
{
printf("\tUnderflow!\n");
exit(-1);
}
--p_stack->t;
}
BiThrTree top_seq(PSeqStack p_stack)
{
if(isEmptyStack_seq(p_stack))
{
printf("\tNo data!\n");
}
return p_stack->s[p_stack->t];
}
BiThrTree createBiThrTree() //先序创建二叉树
{
char ch;
BiThrTree T;
scanf("%c",&ch);
if(ch=='#')
T=NULL;
else
{
T=(BiThrTree)malloc(sizeof(BiThrTreeNode));
if(!T)
exit(0);
T->info=ch;
T->LTag=Link;
T->RTag=Link;
T->l_link=createBiThrTree();
T->r_link=createBiThrTree();
}
return T;
}
void thread(BiThrTree bt) //按对称序线索化二叉树
{
PSeqStack p_stack=createEmptyStack_seq();
BiThrTree p,pre;
if(bt==NULL)
return;
p=bt;
pre=NULL;
do
{
while(p!=NULL)
{
push_seq( p_stack,p); //遇到结点推入栈中,然后进入左子树中
p=p->l_link;
}
printf("*****************\n");
p=top_seq(p_stack);
pop_seq(p_stack);
if(pre!=NULL)
{
if(pre->r_link==NULL) //修改前驱结点的右指针
{
pre->r_link=p;
pre->RTag=Thread;
}
if(p->l_link==NULL) //修改前驱结点的左指针
{
p->l_link=pre;
p->LTag=Thread;
}
pre=p;
p=p->r_link; //进入右子树
}
}while(!isEmptyStack_seq(p_stack)||p!=NULL);
}
void visit(BiThrTree bt)
{
printf("%c",bt->info);
}
void InOder(BiThrTree bt) //按对称序遍历对称序线索二叉树
{
BiThrTree p=bt;
if(bt==NULL)
return;
while(p->l_link!=NULL&&p->LTag==Link)
p=p->l_link; //顺左子树一直向下
while(p!=NULL)
{
visit(p);
if(p->r_link!=NULL&&p->RTag==Link)//右子树不是线索时
{
p=p->r_link;
while(p->l_link!=NULL&&p->LTag==Link)
p=p->l_link; //顺右子树的左子树一直向下
}
else
p=p->r_link; //顺线索向下
}
}
int main()
{
BiThrTree bt;
BiThrTree thrNode=NULL;
printf("请按先序遍历序列输入二叉树中各个结点的值(字符)，若为空树时输入#:\n");
printf("<说明：例如参考数据为:abc##de#g##f###,输完后再输入一个回车键.>\n");
bt=createBiThrTree();
printf("中序线索化二叉树:\n");
thread(bt);
printf("线索化工作已经完成!\n");
printf("中序遍历线索二叉树:\n");
InOder(bt);
return 0;
}
程序代码：