资源描述：
《证明由一棵二叉树的先序序列和中序序列可唯一确定这棵》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、证明：由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树.txt每天早上起床都要看一遍“福布斯”富翁排行榜，如果上面没有我的名字，我就去上班。谈钱不伤感情，谈感情最他妈伤钱。我诅咒你一辈子买方便面没有调料包。因为知道先序遍历后,第一个根是唯一确定的.然后在中序遍历里这个根将它分为两个部分,第一个根的两棵子树的根也会唯一确定,依次此类推,所有子树的根都唯一确定,二叉树就是唯一的.解题步骤1.由先序序列确定根结点(就是第一个字母了)2.按根结点把中序序列分为两段,前面的是左子树,后面的是右子树后面的步骤就基本
2、是前面两步的重复注意先序序列和中序序列的概念这题目就很容易的搞定#include#includetypedefcharTElemType;//Status是函数的类型，其值是函数结果状态码typedefintstatus;//函数结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2intw=0;#defineLink0#defineThread
3、1typedefstructBiThrNode{TElemTypedata;structBiThrNode*lchild,*rchild;//左右孩子指针intLTag,RTag;}BiThrNode,*BiThrTree;//构造二叉链表表示的二叉树statuscreatebitree(BiThrTree&T){charch;scanf("%c",&ch);if(ch=='$')T=NULL;else{if(!(T=(BiThrNode*)malloc(sizeof(BiThrNode))))exit(O
4、VERFLOW);T->data=ch;T->LTag=Link;T->RTag=Link;createbitree(T->lchild);createbitree(T->rchild);}returnOK;}voidInThreading(BiThrTree&p,BiThrTree&pre){//算法6.7//BiThrTreepre;if(p){InThreading(p->lchild,pre);//左子树线索化if(!p->lchild)//建前驱线索{p->LTag=Thread;p->lchil
5、d=pre;}if(!pre->rchild)//建后继线索{pre->RTag=Thread;pre->rchild=p;}pre=p;//保持pre指向p的前驱InThreading(p->rchild,pre);//右子树线索化}}//InThreading//输出元素statusvisit(TElemTypee){printf("%c",e);returnOK;}statusInOrderTraverse_Thr(BiThrTreeT,status(*Visit)(TElemType)){//中序遍
6、历二叉树T，并将其中序线索化，Thrt指向头结点。BiThrTreeThrt,pre;if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))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)
7、;//算法6.7：中序遍历进行中序线索化pre->rchild=Thrt;pre->RTag=Thread;//最后一个结点线索化Thrt->rchild=pre;}//*************************************************//Thrt指向头结点，若树不空，头结点的ltag为0，lchild指向根结点BiThrTreep;printf("前序遍历线索二叉树：");if(Thrt->LTag==0){p=Thrt->lchild;while(true){while(
8、p){visit(p->data);if(p->LTag==0)p=p->lchild;elsebreak;}while(p->RTag&&p->rchild!=T){p=p->rchild;}if(p->rchild==T)break;p=p->rchild;}}printf("");//**************************************************//Thrt指向头结
