构建叉树的叉链表存储结构.doc

二叉树的二叉链表存储结构构建方法 假设有关二叉树的二叉链表存储的类型定义如下： typedef struct BiTNode{ // 结点结构 ElemType data ；//数据域 struct BiTNode *Lchild ；//左孩子指针 struct BiTNode *Rchild；//右孩子指针 } BiTNode ，*BiTree ； 1 利用扩展二叉树的先序序列构建 只根据二叉树的序不能唯一确定一棵二叉树。针对问题，做如下处理：二叉树中每个结点的空指针引出一个虚结点，其值为，，把这样处理后的二叉树称为原二叉树的扩展二叉树。扩展二叉树的唯一确定这棵二叉树。给出了一二叉树的扩展二叉树，以及该扩展二叉树的序列。建立二叉链表的算法如下： Create(BiTree T) {//输入扩展二叉树的先序序列，构建二叉链表 scanf(ch); //输入一个元素 if (ch==# ) T = NULL; else { T= (BiTree)malloc(sizeof(BiTNode))； //申请根结点 T-data =ch; // 给根结点数据域赋值 Create(T-Lchild);//建左子树 Create(T-Rchild);//建右子树 } } // Create 2 利用二叉树的先序序列和中序序列 容易证明：由一棵二叉树的先序序列和中序序列可唯一的确定一棵二叉树。 基本思想：先根据先序序列的第一个元素建立根结点；然后在中序序列中找到该元素，确定根结点的左、右子树的中序序列；左、右子树的中序序列再在先序序列中确定左、右子树的先序序列；最后由左子树的先序序列与中序序列建立左子树，由右子树的先序序列与中序序列建立右子树。int Find(ElemType *P, int L2 ,int H2, ElemType x) {//在数组P的区间L2..H2内确定x的位置 i=L2; while(P[i]!=x) i++; return i; }// Find void Create (BiTree T, int L1, int H1, int L2, int H2) {//已知先序序列pre[L1..H1]， //中序序列mid[L2..H2]构建二叉链表 if (L2H2) T=NULL; //建空树 else { T =(BiTree)malloc(sizeof(BiTNode)); //创建根结点T T -data=pre[L1]; //给根数据域赋值 k=Find(mid, L2, H2, pre[L1]); //找根在中序序列的位置 Create (T -Lchild, L1+1,k+L1-L2, L2,k-1); //创建左子树 Create(T-Rchild,k+L1-L2+1,H1,k+1, H2); //创建右子树 } }// Create 3 利用扩展完全二叉树的顺序存储 约定对二叉树上的结点从根结点起，自上而下，自左而右进行连续编号，根结点的编号为1。深度为k的，有n个结点的二叉树，当且仅当其每个结点的编号都与深度为k的满二叉树中编号为1至n中的结点一一对应时，称其为完全二叉树。 如果一棵二叉树不是完全二叉树，可以用添加虚结点的方式将其扩展为一棵完全二叉树，虚结点的值为，，把这样处理后的二叉树称为原二叉树的扩展二叉树。扩展二叉树 # ) then 建空树; else { if (2i=n) then s[2i]是s[i]的左孩子else 左孩子为空； if (2i+1=n) then s[2i+1]是s[i]的右孩子; else 右孩子为空; } 显然，这是一个递归过程。其算法如下： void Create (Bitree T , ElemType *s, int i, int n) {//创建一棵以s[i]值为根的值的二叉树的二 //叉链表，树的根为T if(s[i]==#) T =NULL; else { T =(BiTree)malloc(*sizeof(BiTNode)); //申请根结点 T -data=s[i]; // 给根结点的数据域赋值 j=2*i; if (j=n) //创建左子树 Create (T-Lchild , s, j, n); else T-Lchild=NULL; j++; if(j=n) //创建右子树 Create (T -Rchild , s, j, n); else T -Rchild=NULL; } }// Create 4 利用二叉排序树的性质 基本思