证明：由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树

《证明：由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树》由会员分享，可在线阅读，更多相关《证明：由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树（6页珍藏版）》请在金锄头文库上搜索。

1、证明：由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树证明：由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树因为知道先序遍历后,第一个根是唯一确定的.然后在中序遍历里这个根将它分为两个部分,第一个根的两棵子树的根也会唯一确定,依次此类推,所有子树的根都唯一确定,二叉树就是唯一的. 解题步骤1.由先序序列确定根结点(就是第一个字母了)2.按根结点把中序序列分为两段,前面的是左子树,后面的是右子树后面的步骤就基本是前面两步的重复注意先序序列和中序序列的概念这题目就很容易的搞定#include#includetypedef char TElemType;/Status 是函数的类型，其值是函

2、数结果状态码typedef int status;/函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2int w=0; #define Link 0#define Thread 1typedef struct BiThrNodeTElemType data;struct BiThrNode *lchild,*rchild; /左右孩子指针int LTag,RTag;BiThrNode,*BiThrTree;/构造二叉链表表示的二叉树sta

3、tus createbitree(BiThrTree scanf(“%c“,if(ch=$) T=NULL;elseif(!(T=(BiThrNode *)malloc(sizeof(BiThrNode)exit(OVERFLOW);T-data =ch;T-LTag=Link;T-RTag=Link;createbitree(T-lchild);createbitree(T-rchild);return OK;void InThreading(BiThrTree if (p) InThreading(p-lchild,pre); / 左子树线索化if (!p-lchild) / 建前驱线索

4、p-LTag = Thread; p-lchild = pre; if (!pre-rchild) / 建后继线索 pre-RTag = Thread; pre-rchild = p; pre = p; / 保持 pre 指向 p 的前驱InThreading(p-rchild,pre); / 右子树线索化 / InThreading/输出元素status visit(TElemType e)printf(“%c“,e);return OK;status InOrderTraverse_Thr(BiThrTree T, status (*Visit)(TElemType) / 中序遍历二叉树

5、T，并将其中序线索化，Thrt 指向头结点。BiThrTree Thrt,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); / 算法 6.7：中序遍历进行中序线索化pre-rchild

6、 = Thrt; pre-RTag = Thread; / 最后一个结点线索化Thrt-rchild = pre; /*/Thrt 指向头结点，若树不空，头结点的 ltag 为 0，lchild指向根结点 BiThrTree p;printf(“前序遍历线索二叉树：“);if(Thrt-LTag=0) p=Thrt-lchild; while(true) while(p) visit(p-data); if(p-LTag=0)p=p-lchild; else break; while(p-RTag if(p-rchild=T)break; p=p-rchild; printf(“n“);/*/

7、 Thrt 指向头结点，头结点的左链 lchild 指向根结点，头结点的右链 lchild 指向/ 中序遍历的最后一个结点。中序遍历二叉线索链表表示的二叉树 T，/ 对每个数据元素调用函数 Visit。printf(“中序遍历线索二叉树:“);p = Thrt-lchild; / p 指向根结点while (p != Thrt) / 空树或遍历结束时，p=Twhile (p-LTag=Link) p = p-lchild;if (!visit(p-data) return ERROR; / 访问其左子树为空的结点while (p-RTag=Thread visit(p-data); / 访问后

8、继结点p = p-rchild; / p 进至其右子树根printf(“n“);return OK; / InOrderTraverse_Thr/后序遍历status b(BiThrTree T,status(* visit)(TElemType e)if(T)if(b(T-lchild ,visit)if(b(T-rchild ,visit)if(visit(T-data)if(T-rchild=NULLreturn OK;return ERROR;else return OK;void main() BiThrTree T;createbitree(T);printf(“后序遍历线索二叉树:“);b(T,visit);printf(“n“);InOrderTraverse_Thr(T,visit); /中序线索二叉树printf(“n“);printf(“叶子节点个数：“);printf(“%dn“,w);