《证明：由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树.doc》由会员分享，可在线阅读，更多相关《证明：由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树.doc（6页珍藏版）》请在金锄头文库上搜索。
1、证明：由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树因为知道先序遍历后,第一个根是唯一确定的.然后在中序遍历里这个根将它分为两个部分,第一个根的两棵子树的根也会唯一确定,依次此类推,所有子树的根都唯一确定,二叉树就是唯一的. 解题步骤1.由先序序列确定根结点(就是第一个字母了)2.按根结点把中序序列分为两段,前面的是左子树,后面的是右子树后面的步骤就基本是前面两步的重复注意先序序列和中序序列的概念这题目就很容易的搞定#include#includetypedef char TElemType;/Status是函数的类型，其值是函数结果状态码typedef int status;/函数结果
2、状态代码#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 BiThrNode TElemType data; struct BiThrNode *lchild,*rchild; /左右孩子指针 int LTag,RTag;BiThrNode,*BiThrTree;/构造二叉链表表示的二叉树status createbitree(BiThrTree
3、&T) char ch; scanf(%c,&ch); if(ch=$) T=NULL; else if(!(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 &p,BiThrTree &pre) / 算法6.7 /BiThrTree pre; if (p) InThreading(p-lch
4、ild,pre); / 左子树线索化 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,pre); / 右子树线索化 / InThreading/输出元素status visit(TElemType e) printf(%c,e); return OK;status InOrderTraverse_Thr(BiThrTree T
5、, status (*Visit)(TElemType) / 中序遍历二叉树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; InThre
6、ading(T,pre); / 算法6.7：中序遍历进行中序线索化 pre-rchild = 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&p-rchi
7、ld!=T) p=p-rchild; if(p-rchild=T)break; p=p-rchild; printf(n);/* / Thrt指向头结点，头结点的左链lchild指向根结点，头结点的右链lchild指向 / 中序遍历的最后一个结点。中序遍历二叉线索链表表示的二叉树T， / 对每个数据元素调用函数Visit。 printf(中序遍历线索二叉树:); p = Thrt-lchild; / p指向根结点 while (p != Thrt) / 空树或遍历结束时，p=T while (p-LTag=Link) p = p-lchild; if (!visit(p-data) retur
8、n ERROR; / 访问其左子树为空的结点 while (p-RTag=Thread & p-rchild!=Thrt) p = p-rchild; visit(p-data); / 访问后继结点 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=NULL&T-lchild=NULL) w+; return 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);
