Question

新人求解，C语言中根线索树上查找前驱结点的问题

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef int ElemType;
typedef struct Btnode /*二叉树结点结构*/
{ElemType data;
struct Btnode *lch,*rch;
int ltag,rtag;
}Btnode;

Btnode *creat_bt0();
void preorder(Btnode *p);
void inthread(Btnode *p);
Btnode * inthorder(Btnode *t,int n);
Btnode *inpre(Btnode *q);
Btnode *insucc(Btnode *q);

Btnode *t,*p,*q,*pr,*r;
int z,i,j,k,e,m,n,a,g,x,y;

void main()
{do{printf("\n\n");
printf("\n\n==线索二叉树--主菜单===");
printf("\n\n 0.建立二叉树 ");
printf("\n\n 1.中根线索化递归 ");
printf("\n\n 2.中根线索树上查找前驱结点 ");
printf("\n\n 3.结束程序运行 ");
printf("\n===================================");
printf("\n 请输入您的选择(0,1,2,3,4,)：");scanf("%d",&k);
switch(k)
{case 0:{printf("\n s输入(0 0)结束:");
t=creat_bt0();
preorder(t);
}break;
case 1:{printf("\n 递归中根线索化:");inthread(t);
}break;
case 2:{ printf(" 请输入要查找前趋结点的结点：n = ");scanf("%d",&n);
printf("所找结点前趋结点为m=%d",inpre(inthorder(t,n))->data);
}break;
case 3:exit(0);
}
printf("\n----------------");
}while(k>=0&&k <6);
printf("\n 再见！");scanf("%d",&z);
}/*main*/

Btnode *creat_bt0() /*利用二叉树性质5，借助一维数组V建立二叉树*/
{Btnode *t,*p,*v[20];
printf("\n i data=");scanf("%d%d",&i,&e);
while(i!=0&&e!=0)
{p=(Btnode *)malloc(sizeof(Btnode));
p->data=e;p->lch=NULL;p->rch=NULL;
v[i]=p;
if(i==1)t=p;
else{j=i/2;
if(i%2==0)v[j]->lch=p; else v[j]->rch=p;
}
printf("\n i data=");scanf("%d%d",&i,&e);
}
return(t);
}/*creat_bt0*/

void preorder(Btnode *p)
{if(p!=NULL){ printf("%6d",p->data);
preorder(p->lch);
preorder(p->rch);
}
}/*preorder*/

void inthread(Btnode *p)
{if(p!=NULL)
{inthread(p->lch);
printf("%6d",p->data);
inthread(p->rch);
if(p->lch!=NULL) p->ltag=0;
else{p->ltag=1;
p->lch=pr;
}
if(pr!=NULL)
{if(pr->rch!=NULL) pr->rtag=0;
else{pr->rtag=1;
pr->rch=p;
}
}
pr=p;/*maybe null*/
}
}/*inthread*/

Btnode * inthorder(Btnode *t,int n)
{
p = t;
Btnode * t0=NULL;
if(p!=NULL)
while(p->lch!=NULL) p=p->lch;
printf("\n %6d",p->data);
while(p->rch!=NULL){p=insucc(p);
printf("%6d",p->data);
if (p->data==n)
t0=p;
}
return(t0);
}

Btnode *inpre(Btnode *q)
{Btnode *p;
if(q->ltag==1) p=q->lch;
else{r=q->lch;
while(r->rtag!=1) r=r->rch;
p=r;
}
return(p);
}

Btnode *insucc(Btnode *q)
{Btnode *p;
if(q->rtag==1) p=q->rch;
else {r=q->rch;
while(r->ltag!=1) r=r->lch;
p=r;
}
return(p);
}

这个代码有什么问题，就是查找前驱结点的时候变成了无限循环，怎么回事？

Answer 1

是不是你建的二叉树没有建队 建成了循环队列