第六章 二叉树

实验4二叉树一、实验目的本次实验的目的是熟悉树的各种物理表示方法及各种遍历方式(其中以二叉树为侧重点)，了解树在计算机科学及其他工程中的应用。二、实验内容1.二叉树的建立(1)定义根指针,输入结点储存的date，若输入#，则该结点为空；(2)申请一个新结点，判断它的父结点是否为空，如果不为空再判断其为左或者右孩子，并把地址赋值给父结点，把date写入。二叉树与二叉链表存储示意图，二叉树的结点结构头指针roottypedefstructNodelchilddaterchildAB^C^D^F^^E^^G^ABCDEFG{datatypedata;structNode*LChild;structNode*RChild;}BiTNode,*BiTree;2.遍历二叉树(递归和非递归形式)（1）先序遍历：（DLR）先访问根结点；按先序遍历左子树；按先序遍历右子树。先序遍历非递归#includebitree.h#includestack.hvoidVisit(charch){printf(%c,ch);}voidInOrder(BiTreeroot)/*中序遍历二叉树的非递归算法*/{SeqStackS;BiTreep;InitStack(&S);p=root;while(p!=NULL||!IsEmpty(&S)){if(p!=NULL)/*根指针进栈，遍历左子树*/{Visit(p-data);Push(&S,p);p=p-LChild;}else{/*根指针退栈，访问根结点，遍历右子树*/Pop(&S,&p);p=p-RChild;}}}voidmain(){BiTreeT;printf(按扩展先序遍历序列建立二叉树，请输入序列:\n);CreateBiTree(&T);printf(前序遍历输出叶子结点为:);InOrder(T);getch();}（2）中序遍历：（LDR）按中序遍历左子树；访问根结点；按中序遍历右子树。中序遍历非递归#includebitree.h#includestack.hvoidVisit(charch){printf(%c,ch);}voidinorder(BiTreeroot)/*中序遍历二叉树，root为二叉树的根结点*/{inttop=0;BiTreep;BiTrees[Stack_Size];intm;m=Stack_Size-1;p=root;do{while(p!=NULL){if(topm)return;top=top+1;s[top]=p;p=p-LChild;};/*遍历左子树*/if(top!=0){p=s[top];top=top-1;Visit(p-data);/*访问根结点*/p=p-RChild;/*遍历右子树*/}}while(p!=NULL||top!=0);}voidInOrder(BiTreeroot)/*中序遍历二叉树的非递归算法*/{SeqStackS;BiTreep;InitStack(&S);p=root;while(p!=NULL||!IsEmpty(&S)){if(p!=NULL)/*根指针进栈，遍历左子树*/{Push(&S,p);p=p-LChild;}else{/*根指针退栈，访问根结点，遍历右子树*/Pop(&S,&p);Visit(p-data);p=p-RChild;}}}voidmain(){BiTreeT;printf(按扩展先序遍历序列建立二叉树，请输入序列:\n);CreateBiTree(&T);printf(中序遍历输出叶子结点1为:);inorder(T);printf(\n);printf(中序遍历输出叶子结点2为:);InOrder(T);getch();}（3）后序遍历：（LRD）按后序遍历左子树；按后序遍历右子树；访问根结点。后序遍历非递归#includebitree.h#defineStack_Size50#defineNUM50voidvisit(charch){printf(%c,ch);}voidPostOrder(BiTreeroot){BiTNode*p,*q;BiTNode**s;//BiTrees[Stack_Size];inttop=0;q=NULL;p=root;s=(BiTNode**)malloc(sizeof(BiTNode*)*NUM);/*NUM为预定义的常数*/while(p!=NULL||top!=0){while(p!=NULL){top++;s[top]=p;p=p-LChild;}/*遍历左子树*/if(top0){p=s[top];if((p-RChild==NULL)||(p-RChild==q))/*无右孩子，或右孩子已遍历过*/{visit(p-data);/*访问根结点*/q=p;/*保存到q，为下一次已处理结点前驱*/top--;p=NULL;}elsep=p-RChild;}}free(s);}voidmain(){BiTreeT;printf(按扩展先序遍历序列建立二叉树，请输入序列:\n);CreateBiTree(&T);printf(后序遍历输出叶子结点为:);PostOrder(T);printf(\n);getch();}例如图所示，其先序、中序、后序遍历如下。先序遍历：A、B、D、F、G、C、E、H中序遍历：B、F、D、G、A、C、E、H后序遍历：F、G、D、B、H、E、C、A3.线索二叉树的建立和遍历线索二叉树结点结构LChildLtagDataRtagRChid其中：0，LChild域指示结点的左孩子Ltag=1，LChild域指示结点的遍历前驱0，RChild域指示结点的右孩子Rtag=1，RChild域指示结点的遍历后继ABCEHHGDFF在这种存储结构中，指向前驱和后继结点的指针称为线索。以这种结构结构组成的二叉链表作为二叉树的存储结构，称为线索链表。对二叉树以某种次序进行遍历并加上线索的过程称为线索化。线索化了的二叉树称为线索二叉树。建立中序线索树算法思想（1）中序线索化才用中序递归遍历算法框架（2）加线索操作就是访问结点操作（3）加线索操作需要利用刚访问过结点与当前结点的关系，因此设置一个指针pre，始终记录刚访问过的结点，其操作如下：a：如果当前遍历结点root的左子域为空，则让左子域指向pre；b：如果前驱pre的右子域为空，则让右子域指向当前遍历结点root;c：为下次做准备，当前访问结点root作为下一个访问结点的前驱pre.算法voidInthread(BiTreeroot)/*对root所指的二叉树进行中序线索化，其中pre始终指向刚访问过的结点，其初值为NULL*/{if(root!=NULL){Inthread(root-LChild);/*线索化左子树*/if(root-LChild==NULL){root-Ltag=1;root-LChild=pre;/*置前驱线索*/}if(pre!=NULL&&pre-RChild==NULL)/*置后继线索*/{pre-RChild=root;pre-Rtag=1;}pre=root;Inthread(root-RChild);/*线索化右子树*/}}AvoidInthread(BiTreeroot)/*BvoidInthread(BiTreerootCvoidInthread(BiTreerootFvoidInthread(BiTreEvoidInthread(BiTreHvoidInthreadGvoidInthreadDvoidInthread(BiTre二叉树NULLNULL中序线索二叉树LR中序遍历序列关系示意图在中序线索树中找结点后继的算法BiTNode*InNext(BiTNode*p)/*在中序线索二叉树中查找p的中序后继结点，并用next指针返回结果*/{BiTNode*Next;BiTNode*q;if(p-Rtag==1)Next=p-RChild;/*直接利用线索*/else{/*在p的右子树中查找最左下端结点*/if(p-RChild!=NULL){for(q=p-RChild;q-Ltag==0;q=q-LChild);Next=q;}elseNext=NULL;}return(Next);}遍历中序二叉线索树的算法AACAFEAHGDABA………………XP………………voidTinOrder(BiTreeroot){BiTNode*p;p=TinFirst(root);while(p!=NULL){printf(%c,p-data);p=InNext(p);}}遍历组合及二叉树的确定两种遍历序列的组合是否能唯一确定二叉树先序+中序是后序+中序是先序+后序否4、树、森林和二叉树的关系数据双亲结点双亲表示法结点结构序号0123456树的双亲表示法树的孩子表示法DataParentDataParentA-1B0C0D1E1F1G2ABCD^E^F^G^136^2^45^ABCGFEDGEGCABEDBDHFFC（1）（2）（3）（4）树到二叉树的转换（2）（1）（3）森林（1）（2）（3）AHAACDEFGHBECFDBHGABECDFGHJIDBCEFGAHIJ森林对应的二叉树树和森林都可以转换为二叉树，二者的不同是：由树转换而成的二叉树，其根结点必然无右孩子，而由森林转换而得的二叉树，其根结点有有孩子。将一颗二叉树还原为树或森林。（1）若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的有孩子……都与该结点的双亲结点用线连起来。（2）删掉原二叉树中所有双亲结点与右孩子结点的连线。（3）整理由（1）、（2）两步所得到的树或森林，使之结构层次分明。树的遍历结果与由树转换而得的二叉树有如下对应关系：树的先根遍历转换后二叉树的前序遍历树的后根遍历转换后二叉树的中序遍历森林的遍历（1）先序遍历若森林非空，则遍历方法为：a：访问森林中第一棵树的根结点；b：先序遍历第一棵树的根结点的子树森林；c：先序遍历除去第一棵树之后剩余的树构成的森林。（2）中序遍历若森林非空，则遍历方法为：a：中序遍历第一棵树的根结点的子树森林；b：访问森林中第一棵树的根结点；c：中序遍历除去第一棵树之后剩余的树构成的森林。（3）后序遍历a：后序遍历第一棵树的根结点的子树森林；b：后序遍历除去第一棵树之后剩余的树构成的森林；c：访问森林中第一棵树的根结点。ABEGDCFHJI5.哈夫曼树和哈夫曼树编码路径和路径长度路径是指从根结点到该结点的分支序列；路径长度是指根结点到该结点所经过的分支数目。结点的权和带权路径长度在实际应用中，人们常常给树的每个结点赋予一个具有某种实际意义的实数，称该实数为这个结点的权。在树结构中，把从树根到某一结点的路径长度与该结点的权的乘积，称为该结点的带权路径长度。树的带权路径长度树的带权路径长度为树中从根到所有叶子结点的各个带权路径长度之和，通常记为iniilwWPL1其中，n为叶子结点的个数,iw为第i个叶子结点的权值，il为第i个叶子结点的路径长度。哈夫曼树的构造哈夫曼树是由n个带权叶子结点构成的所有二叉树中带权路径长度最短的二叉树。因为这种树最早是由哈夫曼研究，所以称为哈夫曼树，又称为最优二叉树。（1）初始化：用给定的N个权值{1W,2W,……，nW}构造n棵二叉树并构成的森林F={1T，2T，……，nT}，其中每一棵二叉树iT(1≤i≤n)都只有一个权值为iW的根结点，其左、右子树为空。（2）找最小树：在森林F中选择两棵根结点权值最小的二叉树，作为一颗新二叉树的左、右子树，标记新二叉树的根结点权值为其左、右子树的根结点权值之和。（3）删除与加入：从F中删除被选中的两棵二叉树，同时把新构成的二叉树加入到森林F中。（4）判断：重复（2）（3）操作，直到森林中只含有一颗二叉树为止，此时的到的这棵二叉树就是哈夫曼树。哈夫曼的存储结构权值双亲序号左孩子序号右孩子序号静态三叉链表中结点