线索二叉树

发布网友发布时间：2022-03-31 18:17

共1个回答

热心网友时间：2022-03-31 19:46

#include"stdio.h"
#include"stdlib.h"
#include"string.h"
typedef struct Threadnode {
int ltag,rtag;
char date[20];
struct Threadnode *lchild, *rchild;
} Threadnode, *ThreadTree;
ThreadTree pre=NULL;
void visite(char * ch)
{
printf("\n输出节点信息:");
printf("%s",ch);

}
//初始化二叉树

ThreadTree CreatThreadTree(char ch[])
{
ThreadTree t;
char ch1[20],ch2[20];

t=( ThreadTree )malloc(sizeof(Threadnode));
strcpy(t->date,ch);
printf("\n请输入左子树的数值，结束输入0:\n");
scanf("%s",ch1);
if(strcmp(ch1,"0")==0)
{
t->ltag=1;
t->lchild=NULL;
}
else
{ t->ltag=0;
t->lchild=CreatThreadTree(ch1);
}
printf("\n请输入右子树的数值，结束输入0:\n");
scanf("%s",ch2);
if(strcmp(ch2,"0")==0)
{
t->rtag=1;
t->rchild=NULL;
}
else
{t->rtag=0;
t->rchild=CreatThreadTree(ch2);
}

return t;
}
//建立中序线索二叉树算法实现

void InThread (ThreadTree t)
{ if (t)
{ InThread(t->lchild);
if (t->lchild==NULL)
{ t->ltag=1; t->lchild=pre; }
if (t->rchild==NULL)
t->rtag=1;
if ((pre)&&(pre->rtag==1))
pre->rchild=t;
pre=t;
InThread (t->rchild); }
}
//在中序线索二叉树上寻找结点p的中序后继结点的算法:
ThreadTree InPostNode(ThreadTree p)
{ ThreadTree post;
post=p->rchild;
if (p->rtag==0)
while (post->ltag==0) post=post->lchild;

return (post);
}
// 在中序线索二叉树上查找值为X的结点

ThreadTree Search (ThreadTree t,char x[] )
{ ThreadTree p;
p=t;
if (p)
{ while (p->ltag==0) p=p->lchild;
while (p&&strcmp(p->date,x)!=0)
p= InPostNode (p);
}

return p;
}
//在中序线索二叉树上寻找结点p的中序前驱结点的算法：
ThreadTree InPreNode(ThreadTree p)
{ ThreadTree prel;
prel=p->lchild;
if (p->ltag==0)
while (prel->rtag==0) prel= prel->rchild;
printf("\n结点p的中序前驱结点信息！\n");
visite(prel->date);
return(prel);
}
// 中序线索二叉树的遍历算法
void InOrderTh ( ThreadTree t)
{ ThreadTree p;
if (t)
{ p=t;
while (p->ltag==0) p=p->lchild;
while (p)
{ visite(p->date);
p= InPostNode (p);
}
}
}

void main()
{
ThreadTree t,p;
char ch[20],x[20];
int flag=1;
while(flag){
printf("\n请选择需要进行的操作:\n");
printf("\n1：创建二叉树\n");
printf("\n2：线索二叉树\n");
printf("\n3：中序线索二叉树\n");
printf("\n4：寻找结点p的中序前驱结点\n");
printf("\n5：寻找结点p的中序后继结点\n");
printf("\n6：查找值为X的结点\n");
printf("\n0：退出！\n\n");
scanf("%d",&flag);

switch(flag){

case 1 :
printf("\n开始创建二叉树\n");
printf("\n请输入一个数值:");
scanf("%s",ch);
t=CreatThreadTree(ch);
printf("\n\n\n\n\n");break;
case 2:
printf("\n开始线索二叉树！\n");
InThread (t) ;break;
case 3:
printf("\n中序线索二叉树！\n");
InOrderTh ( t) ;break;
case 4://在中序线索二叉树上寻找结点p的中序前驱结点的算法：
printf("\n输入P节点信息，以方便查找\n");
scanf("%s",x);
printf("\n寻找结点p的中序前驱结点!\n");
p=Search (t,x) ;
InPreNode( p);
break;
case 5://在中序线索二叉树上寻找结点p的中序后继结点的算法:
printf("\n输入P节点信息，以方便查找!\n");
scanf("%s",x);
printf("\n结点p的中序后继结点信息！\n");

printf("\n寻找结点p的中序后继结点!\n");
p=Search (t,x) ;
p=InPostNode( p);
visite(p->date);
break;
case 6:// 在中序线索二叉树上查找值为X的结点
printf("\n请输入查找的数值！\n");
scanf("%s",x);
p=Search(t,x);
if(p) printf("\n查找成功！\n\n"); else printf("\n查找失败！\n\n");
break;
default:break;
}
if(flag!=0)
printf("\n****************请选择操作*****************\n");
}
}