数据结构讲义(严蔚敏版)第六章 树和二叉树

第六章树和二叉树非线性结构第六章树和二叉树树是以分支关系定义的层次结构树的定义、相关术语、存储结构二叉树的定义、五个重要性质和存储结构二叉树的遍历、线索化操作树和森林与二叉树的转换二叉树的应用-huffman编码和译码重点：1.二叉树的性质及遍历算法2.理解二叉树的线索化过程3.掌握树和森林与二叉树的转换关系难点：二叉树的二叉链表存储结构及其上的各种遍历算法实现线性结构和树形结构的对比春夏秋冬245136线性结构树结构第一个元素第一个数据元素(无前驱)根结点(无前驱)最后一个元素最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素一个直接前驱和一个直接后继树中其它结点(一个直接前驱、多个直接后继)6．1树的定义和基本术语树：n（n≥0）个结点的有限集。在任一棵非空树中：1.有且仅有一个特定称为根的结点2.n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tn，Ti称为树的子树。树的性质：递归性层次性基本术语：树的结点：数据元素及若干指向其子树的分支叶子（终端结点）：度（分支的个数）为零的结点分支结点（非终端结点）：度大于零的结点树的抽象数据类型定义ADTTree{

数据对象D:D是具有相同特性的元素集合

数据关系R:若D为空集,则称空树;若D中只含一个数据元素,则R为空集,否则R={H},H是如下二元关系:(1)在D中存在惟一的称为根的数据元素root,它在关系H下无前驱;(2)若D-{root}非空，则存在一个划分D1,D2,…,Dm(m>0),对任意jk(1j,km)有DjDk=,且对任意的i(1im),惟一存在数据元素xiDi,有<root,xi>H;(3)对应于D-{root}的划分，H－｛<root,x1>，…,<root,xm>｝有惟一的一个划分H1,H2,…,Hm(m>0),对任意jk(1j,km)有HjHk=,且对任意的i(1im)，Hj是Di上的二元关系,(Di,{Hi})是一棵符合本定义的树，称为根root的子树。

基本操作：InitTree(&T);DestroyTree(&T);CreateTree(&T,definition);ClearTree(&T);TreeEmpty(T);TreeDepth(T);Root(T);Value(T,cur_e);Assign(T,cur_e,value);Parent(T,cur_e);LeftChild(T,cur_e);RightSibling(T,cur_e);InsertChild(&T,&p,i,c);DeleteChild(&T,&p,i);TraverseTree(T,visit());}ADTTree6．1树的定义和基本术语（续）结点的度：分支的个数树的度：树中所有结点的度的最大值树的深度（高度）：树中叶子结点所在的最大层次6．1树的定义和基本术语（续）双亲(结点)：孩子(结点)：结点子树的根称为该结点的孩子祖先(结点)：从根到该结点所经分支上的所有结点。子孙(结点)：以某结点为根的子树的任一结点兄弟(结点)：同一双亲的孩子互称兄弟。堂兄弟(结点)：双亲在同一层的结点互称堂兄弟

有序树：树中结点的各子树从左到右有次序(不能互换)。无序树：树中结点的各子树从左到右无次序(能互换)。森林：m（m≥0）棵互不相交的树的集合CDBFEAG1、树的根是

。2、树的叶子是

。3、结点D的度是

。4、结点B的孩子是

,子孙

。5、树的度是

,深度是

。6、结点K的双亲是

。7、结点F的堂兄弟是

。举例：如图的树，回答以下问题：IHKMLJ树的定义和基本术语（续）HJKIDAEBFGC(a)嵌套集合表示法JKIHDGCFEBA(b)凹入表示法(A(B(E,F),C(G),D(H,J,I(K))))(c)广义表表示法CDBFEAGIHKMLJ(d)树形表示法树的表示法6.2二叉树学习二叉树的目的二叉树存储结构和基本操作实现简单任何树都可与二叉树相互转换，解决了树的存储结构及运算复杂性的问题。二叉树递归定义：由n(n>=0)个结点的有限集合，或为空集，或由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。二叉树的五种不同形态二叉树的抽象数据类型定义ADTBinaryTree{数据对象D:D是具有相同特性的元素集合

数据关系R:若D为空集,则称空树;若D中只含一个数据元素,则R为空集,否则R={H},H是如下二元关系:(1)在D中存在惟一的称为根的数据元素root,它在关系H下无前驱;(2)若D-{root}非空，则存在一个划分Dl,Dr,且DlDr=,(3)若Dl≠,则Dl存在数据元素xlDl,有<root,xl>H;且存在Ｄl上关系Hl在H中;若Dr≠,则Dr存在数据元素xrDr,有<root,xr>H;且存在Ｄr上关系Hr在H中;H={<root,xl>,<root,xr>,Hl,Hr};(3)(Di,{Hl})是一棵符合本定义的二叉树，称为根的左子树；(Dr,{Hr})是一棵符合本定义的二叉树，称为根的右子树。

基本操作：InitBiTree(&T);DestroyBiTree(&T);CreateBiTree(&T,definition);ClearBiTree(&T);BiTreeEmpty(T);BiTreeDepth(T);Root(T);Value(T,e);Assign(T,&e,value);Parent(T,e);LeftChild(T,e);RightSibling(T,e);InsertChild(&T,p,LR,c);DeleteChild(&T,p,LR);PreOrderTraverse(T,visit());InOrderTraverse(T,visit());PostOrderTraverse(T,visit());LevelOrderTraverse(T,visit());}ADTBinaryTree6.2.2二叉树的性质性质1：在二叉树的第i层上至多有2i-1个结点(i>=1)。性质2：深度为k的二叉树至多有2k－1个结点（k>=1).性质3：对任一棵二叉树，若其终端结点数为n0，度为2的结点数为n2，则n0＝n2＋1。2311层：202层：21…i层：2i-1…k层：2k-1…2i-12k-12i-12k-1……6.2.2二叉树的性质证明性质1：在二叉树的第i层上至多有2i-1个结点(i>=1)。采用归纳法：当i=1时，只有一个根结点，2i-1=20=1,命题成立。现假定对所有的j，1<=j<i,命题成立，即第j层上至多有2j-1个结点，那么可以证明j＝i时命题也成立。由归纳假设可知，第i－1层上至多有2i-2个结点。由于二叉树每个结点的度最大为2，故在第i层上最大结点数为第i－1层上最大结点数的二倍，即2×2i-2＝2i-1。命题得到证明。证明性质2：深度为k的二叉树至多有2k－1个结点(k>=1).深度为k的二叉树的最大的结点数为二叉树中每层上的最大结点数之和，由性质1得到每层上的最大结点数：6.2.2二叉树的性质6.2.2二叉树的性质证明性质3：对任何一棵二叉树，若终端结点数为n0，度为2的结点数为n2，则n0＝n2＋1。设二叉树中总结点数为n，度为1的结点数为n1，因二叉树中所有结点的度均小于或等于2，有n＝n0＋n1＋n2(6-1)从二叉树分支数看，除根结点外，其余结点都有一个进入的分支，且均由度为1和2的结点射出。设二叉树分支总数为B，有：n＝B＋1＝n1+2n2+1。(6-2)由式(6-1)和(6-2)得到：n0+n1+n2=n1+2n2+1n0＝n2＋1得证满二叉树和完全二叉树满二叉树：一棵深度为k且有2k-1个结点的二叉树。完全二叉树：若深度为k、有n个结点的二叉树中各结点能与深度为k的顺序编号的满二叉树编号从1到n的结点相对应。所有的叶结点都出现在第k层或k－1层。若任一结点右子树最大层次为l，其左子树最大层次为1或l＋1。性质4：有n个结点的完全二叉树的深度为log2n＋1。(b)完全二叉树(c)非完全二叉树(d)非完全二叉树2453671(a)满二叉树6245312431234516.2.2二叉树的性质证明性质4：有n个结点的完全二叉树的深度为log2n

＋1。假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到：

2k-1-1<n<=2k-1或2k-1<=n<2k取对数得到：k-1<=log2n<k因为k是整数。所以有：k＝log2n

＋1。6.2.2二叉树的性质性质5：若对一棵有n个结点的完全二叉树结点按层序编号(从第1层到第log2n+1层，每层从左到右),对任一结点i（1≤i≤n),有：(1)若i＝1，i无双亲，是二叉树的根；若i>1，其双亲是结点i/2(2)若2i>n，i为叶子结点，无左孩子；否则，其左孩子是结点2i。(3)若2i＋1>n，则i无右孩子；否则，其右孩子是结点2i＋1。i和i+1结点不在同一层…i+12i+22i+3i2i2i+1……22i31完全二叉树i/2ii+12i+12i+22i+3i和i+1结点在同一层

2ii……i+1i+2i+36.2.3二叉树的存储结构(1)顺序存储结构:用一组地址连续的存储单元依次自上而下、自左至右存储二叉树的结点。仅适用于完全二叉树。缺点：可能对存储空间造成极大的浪费，比如单支树。二叉树的顺序存储表示的C语言描述：#defineMAX_TREE_SIZE100typedefTElemTypeSqBiTree[MAX_TREE_SIZE];SqBiTreebt;6.2.3二叉树的存储结构(2)链式存储结构二叉链表：二叉树的二叉链表C语言描述typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;三叉链表:二叉树的三叉链表C语言描述typedefstructThiTNode{TElemTypedata;structThiTNode*lchild,*rchild,*parent;}ThiTNode,*ThiTree;lChilddatarChilddatalChildrChildlChilddataparentrChilddatalChildrChildparent二叉树的链式存储结构示例C^^A^BDE^G^^F^^T的二叉链表TA^^BC^^DE^G^^F^^T的三叉链表TBDFEGCA二叉树T6.3遍历二叉树和线索二叉树遍历二叉树:按某条搜索路径巡访树中的每一个结点，使每一个结点均被访问一次且仅被访问一次。在树中查找具有某种特征的结点；对树中全部结点逐一进行某种处理；寻找遍历二叉树的规律二叉树基本组成：根结点D、左子树L和右子树R。遍历二叉树有DLR、LDR、LRD、DRL、RDL、RLD六种方案。若规定先左后右，则只有三种：DLR—先（根）序遍历，LDR—中（根）序遍历，LRD—后（根）序遍历。D遍历二叉树先序遍历访问根结点；先序遍历左子树；先序遍历右子树；中序遍历中序遍历左子树；访问根结点；中序遍历右子树；后序遍历后序遍历左子树；后序遍历右子树；访问根结点层序遍历按从上到下，从左到右的顺序访问结点BDFEGCA先序序列：ABCDEGF中序序列：CBEGDFA后序序列：CGEFDBA层序序列：ABCDEFG先序遍历的递归算法StatusPreorderTraverse(BiTreeT,int(*visit)(chare)){if(T)//树不空{if(visit(T->data))//访问当前的根结点if(PreorderTraverse(T->lchild,visit))//先序遍历左子树if(PreorderTraverse(T->rchild,visit))//先序遍历右子树returnOK;returnERROR;//若访问不到当前根结点值，出错}elsereturnOK;//树空}时间复杂度：n个结点的二叉树先序遍历时间复杂度O(n)中序遍历的递归算法StatusInorderTraverse(BiTreeT,int(*visit)(chare)){if(T)//树不空{if(InorderTraverse(T->lchild,visit))//中序遍历左子树if(!visit(T->data))//访问当前的根结点if(InorderTraverse(T->rchild,visit))//中序遍历右子树returnOK;returnERROR;}elsereturnOK;//树空}时间复杂度：n个结点的二叉树中序遍历时间复杂度O(n)二叉树中序遍历递归算法改非递归算法(1)voidInorderTraverse(BiTreeT,int(*visit)(chare)){if(T)//树不空

{InorderTraverse(T->lchild,visit);//中序遍历左子树

visit(T->data);//访问根结点

InorderTraverse(T->rchild,visit);//中序遍历右子树

}}将算法中第二个递归语句消去,用循环实现voidInorderTraverse(BiTreeT,int(*visit)(chare)){if(T)//树不空

{InorderTraverse(T->lchild,visit);//中序遍历左子树

visit(T->data);//访问根结点

T=T→rchild；

}}二叉树中序遍历递归算法改非递归算法(2)借助栈,记忆回退的路径.消去算法中的第一个递归StatusInorderTraverse(BiTreeT,int(*visit)(chare)){

InitStack(S);p=T;while(p||!StackEmpty(S)){if(p){Push(S,p);p=p->lchild;}//向左走else{Pop(S,p);visit(p->data);//访问根结点

p=p->rchild;}//中序遍历右子树

}returnOK;}//算法先序遍历二叉树的非递归算法1StatusNPreorderTraverse(BiTreeT,int(*visit)(chare)){

InitStack(S);p=T;while(p||!StackEmpty(S)){if(p){visit(p->data);//访问根结点Push(S,p);p=p->lchild;}else{Pop(S,p);p=p->rchild;}//向右子树走}returnOK;}先序遍历二叉树的非递归算法2intNPreorderTraverse(BiTreeT,int(*visit)(chare)){InitStack(S);Push(S,T);//根指针入栈while(!StackEmpty(S))//在栈不空的情况下{while(GetTop(S,p)&&p){visit(p->data);Push(S,p->lchild);//向左走到头}Pop(S,p);//空指针退栈if(!StackEmpty(S)){Pop(S,p);//元素出栈 Push(S,p->rchild);//右子树入栈}}returnOK;}//NInOrderTraverse先序遍历二叉树的非递归算法3StatusNPreOrderTraverse(BiTree&T){ BiTreep; p=T; SqStackS; InitStack(S); Push(S,T);//根结点入栈 while(!StackEmpty(S))//在树不空的情况下 { Pop(S,p);//退栈并访问根结点 visit(p->data); if(p->rchild)//右孩子入栈 Push(S,p->rchild); if(p->lchild)//左孩子入栈，顺序不可颠倒 Push(S,p->lchild); } returnOK;}中序遍历二叉树非递归算法intNInorderTraverse(BiTree&T，int(*visit)(chare)){InitStack(S);Push(S,T);//根指针入栈while(!StackEmpty(S))//在栈不空的情况下{while(GetTop(S,p)&&p)Push(S,p->lchild);//向左走到头Pop(S,p);//空指针退栈if(!StackEmpty(S)){Pop(S,p);//元素出栈 if(!visit(p->data)) returnERROR; Push(S,p->rchild);//右子树入栈}}returnOK;}//NInOrderTraverse后序遍历二叉树非递归算法typedefstructData{ BiTNode*p; inttag;}Data,SElemType;intNPostOrderTraverse(BiTreeT){PSqStackS; PInitStack(S); Datadata; data.p=T; do{ if(data.p) { data.tag=0;PPush(S,data);data.p=data.p->lchild;} else { PPop(S,data); if(data.tag==0) { data.tag=1;PPush(S,data);data.p=data.p->rchild;} else { visit(data.p->data); data.p=NULL; } } }while(data.p||!PStackEmpty(S)); returnOK;}层序遍历二叉树非递归算法voidLevelOrderTraverse1(BiTreeT){ SqQueueQ; InitQueue_C(Q); BiTreep; p=T; EnQueue_C(Q,p); while(!QueueEmpty_C(Q)) {DeQueue_C(Q,p); visit(p->ch); if(p->lchild) EnQueue_C(Q,p->lchild);if(p->rchild) EnQueue_C(Q,p->rchild);}}二叉树的遍历举例已知某二叉树前序序列{ABHFDECKG}和中序序列{HBDFAEKCG},构造二叉树过程如下：HBDFEKCGAEKCGABHDFEKCGABHFDEABHFDCKGAKCGEBHFDA二叉树前序遍历的应用-建立二叉树输入ABCΦΦDEΦGΦΦFΦΦΦ(Φ表示空格)建立二叉树的二叉链表存储结构。StatusCreateBiTree(BiTree&T){scanf(“%c”,&ch);if(ch==‘’)T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T–>data=ch;CreateBiTree(T–>lchild);CreateBiTree(T–>rchild);}returnOK;}二叉树前序遍历的应用-二叉树判等voidEqual(BiTreeT1,BiTreeT2,bool&flag){ if(T1==NULL&&T2==NULL) flag=true; elseif(T1==NULL||T2==NULL) flag=false; else { if(T1->data==T2->data) flag=true; else flag=false; if(flag) { Equal(T1->lchild,T2->lchild,flag); Equal(T1->rchild,T2->rchild,flag);} }}二叉树前序遍历的应用-两棵二叉树判等StatusEqual(BiTreeT1,BiTreeT2){ if(T1==NULL&&T2==NULL) return1; elseif(T1!=NULL&&T2!=NULL&&T1->data==T2->data&&Equal(T1->lchild,T2->lchild)&&Equal(T1->rchild,T2->rchild)) return1; else return0;}二叉树前序遍历的应用-复制二叉树BiTreeCopy(BiTreeT1,BiTree&T2){ if(T1==NULL) returnNULL; if(!(T2=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW); T2->data=T1->data; T2->lchild=Copy(T1->lchild,T2->lchild); T2->rchild=Copy(T1->rchild,T2->rchild); returnT2;}二叉树后序遍历的应用-求二叉树的深度intdepth(BiTreeT){if(!T)return0;if(T->lchild==NULL&&T->rchild==NULL) return1;else{depthl=depth(T->lchild);depthr=depth(T->rchild); }return(depthl>depthr?depthl:depthr)+1;}二叉树后序遍历的应用-求二叉树叶子结点数intLeafNodes(BiTreeT){if(T==NULL)return0;elseif((T->lchild==NULL)&&(T->rchild==NULL))return1;else{ numl=LeafNodes(T->lchild); numr=LeafNodes(T->rchild); returnnumr+numl;} }二叉树层序遍历的应用-计算每层结点data值>50的结点个数并输出voidGetMoreThan50(BiTreeT){ inttotal[100]; InitQueue(Q);EnQueue(Q,T); intlevel=1;//统计的当前层 intnum=1;//记录每层总结点数 while(!QueueEmpty(Q)) { for(i=1;i<=num;i++) { DeQueue(Q,p); if(p->data>50)total[level]++; if(p->lchild)EnQueue(Q,p->lchild); if(p->rchild)EnQueue(Q,p->rchild); } num=QueueLength(Q);//更新为下一层的总结点数 level++; } for(i=1;i<=level;i++) printf("%d",total[50]);}由二叉树的顺序存储结构构造二叉树的二叉链表存储结构chara[]={‘0’,‘1’,‘2’,‘3’,‘4’,‘5’,‘6’};voidCreateBiTreeFromArray(BiTree&T,chara[n],inti){ T=(BiTree)malloc(sizeof(BiTNode)); T->ch=a[i]; if(2*i<n) CreateBiTreeFromArray(T->lchild,a,2*i); else T->lchild=NULL; if(2*i+1<n)CreateBiTreeFromArray(T->rchild,a,2*i+1); else T->rchild=NULL;}二叉树遍历小结二叉树的遍历：按一定规则(前序、中序、后序、层序)将二叉树中的结点排列成一个线性序列。二叉树的遍历的实质：非线性结构线性化-使得每个结点(除第一个和最后一个)在线性序列中均有且只有一个直接前驱和一个直接后继。二叉树的遍历的应用是二叉树各种操作的基础问题：只有在遍历过程中才能得到结点在相应遍历序列中的直接前驱和直接后继信息.6.3.2线索二叉树C^^A^BDE^G^^F^^TCABDEGFT中序全线索二叉树BDFEGCA二叉树TT的二叉链表二叉树线索二叉树线性序列线索化动态遍历静态遍历6.3.2线索二叉树引入线索二叉树的目的：充分利用二叉链表的空指针域，保存动态遍历过程中得到的结点在某遍历序列中的直接前驱和直接后继信息如何保存这种在遍历过程中得到的信息?1)在每个结点上增加两个指针域fwd和bkwd，分别指向结点在按照任意遍历时得到的前驱和后继。2)在有n个结点的二叉链表中必定存在n+1个空链域，用它们存放遍历过程中结点的前驱和后继。若结点没有左子树，lchild指向某遍历序列的直接前驱；若结点没有右子树，rchild指向某遍历序列的直接后继；lchildfwddatabkwdrchild6.3.2线索二叉树如何区分lchild和rchild域中存储的是子树还是指向结点前驱与后继的信息呢？A：增加标志域线索二叉树的结点：术语线索：指向结点前驱与后继的指针。线索二叉树：加上线索的二叉树。线索化:对二叉树以某种次序遍历使其变为线索二叉树的过程。线索链表：以上述结点构成的二叉链表。lchildltagdatartagrchild

ltag=

0lchild指示结点的左孩子1lchild指示结点的前驱0rchild指示结点的右孩子1rchild指示结点的后继rtag=线索二叉树的存储结构二叉树的二叉线索存储表示typedefenum{Link,Thread}PointerTag;//Link==0:指针,Thread==1:线索typedefstructBiThrNode{TElemTypedata;structBiThrNode*lchild,*rchild;//左右孩子指针PointerTagLTag,RTag;//左右标志}BiThrNode,*BiThrTree;二叉树的线索化线索化的过程：在遍历过程中修改空指针使其指向该遍历序列中的直接前驱结点或直接后继结点。例：中序遍历建中序线索二叉树设指针pre始终指向刚刚访问过的结点，指针p指向当前访问的结点，即pre始终指向p的前驱。p->lchild=pre;pre->rchild=p;中序遍历建立中序线索链表算法StatusInorderThreading(BiThrTree&Thrt，BiThrTreeT){//中序遍历T，并将其中序线索化，Thrt指向头结点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;InThrTreading(T);//中序线索化pre–>rchild=Thrt;pre–>RTag=Thread;Thrt–>rchild=pre;}returnOK;}//InorderThreading中序遍历建立中序线索链表算法voidInThreading(BiThrTreep){if(p){InThreading(p–>lchild);//左子树线索化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);//递归右子树线索化}}0A00B00C00D00E0T01Thrt0A00B00C00D00E0Tpre==NULLp01Thrt0A01B00C00D00E0Tpre==NULLp01Thrt0A01B00C01D00E0Tprep01Thrt0A01B00C01D1

0E0Tprep01Thrt0A01B00C01D1

1E0Tprep01Thrt0A01B00C01D1

1E1

Tprep01Thrt0A01B00C1

1D1

1E1

Tpre01Thrt0A01B00C1

1D1

1E1

Tpre01Thrt0A01B00C1

1D1

1E1

Tpre01Thrt遍历线索二叉树在线索二叉树上遍历的过程，就是根据线索和遍历规则不断找当前结点的直接后继结点的过程。思想：先找到(前、中、后)序遍历序列中的第一个结点，然后依次找结点后继直至其后继为空。实现：for(p=firstNode(T);p;p=Succ(p))Visit(p->data);二叉树线索二叉树线性序列线索化动态遍历静态遍历遍历中序线索二叉树算法StatusInorderTraverse_Thr(BiThrTreeT,Status(*visit)(TElemType)){//T指向头结点,头结点的lchild域指向根结点p=T–>lchild;//p指向二叉树根结点while(p!=T)//树不空或未遍历完{while(p–>LTag==Link)p=p–>lchild;//左孩子存在,向左走到头if(!visit(p–>data))//访问其左子树为空的结点returnerror;while(p–>RTag==Thread&&p–>rchild!=T){//该结点rchild指向后继，且不是中序遍历的最后一个结点。

p=p–>rchild;visit(p–>data);//访问后继结点}p=p–>rchild;}returnOK;}在前序线索二叉树中遍历设p为指向当前结点的指针，pn是指向p所指结点直接后继的指针．找结点p的后继

①if(p->rtag==1)pn=p->rchild

②if(p->rtag==0)if(p->lchild)pn=p->lchild;elsepn=p->rchild;

前序全线索树BDFEGCA在中序线索二叉树中找结点的直接前驱设p为指向当前结点的指针，pre是指向p所指结点直接前驱结点的指针．找结点p的直接前驱if(p->ltag==1)if(p->lchild)_

pre=p->lchild;elsepre=NULL;if(p->ltag==0)if(p->lchild)

//pre为当前结点左子树中序下的最后一个结点

else出错中序全线索树BDFEGCA在中序线索二叉树中找结点的直接后继设p为指向当前结点的指针，pn是指向p所指结点直接后继的指针．找结点p的后继if(p->rtag==1)pn=p->rchild;if(p->rtag==0){

pn=p->rchild;

while(pn->lchild)

pn=pn->lchild;}中序全线索树BDFEGCA在后序线索二叉树中遍历后序全线索树用带标志域的三叉链表做存储结构,设p为指向当前结点的指针，f是指向p的双亲的指针,pn指向p的直接后继结点．找结点的后继①

if(p->rtag==1)pn=p->rchild;②if(p->rtag==0){if(f->lchild==p)&&f->rchild==NULL)

pn=f;if(f->lchild==p)&&f->rchild!=NULL){pn=f->rchild;

while(pn->lchild)

pn=pn->lchild;}}BDFEGCA在中序线索二叉树上的遍历BiThrTreeFirst(BiThrTreeThrt){//求遍历中序线索二叉树的第一个结点 BiThrTreep=Thrt->lchild; while(p->LTag==0) p=p->lchild; returnp;}BiThrTreeLast(BiThrTreeThrt){//求遍历中序线索二叉树的最后一个结点 BiThrTreep=Thrt->lchild; while(p->RTag==0) p=p->rchild; returnp;}在中序线索二叉树上的遍历BiThrTreeNext(BiThrTreep){//求遍历中序线索二叉树的p结点的直接后继 BiThrTreepn=p-rchild; if(p->RTag==0) returnFirst(pn); else returnpn;}BiThrTreePrior(BiThrTreep){//求遍历中序线索二叉树的p结点的直接前驱 BiThrTreepre=p-lchild; if(p->LTag==0) returnLast(pre); else returnpre;}6.4.1树的存储结构-双亲表示法树的顺序存储结构：用结构数组存放树的结点，每个结点含两个域：数据域：存放结点本身信息双亲域：指示本结点的双亲结点在数组中位置特点：找双亲容易，找孩子难树的双亲表存储描述#defineMAX_TREE_SIZE100typedefstructPTNode{TElemTypedata;intparent;}PTNode;typedefstruct{PTNodenodes[MAX_TREE_SIZE];intr,n;}PTree;R-1A0B0C0D1E1F3G6H6K60123456789T的双亲表示示例BCAEDRFHKG树Tdataparent6.4.1树的存储结构—孩子表示法datachild1child2child3childDchildnext结点同构，结点的指针个数相等，为树的度D．操作简便，浪费空间datadchild1child2childd结点不同构，结点指针个数不等，为该结点的度d．操作不便便于涉及孩子结点操作的实现，不适用于求结点的双亲。多重链表：每个结点有多个指针域，分别指向其子树的根孩子链表:结点的孩子用单链表存储，用结构数组指向每个孩子链表孩子链表示例孩子链表Ｃ语言描述：孩子结点结构:

typedef

struct

CTNode{

intchild;

struct

CTNode*next;}*ChildPtr;双亲结点结构

typedef

struct{

TElemTypedata;

ChildPtrfirstchild;//孩子链表头指针

}CTBox;孩子链表结构:

typedef

struct{

CTBoxnodes[MAX_TREE_SIZE];

intn,r;//结点数和根结点的位置

}CTree;BCAEDRFHKGTR^K^H^GF^ED^C^BA012345678913^2

5^46^79^8T的孩子链表datafirstchildKHGFEDCBAR^6^6^63^1^10^00-1012345678913^25^46^79^8T带双亲的孩子链表parentdatafirstchild孩子链表Ｃ语言描述：孩子结点结构:

typedef

struct

CTNode{

intchild;

struct

CTNode*next;}*ChildPtr;双亲结点结构

typedef

struct{

intparent;

TElemTypedata;

ChildPtrfirstchild;}CTBox;孩子链表结构:

typedef

struct{

CTBoxnodes[MAX_TREE_SIZE];

intn,r;}CTree;改进的孩子链表和示例BCAEDRFHKGT树的存储结构—孩子兄弟表示法二叉树(二叉链表)表示法:链表中结点的两个链域分别指向该结点的第一个孩子和下一个兄弟。结点结构：树的二叉链表存储表示typedefstructCSNode{ElemTypedata;structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;优点：易于找结点孩子缺点：不易查找结点的双亲破坏了树的层次datafirstchildnextsibling6.4.2树和二叉树的转换ADECBCEBADA^B^CD^^E^^存储存储E^^A^B^CD^^B^E^^A^CD^^解释解释二叉链表树转换成二叉树步骤1：加线-在兄弟之间加一连线步骤2：抹线-对每个结点，除了其左孩子外，去除其与其余孩子之间的关系步骤3：旋转-以树的根结点为轴心，将整树顺时针转45°ABCDEFGHI树T树转换成二叉树ABCDEFGHI步骤1：加线-在兄弟之间加一连线步骤2：抹线-对每个结点，除了其左孩子外，去除其与其余孩子之间的关系步骤3：旋转-以树的根结点为轴心，将整树顺时针转45°ABCDEFGHI树T树转换成二叉树ABCDEFGHI步骤1：加线-在兄弟之间加一连线步骤2：抹线-对每个结点，除了其左孩子外，去除其与其余孩子之间的关系步骤3：旋转-以树的根结点为轴心，将整树顺时针转45°ABCDEFGHI树T树转换成二叉树ABCDEFGHI步骤1：加线-在兄弟之间加一连线步骤2：抹线-对每个结点，除了其左孩子外，去除其与其余孩子之间的关系步骤3：旋转-以树的根结点为轴心，将整树顺时针转45°ABCDEFGHI树T树转换成二叉树ABCDEFGHI步骤1：加线-在兄弟之间加一连线步骤2：抹线-对每个结点，除了其左孩子外，去除其与其余孩子之间的关系步骤3：旋转-以树的根结点为轴心，将整树顺时针转45°ABCDEFGHI树TABCDEFGHIT转换的二叉树B二叉树转换成树步骤1：加线-若p结点是双亲结点的左孩子，将p的右孩子，沿分支找到的所有右孩子与p的双亲连线。步骤2：抹线-抹掉原二叉树中双亲与右孩子之间的连线步骤3：将结点按层次排列，形成树结构ABCDEFGHI二叉树B二叉树转换成树步骤1：加线-若p结点是双亲结点的左孩子，将p的右孩子，沿分支找到的所有右孩子，与p的双亲连线。步骤2：抹线-抹掉原二叉树中双亲与右孩子之间的连线步骤3：将结点按层次排列，形成树结构ABCDEFGHIABCDEFGHI二叉树B二叉树转换成树步骤1：加线-若p结点是双亲结点的左孩子，将p的右孩子，沿分支找到的所有右孩子，与p的双亲连线。步骤2：抹线-抹掉原二叉树中双亲与右孩子之间的连线步骤3：将结点按层次排列，形成树结构ABCDEFGHIABCDEFGHI二叉树B二叉树转换成树步骤1：加线-若p结点是双亲结点的左孩子，将p的右孩子，沿分支找到的所有右孩子，与p的双亲连线。步骤2：抹线-抹掉原二叉树中双亲与右孩子之间的连线步骤3：将结点按层次排列，形成树结构ABCDEFGHIABCDEFGHI二叉树B二叉树转换成树步骤1：加线-若p结点是双亲结点的左孩子，将p的右孩子，沿分支找到的所有右孩子，与p的双亲连线。步骤2：抹线-抹掉原二叉树中双亲与右孩子之间的连线步骤3：将结点按层次排列，形成树结构ABCDEFGHIABCDEFGHI二叉树BABCDEFGHIB转换的树TABEFGCDHI6.4.2树的遍历先根遍历:若树不空，先访问根结点，再依次先根遍历各棵子树后根遍历:若树不空，先依次后根遍历各棵子树，再访问根结点ABCDEFGHIABCDEFGHI树TABCDEFGHIT转换的二叉树B二叉树遍历先根(DLR)中根(LDR)后根(LRD)层序EFGBCHIDA树的遍历先根后根6.4.2森林和二叉树的转换－规则设森林F={T1,T2,……Tm}，二叉树B=（root，LB，RB）(1)森林转化成二叉树的规则若F为空(m=0)，B为空;若F不空(m≠0)，B的根root(B)是F中第一棵树T1的根root(T1)；左子树LB从T1根结点的子树森林(T11,T12,…,T1m)转换来；右子树RB是从森林F’={T2,T3,…,Tm}转换而来。(2)二叉树转换为森林的规则若B为空，F为空；若B非空，则F中第一棵树T1的根为二叉树的根root(B)；T1根的子树森林F1由B的左子树LB转换而来；F中除T1外其余树组成的森林F’={T2,T3,…,Tn}由B的右子树RB转换而来。森林转换成二叉树步骤1：转换－将各棵树分别转换成二叉树步骤2：加线－将每棵树的根结点用线相连步骤3：旋转－以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树ABCDEFGHIJ森林F森林转换成二叉树步骤1：转换－将各棵树分别转换成二叉树步骤2：加线－将每棵树的根结点用线相连步骤3：旋转－以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树ABCDEFGHIJABCDEFGHIJ森林FF中每棵树对应的二叉树森林转换成二叉树步骤1：转换－将各棵树分别转换成二叉树步骤2：加线－将每棵树的根结点用线相连步骤3：旋转－以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树ABCDEFGHIJABCDEFGHIJ森林F森林转换成二叉树步骤1：转换－将各棵树分别转换成二叉树步骤2：加线－将每棵树的根结点用线相连步骤3：旋转－以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树ABCDEFGHIJABCDEFGHIJ森林FF转换的二叉树BABCDEFGHIJ二叉树转换成森林步骤1：抹线－将二叉树根结点与其右孩子连线、沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成多棵二叉树步骤2：还原－将孤立的二叉树还原成树二叉树BABCDEFGHIJ二叉树转换成森林步骤1：抹线－将二叉树根结点与其右孩子连线、沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成多棵二叉树步骤2：还原－将孤立的二叉树还原成树二叉树BABCDEFGHIJABCDEFGHIJ二叉树转换成森林步骤1：抹线－将二叉树根结点与其右孩子连线、沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成多棵二叉树步骤2：还原－将孤立的二叉树还原成树ABCDEFGHIJ二叉树BABCDEFGHIJABCDEFGHIJ二叉树转换成森林步骤1：抹线－将二叉树根结点与其右孩子连线、沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成多棵二叉树步骤2：还原－将孤立的二叉树还原成树B转换成的森林F二叉树BABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ6.4.3树和森林的遍历－森林的遍历先序遍历访问第一棵树的根。先根遍历第一棵树中根结点的子树森林。先根遍历除去第一棵树之后剩余的树构成的森林。中序遍历中序遍历第一棵树中根结点的子树森林。访问第一棵树的根。中序遍历除去第一棵树之后剩余的树构成的森林。对森林中每一棵树进行先根遍历对森林中每一棵树进行后根遍历ABCDEFGHIJ6.4.3树和森林的遍历－森林的遍历ABCDEFGHIJABCDEFGHIJ森林FF转换的二叉树BABCDEFGHIJ二叉树遍历先根(DLR)中根(LDR)后根(LRD)层序森林的遍历先根中根后根BCDAFEHJIG6.6赫夫曼树(HuffmanTree)及应用最优二叉树的定义构造最优二叉树的算法最优二叉树的应用-huffman编码赫夫曼树最优二叉树赫夫曼树和最优二叉树的关系6.6.1最优二叉树的定义(1)两个结点间的路径:从树中一个结点到另一个结点之间的分支。两个结点间的路径长度：路径上的分支数目。树的路径长度：从树根到每个结点的路径长度之和。

权：一些有意义的实数结点带权路径长度：从该结点到树根的路径长度与结点权的乘积树的带权路径长度：树中所有叶子结点的带权路径长度之和。设二叉树中有n个叶子结点,wi为树中第i个叶子结点的权，li为它到树根的路径长度，则叶子结点i的带权路径长度=树的带权路径长度(WPL)=6.6.1最优二叉树的定义(2)最优二叉树：设n个权值{w1,w2,…wn}，构造一棵有n个叶子结点的二叉树，第i个叶子结点权值是wi，则其中带权路径长度最小的二叉树称为最优二叉树。abcd7524B3abcd7524B1dcab2475B2最优二叉树构造最优二叉树的算法步骤1：根据给定的n个权值{w1,w2,…,wn}，构造有n棵二叉树的森林F={T1,T2,…,Tn}，Ti(1≤i≤n)中只有一个带权值wi的根结点，其左、右子树均为空。步骤2：在F中选取两棵根结点权值最小和次小的二叉树作为左、右子树构造一棵新二叉树。置新的二叉树的根结点的权值为其左、右子树根结点的权值之和。步骤3：在F中删去这两棵二叉树，把新的二叉树加入F。步骤4：重复步骤2和步骤3,直到F中仅剩下一棵二叉树为止，这棵二叉树就是最优二叉树。例：某字符串中共使用4种字符a,b,c,d，每个字符分别出现7次,5次,2次,4次,构造对应的最优二叉树．a7b5c2d4构造最优二叉树的说明1在选取两棵根结点权值为最小和次小的二叉树时，如果出现权值相同的情况，可以在相同权值的二叉树中任选一棵。2当两棵根结点权值为最小和次小的二叉树组成新的二叉树的左右子树时，谁是左子树谁是右子树没有特殊规定。3在最优二叉树中没有度为1的结点，根据二叉树的性质3可知有n个叶子结点的二叉树有n-1个非终端结点共有2*n-1个结点。a7b5c2d461118a7b5d4c261118最优二叉树的存储结构用动态分配的一维数组来存储最优二叉树。typedefstruct{unsignedintweight;//权值unsignedintparent,lchild,rchild;//双亲，左、右孩子}HTNode,*HuffmanTree;构造最优二叉树的算法weightparentlchildrchild最优二叉树的应用-最佳判定树(1)例子：有100名学生，编制一个将百分制成绩转换成五级制的程序，要使效率最高（总的比较次数最少）。百分制0-5960-6970-7980-8990-100五级制badpassgeneralgoodexcellent比例5%15%40%30%10%if(a<60)p=“bad”;elseif(a<70)p=“pass”;elseif(a<80)p=“general”;elseif(a<90)p=“good”;elsep=“excellent”;a<60a<70a<80a<90badpassgeneralgoodexcellentYYYYNNNN最优二叉树的应用-最佳判定树(2)例子：有100名学生，编制一个将百分制成绩转换成五级制的程序，要使效率最高（总的比较次数最少）。讨论：为使程序效率最高，比较次数最少，以学生在各分数段的人数为权值，构造最优二叉树。70≤a<8080≤a<9060≤a<70a<60generalgoodpassbadexcellentYYYYNNNNa<80a<70a<90a<60generalbadpassgoodexcellentYYYYNNNN最佳判定树最优二叉树的应用-数据压缩(DataEncoding)编码方式示例适用场合和优点固定长度编码ASCⅡ码在字符使用频率相等时效率最高不等长编码赫夫曼编码节省磁盘空间，提高运算速度固定长度编码：每个被编码对象的码长相等。优点：码长等长，易于解码；缺点：被编码信息总码长较长；不等长编码：每个被编码对象的码长不等。优点：总码长较短；缺点：不易解码，解码容易产生二义性最优二叉树的应用-数据压缩(DataEncoding)解决二义性问题：前缀编码：任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。长度最短的二进制前缀编码：以n种字符出现频率为权，设计一棵huffman树，由此得到的编码称为huffman编码赫夫曼编码的存储表示：typedefchar**HuffmanCode;abcd000111例：构建赫夫曼树求赫夫曼编码023141152937800000011111115297814233110110101110111111000011101051129323814753112923147853112923141588781915295311292314878191529425810058428291519abcde例：HT的存储结构的初态和终态500029000700080001400023000300011000—000—000—000—000—000—000—000123456789101112131415weightparentlchildrchild50029000700080001400023000300011000000—000—000—000—000—000—000123456789101112131415weightparentlchildrchild99178101034151111891912125102913136114214142125815151314100知识结构图定义树与二叉树基本概念存储结构树二叉树主要性质和特点森林层序前序中序后序二叉树遍历遍历方法的应用求路径复制二叉树统计结点数求二叉树深度赫夫曼树特点构造方法应用构造*按前序遍历按后序遍历按中序遍历线索二叉树前序中序后序相互转换应掌握的题集习题：，，，，，，，，，，，，，，，，，，，，6.29课后作业：，，，，，，，上机作业：二叉树的前、中、后序的遍历算法和应用应掌握的习题及