题目
已知二叉树的先根遍历和中序遍历,求后序遍历的算法?
麻烦详细写出由先根和中根还原出原来二叉树的算法!
麻烦详细写出由先根和中根还原出原来二叉树的算法!
提问时间:2021-03-27
答案
线索二叉树算法
#include
#include
#include
typedef char DataType;/*定义DataType类型*/
typedef enum {Link,Thread}PointerTag;
typedef struct node{
DataType data;
struct node *lchild,*rchild;/*左右孩子子树*/
PointerTag LTag,RTag;
}BiThrNode; /*结点类型*/
typedef BiThrNode *BiThrTree ;/*二叉树类型*/
void CreatBinTree(BiThrTree *T)
{ /*构造二叉链表,注意:输入序列是先序序列*/
char ch;
if ((ch=getchar())==)
*T=NULL;
else{ /*读入非空格*/
*T=(BiThrNode *)malloc(sizeof(BiThrNode));/*生成结点*/
(*T)->data=ch;(*T)->LTag=Link;(*T)->RTag=Link;
CreatBinTree(&(*T)->lchild); /*构造左子树 */
CreatBinTree(&(*T)->rchild); /*构造右子树*/
}
}
BiThrTree pre;/*全局变量*/
void InThreading(BiThrTree 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;/*保持pre指向p*/
InThreading(p->rchild);/*右子树线索化*/
}
}
int InOrderThreading(BiThrTree *Thrt,BiThrTree T)
/*中序遍厉二叉树T,并将其中序线索化,Thrt指向头结点*/
{ if(!(*Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(0);
(*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 1;
}
int print(BiThrTree e)
{printf("%d %c %d ",e->LTag,e->data,e->RTag);return 1;}
int InOrderTraverse(BiThrTree T,int (* visit)(BiThrTree e))
/*T指向头结点,头结点的左链lchild指向根结点,中序遍厉二叉树*/
{BiThrTree p;
p=T->lchild;/*p指向根结点*/
while(p!=T)/*空树或遍厉结束时,p==T*/
{while(p->LTag==Link) p=p->lchild;
if(!visit(p)) return 0;/*打印*/
while(p->RTag==Thread&&p->rchild!=T)
{p=p->rchild;visit(p);}/*访问后继结点*/
p=p->rchild;
}
return 1;
}
void main()
{ /*测试程序*/
BiThrTree T,Thrt;
CreatBinTree(&T);
InOrderThreading(&Thrt,T);
InOrderTraverse(Thrt,print);
}
/*可输入"-+a *b -c d /e f "来测试(注意空格)*/
#include
#include
#include
typedef char DataType;/*定义DataType类型*/
typedef enum {Link,Thread}PointerTag;
typedef struct node{
DataType data;
struct node *lchild,*rchild;/*左右孩子子树*/
PointerTag LTag,RTag;
}BiThrNode; /*结点类型*/
typedef BiThrNode *BiThrTree ;/*二叉树类型*/
void CreatBinTree(BiThrTree *T)
{ /*构造二叉链表,注意:输入序列是先序序列*/
char ch;
if ((ch=getchar())==)
*T=NULL;
else{ /*读入非空格*/
*T=(BiThrNode *)malloc(sizeof(BiThrNode));/*生成结点*/
(*T)->data=ch;(*T)->LTag=Link;(*T)->RTag=Link;
CreatBinTree(&(*T)->lchild); /*构造左子树 */
CreatBinTree(&(*T)->rchild); /*构造右子树*/
}
}
BiThrTree pre;/*全局变量*/
void InThreading(BiThrTree 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;/*保持pre指向p*/
InThreading(p->rchild);/*右子树线索化*/
}
}
int InOrderThreading(BiThrTree *Thrt,BiThrTree T)
/*中序遍厉二叉树T,并将其中序线索化,Thrt指向头结点*/
{ if(!(*Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(0);
(*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 1;
}
int print(BiThrTree e)
{printf("%d %c %d ",e->LTag,e->data,e->RTag);return 1;}
int InOrderTraverse(BiThrTree T,int (* visit)(BiThrTree e))
/*T指向头结点,头结点的左链lchild指向根结点,中序遍厉二叉树*/
{BiThrTree p;
p=T->lchild;/*p指向根结点*/
while(p!=T)/*空树或遍厉结束时,p==T*/
{while(p->LTag==Link) p=p->lchild;
if(!visit(p)) return 0;/*打印*/
while(p->RTag==Thread&&p->rchild!=T)
{p=p->rchild;visit(p);}/*访问后继结点*/
p=p->rchild;
}
return 1;
}
void main()
{ /*测试程序*/
BiThrTree T,Thrt;
CreatBinTree(&T);
InOrderThreading(&Thrt,T);
InOrderTraverse(Thrt,print);
}
/*可输入"-+a *b -c d /e f "来测试(注意空格)*/
举一反三
已知函数f(x)=x,g(x)=alnx,a∈R.若曲线y=f(x)与曲线y=g(x)相交,且在交点处有相同的切线,求a的值和该切线方程.
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
奥巴马演讲不用看稿子.为什么中国领导演讲要看?
想找英语初三上学期的首字母填空练习……
英语翻译
最新试题
- 1森林的小路旁有一个葡萄架,架上挂着一串串葡萄.你认为这些葡萄是酸的还是甜的?我觉得架上的葡萄是 ,因为
- 2长江干流从湖北()到湖南()一段称荆江.这里河道(),水流不畅,被称为(),采取的治理措施主要是(
- 3What are the effects of skyscrapers on environment
- 4已知集合A是不等式x平方-(3a+1)x-(2-3a-2a平方)<0的解集,且2属于A,求a的取值范围及不等式的解集
- 5有小学行程趣题q,急盼详解
- 6第一题:把四分之一,三分之二,十二分之五,二十四分之十五化成分母是48且大小不变的分数
- 7已知函数f(x)=x2/(1+x2),求f(1)+f(2)+f(1/2)+f(3)+f(1/3)+f(4)+f(1/4)的值
- 8天下为公还是天下为私?
- 9词组“listen in on”是什么意思?
- 10、酒后驾车是一种非常严重的违章行为,交警常用“司机饮酒检测仪”检查司机呼出的气体以判断他是否饮酒.司机呼出的乙醇分子能在硫酸存在的条件下,使红色的三氧化铬变为绿色的硫酸铬.硫酸铬[Cr2(SO4)3]
热门考点