第6章树和二叉树资料课件

第六章树和二叉树6.1树的定义和基本概念6.2二叉树

6.2.1树的定义和基本术语

6.2.2二叉树的性质

6.2.3二叉树的存储结构6.3遍历二叉树

6.3.1遍历二叉树

6.3.2线索二叉树

6.4树和森林

6.4.1树的存储结构

6.4.3树的遍历6.6赫夫曼树及其应用

6.6.1最优二叉树（赫夫曼树）

6.6.2赫夫曼编码1树在数据结构中的位置

数据的逻辑结构

数据的存储结构

A．线性结构

B．非线性结构A.顺序存储

B.链式存储

线性表栈和队列串树图数据结构的三个方面

数据的运算：检索、排序、插入、删除、修改等。

数组和广义表2(2)其余的结点可分为m(m>=0)个互不相交的子集T1,T2,T3…Tm，其中每个子集又是一棵树，并称其为子树(Subtree)。36.1树的定义和基本术语(1)有且仅有一个特定的称为根(Root)的结点；给定元素A,B,C,D,E,F,G,H,I,J,K,L,M，及其前驱后继关系如下图所示。每个元素有唯一前驱，单后继不唯一。ABCDGEFHIJKLMEKLFT11BEFKLCGDHIJMT1T2T3HMIJ4树的例子1、日常生活：家族谱、行政组织结构；书的目录2、计算机：资源管理器的文件夹；编译程序：用树表示源程序的语法结构；数据库系统：用树组织信息；分析算法：用树来描述其执行过程；3、表达式表示(如a*b+(c–d/e)*f)+**ab-fc/de56ADTTree7基本术语1、结点的度(degree)：子树个数

叶子(leaf)（终端结点）:degree=0分支结点（非终端结点）:degree≠0内部结点（B、C、D、E、H）:除根外的分支结点树的度（3）：各结点度的最大值2、结点的孩子(child)

双亲(parent)（D为H、I、J的双亲）兄弟(sibling)(H、I、J互为兄弟)：同parent的孩子

祖先(ancestor)：从根到该结点的结点

子孙(descendants)：以某结点为根的子树上的结点(B的子孙为E、K、L、F)FGKLIJMABCDEHA83、结点的层次根结点为第一层。某结点在第i层，其孩子在第i+1

层。树的深度(depth)：最大层次堂兄弟(causin)：双亲同一层4、有序树和无序树9ABCDEFGKLHIJM第1层第2层第3层第4层ABCDADCB5、森林(forest)是m(m≥0)棵互不相交的树的集合。基本术语（续）1、树形表示法2、集合图表示3、广义表表示

4、凹入表表示树的表示bacghdefijabdeijfcghijdfghabcea(b(d,e(i,j),f),c(g,h))106.2二叉树6.2.1二叉树的定义

把满足以下两个条件的树型结构叫做二叉树（BinaryTree）：（1）每个结点的度都不大于2；（2）每个结点的孩子结点次序不能任意颠倒。即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。11下面给出二叉树的五种基本形态：(a)空二叉数(c)只有左子树的二叉树(b)只有根结点的二叉树(d)左右子树均非空的二叉树(e)只有右子树的二叉树二叉树的性质126.2.2二叉树的性质性质1：在二叉树的第i层上至多有2i-1个结点(i>=1)。

证明：

归纳法。（1）当i=1时，2i-1=20=1,命题成立。（2）假定i=k时命题成立，即第k层最多有2k-1个结点；（3）由归纳假设可知，由于二叉树每个结点的度最大为2，故在第k+1层上最大结点数为第k层上最大结点数的2倍，即2×2k-1＝2k=2(k+1)-1命题得到证明。13性质2：深度为k的二叉树至多有2k-1个结点(k≥1)。

证明：

由性质1，深度为k的二叉树的最大结点数为：

14

＝20+21+…+2k-1=2k-1＝数列的前n项和15性质3：对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0＝n2＋1。证明：设二叉树上度为1的结点数为n1，那么，结点总数n=n0+n1+n2…（1）边总数B：因为每个结点都有边进入（除根结点外），所以：n=B+1又，度为1或2的结点才射出边，所以：B=n1

+

2n2得

n=n1

+2n2

+1。…（2）由（1）（2）式，n0=n2+11612345两类特殊的二叉树：满二叉树和完全二叉树满二叉树：一棵深度为k且有2k-1个结点的二叉树完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。（编号的规则为，由上到下，从左到右。）17245367112345612345满二叉树完全二叉树非完全二叉树性质4：具有n个结点的完全二叉树的深度为。证明：

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

2k-1－1<n≤2k－1

或：

2k-1≤n<2k取对数得到：k－1≤log2n<k因为k是整数。所以：。18123456性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层开始，每层从左到右),则对任一结点i（1≤i≤n),有：（1）如果i＝1，则结点i是二叉树的根；

如果i>1，则其双亲是结点。（2）如果2i>n，则结点i为叶子结点，无左孩子；

否则，其左孩子是结点2i。（3）如果2i＋1>n，则结点i无右孩子；

否则，其右孩子是结点2i＋1。19┗i/2┙ii+12i2i+12i+22i+3(a)i和i+1结点在同一层20┗i/2┙ii+12i2i+12i+22i+3i+12i+22i+3i2i2i+1图6.5完全二叉树中结点i和i+1(a)i和i+1结点在同一层(b)i和i+1结点不在同一层如图所示为完全二叉树上结点及其左右孩子结点之间的关系。树和二叉树的ADT定义数据对象数据关系基本操作：查找类（Root(T)；Value(T,cur_e；Parent(T,cur_e)；LeftChild(T,cur_e)RightSibling(T,cur_e)；TreeEmpty(T)；TreeDepth(T)；TraverseTree(T,Visit())）插入类（InitTree(&T)；CreateTree(&T,definition)；Assign(T,cur_e,value)；InsertChild(&T,&p,i,c)）删除类（ClearTree(&T)；DestroyTree(&T)；DeleteChild(&T,&p,i)）216.2.3二叉树的存储结构（1）顺序存储结构完全二叉树：用一组连续的存储单元依次自上而下、自左至右存储各结点元素。即将完全二叉树上编号为i的结点的值存储在下标为i-1的数组元素中。某结点的父结点、左孩子、右孩子可由性质5计算得到。一般情形的二叉树：增添一些空结点使变成完全二叉树形态，再按上述方法存储。22ABCDEFGHIJKL12345678910111223完全二叉树ABCDEFGHIJKL一般二叉树ØABCDEFGØØØABCDEØØØØFG单支二叉树24ABCAB1234567C总结：1、完全二叉树用顺序存储既节约空间，存取也方便；2、一般二叉树用顺序存储，空间较浪费，最坏情况为右单支二叉树。（一个深度为K且只有K个节点的单支树却需要长度为2k-1的一维数组）（2）链式存储结构

常用的有二叉链表和三叉链表存储结构结点的左右孩子或双亲靠指针来指示25二叉链表存储表示TypedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;26三叉链表存储表示27二叉树链表表示的示例：286.3遍历二叉树和线索二叉树任何一个非空的二叉树都由三部分构成29DLR根结点根的左子树根的右子树树的遍历是访问树中每个结点仅一次的过程。遍历可以被认为是把所有的结点放在一条线上，或者将一棵树进行线性化的处理。6.3.1二叉树的遍历先左后右：DLR，LDR，LRD30DLR根结点根的左子树根的右子树先右后左：DRL，RDL，RLD先序遍历DLR：访问根结点、先序遍历左子树、先序遍历右子树31若二叉树非空（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树；若二叉树为空，结束——基本项（也叫终止项）若二叉树非空——递归项（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树；DLR+-/*abfroot先序遍历序列：-+a*b-cd/ef32e-cdvoidPreOrderTraverse(BiTNodePtrT){if(T){printf("%c",T->data);PreOrderTraverse(T->lchild));PreOrderTraverse(T->rchild));}

}typedefintStatus;typedefcharTElemType;typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTNodePtr;中序遍历LDR：中序遍历左子树、访问根结点、中序遍历右子树33DLR213中序遍历LDR：中序遍历左子树、访问根结点、中序遍历右子树34若二叉树非空（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树；若二叉树为空，结束——基本项（也叫终止项）若二叉树非空——递归项（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树；DLR+-/*abfroot中序遍历序列：a+b*c-d-e/f35e-cdvoidInOrderTraverse(BiTNodePtrT){if(T){PreOrderTraverse(T->lchild));printf("%c",T->data);PreOrderTraverse(T->rchild));}returnOK;}typedefintStatus;typedefcharTElemType;typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTNodePtr;中序遍历序列：BACEDGFpAvoidInOrderTraverse(BiTNodePtrT){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);visit(p->data);Push(S,p->rchild);}}}中序非递归遍历36栈：BACEDGFp中序遍历序列：AB37栈：voidInOrderTraverse(BiTNodePtrT){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);visit(p->data);Push(S,p->rchild);}}}BACEDGFp中序遍历序列：ABD∧∧38栈：voidInOrderTraverse(BiTNodePtrT){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);visit(p->data);Push(S,p->rchild);}}}BACEDGFp中序遍历序列：ABD∧∧NULL39voidInOrderTraverse(BiTNodePtrT){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);visit(p->data);Push(S,p->rchild);}}}BACEDGFp中序遍历序列：ABD∧∧D40voidInOrderTraverse(BiTNodePtrT){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);visit(p->data);Push(S,p->rchild);}}}BACEDGFp中序遍历序列：AB∧∧DNULL41voidInOrderTraverse(BiTNodePtrT){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);visit(p->data);

Push(S,p->rchild);}}}BACEDGFp中序遍历序列：AB∧∧D42voidInOrderTraverse(BiTNodePtrT){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);visit(p->data);Push(S,p->rchild);}}}BACEDGFp中序遍历序列：ADB43voidInOrderTraverse(BiTNodePtrT){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);

visit(p->data);Push(S,p->rchild);}}}BACEDGFp中序遍历序列：ADBEG44voidInOrderTraverse(BiTNodePtrT){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);visit(p->data);Push(S,p->rchild);}}}BACEDGFp中序遍历序列：ADBEGNULL∧45voidInOrderTraverse(BiTNodePtrT){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);visit(p->data);Push(S,p->rchild);}}}BACEDGFp中序遍历序列：ADBEG∧G46voidInOrderTraverse(BiTNodePtrT){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);visit(p->data);Push(S,p->rchild);}}}BACEDGFp中序遍历序列：ADBEGNULL∧47voidInOrderTraverse(BiTNodePtrT){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);visit(p->data);

Push(S,p->rchild);}}}BACEDGFp中序遍历序列：ADBE48EGvoidInOrderTraverse(BiTNodePtrT){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);visit(p->data);Push(S,p->rchild);}}}BACEDGFp中序遍历序列：ADBGEA49voidInOrderTraverse(BiTNodePtrT){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);

visit(p->data);Push(S,p->rchild);}}}BACEDGFp中序遍历序列：DBGEAC50voidInOrderTraverse(BiTNodePtrT){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);visit(p->data);

Push(S,p->rchild);}}}BACEDGFp中序遍历序列：DBGEAC∧NULL51voidInOrderTraverse(BiTNodePtrT){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);visit(p->data);Push(S,p->rchild);}}}BACEDGFp中序遍历序列：DBGEAC∧C52voidInOrderTraverse(BiTNodePtrT){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);visit(p->data);Push(S,p->rchild);}}}BACEDGFp中序遍历序列：DBGEACF53voidInOrderTraverse(BiTNodePtrT){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);visit(p->data);

Push(S,p->rchild);}}}BACEDGFp中序遍历序列：DBGEA∧CFNULL54voidInOrderTraverse(BiTNodePtrT){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);visit(p->data);Push(S,p->rchild);}}}BACEDGFp中序遍历序列：DBGEACF∧F55voidInOrderTraverse(BiTNodePtrT){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);visit(p->data);Push(S,p->rchild);}}}BACEDGFp中序遍历序列：DBGEANULLCF56voidInOrderTraverse(BiTNodePtrT){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);visit(p->data);

Push(S,p->rchild);}}}BACEDGF中序遍历序列：DBGEACF57voidInOrderTraverse(BiTNodePtrT){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);visit(p->data);Push(S,p->rchild);}}}后序遍历LRD：后序遍历左子树、后序遍历右子树、访问根结点58DLR312EGFCDAB后序遍历序列:BDFGECA+-/*abfroot后序遍历序列：abcd-*+ef/-59e-cdvoidPostOrderTraverse(BiTNodePtrT){if(T){PreOrderTraverse(T->lchild));PreOrderTraverse(T->rchild));printf("%c",T->data);}

}typedefintStatus;typedefcharTElemType;typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTNodePtr;60voidPostOrderTraverse(BiTNodePtrT){if(T){PreOrderTraverse(T->lchild));PreOrderTraverse(T->rchild));printf("%c",T->data);}}voidInOrderTraverse(BiTNodePtrT){if(T){PreOrderTraverse(T->lchild));printf("%c",T->data);PreOrderTraverse(T->rchild));}}voidPreOrderTraverse(BiTNodePtrT){if(T){printf("%c",T->data);PreOrderTraverse(T->lchild));PreOrderTraverse(T->rchild));}}总结：无论先序、中序、后序遍历二叉树，遍历时的搜索路线是相同的：从根节点出发，逆时针延二叉树外缘移动，对每个节点均途经三次。先序遍历：第一次经过节点时访问。（ABCD）中序遍历：第二次经过节点时访问。（BADC）后序遍历：第三次经过节点时访问。（BDCA）61例如图（1）所示的二叉树表达式

a+b*(c-d)-e/f若先序遍历此二叉树,按访问结点的先后次序将结点排列起来,其先序序列为:(波兰式,前缀表达式)-+a*b-cd/ef

按中序遍历,其中序序列为：a+b*c-d-e/f(中缀表达式)按后序遍历,其后序序列为：abcd-*+ef/-(逆波兰式，后缀表达式)注：时间复杂度均为O(n)－＋*a/b-dcfe图6.962遍历算法的应用举例2、统计二叉树中叶子结点的个数3、求二叉树的深度(后序遍历)4、复制二叉树(后序遍历)5、建立二叉树的存储结构1、查询二叉树中某个结点631、查询二叉树中某个结点64StatusPreorder(BiTNodePtrT,ElemTypex,BiTNodePtr&p)

{//若二叉树中存在和x相同的元素，则

p指向该结点并返回

OK,//否则返回

FALSE

if(T){if(T->data==x){p=T;returnOK,}else{if(Preorder(T->lchild,x,p)returnOK;elsereturn(Preorder(T->rchild,x,p));}//else}elsereturnFALSE;}2、统计二叉树中叶子结点的个数voidCountLeaf(BiTNodePtrT,int&count){

if(T){

if((!T->lchild)&&(!T->rchild))count++;//对叶子结点计数

CountLeaf(T->lchild,count);CountLeaf(T->rchild,count);}}65intCount(BiTNodePtrT){if(!T)return0;if(!T->lchild&&!T->rchild)return1;else{m=Count(T->lchild);n=Count(T->rchild);return(m+n+1);}}统计二叉树中所有结点的个数663、求二叉树的深度(后序遍历)intDepth(BiTNodePtrT){

if(!T)depthval=0;else{depthLeft=Depth(T->lchild);depthRight=Depth(T->rchild);depthval=1+(depthLeft>depthRight?depthLeft:depthRight);

}

returndepthval;}674、复制二叉树(后序遍历)BiTNode*NewTreeNode(TElemTypeitem,BiTNode*lptr,BiTNode*rptr){if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))exit(1);//其数据域为item,左指针域为lptr,右指针域为rptrT->data=item;T->lchild=lptr;T->rchild=rptr;

returnT;}68BiTNode*CopyTree(BiTNode*T){

if(!T)returnNULL;

if(T->lchild)

newlptr=CopyTree(T->lchild);//复制左子树

elsenewlptr=NULL;

if(T->rchild)

newrptr=CopyTree(T->rchild);//复制右子树

elsenewrptr=NULL;newT=NewTreeNode(T->data,newlptr,newrptr);

returnnewT;}694、复制二叉树(后序遍历，续)以递归方式建立二叉树。输入结点值的顺序必须对应二叉树结点先序遍历的顺序。并约定以输入序列中不可能出现的值作为空结点的值。例如用“^”或用“-1”。705、建立二叉树如图所示的二叉树的先序遍历顺序为ABC^^DE^G^^F^^^ABCDEGF^^^^^^^^7172递归方式建立二叉树char*s="ABC^^DE^G^^F^^^";inti=0;StatusCreateBiTree(BiTNodePtr*T){charch=s[i++];if(ch=='\0')returnOK;if(ch=='^')*T=NULL;else{if(!(*T=(BiTNodePtr)malloc(sizeof(BiTNode))))exit(ERROR);(*T)->data=ch;CreateBiTree(&((*T)->lchild));CreateBiTree(&((*T)->rchild));}returnOK;}层序遍历先根，后子树；先左子树，后右子树73EGFCDAB队列队头树根结点A入队层序遍历序列:层序遍历先根，后子树；先左子树，后右子树74EGFCDAB队列队头A层序遍历序列:A出队层序遍历先根，后子树；先左子树，后右子树75EGFCDAB队列队头根结点B、C入队A的子树层序遍历序列:A层序遍历先根，后子树；先左子树，后右子树76EGFCDAB队列队头BB出队C层序遍历序列:A层序遍历先根，后子树；先左子树，后右子树77EGFCDAB队列队头C根结点入队B的子树层序遍历序列:AB层序遍历先根，后子树；先左子树，后右子树78EGFCDAB队列队头CC出队层序遍历序列:AB层序遍历先根，后子树；先左子树，后右子树79EGFCDAB队列队头根结点入队C的子树层序遍历序列:ABC层序遍历先根，后子树；先左子树，后右子树80EGFCDAB队列队头DED出队层序遍历序列:ABC层序遍历先根，后子树；先左子树，后右子树81EGFCDAB队列队头E根结点入队D的子树层序遍历序列:ABCD层序遍历先根，后子树；先左子树，后右子树82EGFCDAB队列队头EE出队层序遍历序列:ABCD层序遍历先根，后子树；先左子树，后右子树83EGFCDAB队列队头根结点F、G入队E的子树层序遍历序列:ABCDE层序遍历先根，后子树；先左子树，后右子树84EGFCDAB队列队头FGF出队层序遍历序列:ABCDE层序遍历先根，后子树；先左子树，后右子树85EGFCDAB队列队头G根结点入队F的子树层序遍历序列:ABCDEF层序遍历先根，后子树；先左子树，后右子树86EGFCDAB队列队头GG出队层序遍历序列:ABCDEF层序遍历先根，后子树；先左子树，后右子树87EGFCDAB队列队头根结点入队G的子树层序遍历序列:ABCDEFG问题的提出：当以二叉链表作为存储结构时,只能找到结点的左右孩子的信息,而不能直接找到结点在任一序列中的前驱与后继信息,这种信息只有在遍历的动态过程中才能得到,为了能保存所需的信息,可增加标志域;其中:0lchild域指示结点的左孩子

LTag={1lchild域指示结点的前驱

0rchild域指示结点的右孩子

RTag={1rchild域指示结点的后驱

以这种结构构成的二叉链表作为二叉树的存储结构,叫做线索链表,其中指向结点前驱与后继的指针叫做线索.加上线索的二叉树称之为线索二叉树。

对二叉树以某种次序遍历使其变为线索二叉树的过程叫线索化。lchildLTagdataRTagrchild886.3.2线索二叉树二叉树的二叉线索存储表示:Typedefenum{Link,Thread}PointerTag;//Link==0:指针,Thread==1:线索TypedefstructBiThrNode{TelemTypedata;structBiTreeNode*lchild,*rchild; PointerTagLTag,Rtag;}BiTreeNode,*BiThrTree;

仿照线性表的存储结构,在二叉树的线索链表上也添加一个头结点,令其lchild域的指针指向二叉树的根结点,其rchild域的指针指向中序遍历时访问的最后一个结点;

同时,令二叉树中序序列中的第一个结点lchild域的指针和最后一个结点rchild域的指针均指向头结点;就像为二叉树建立了一个双向线索链表,就好比人在一个圆圈上走路,有可能存在好走的可能性.

89中序遍历序列为：DBEAHFCGNULLDEGFBCAHNULL90DEGFBCAH练习：构造下列二叉树的后序线索二叉树后序遍历序列为：DEBHFGCANULL91结点的后继：若是叶子结点，其右标志是“1”，即右链是线索，指示其后继；否则是右子树中最左下的结点。结点的前驱：若其左标志为“1”，则左链为线索，指示其前驱，否则左子树最右下的结点为其前驱。什么时候采用线索链表做存储结构？程序中所用二叉树需要经常遍历或查找结点在遍历所得线性序列中的前驱和后继时。如何在线索树上进行遍历？（中序线索树）92线索链表的遍历算法（中序找后继法，算法6.5）：StatusInOrderTraverse_Thr(BiThrTreeT,Visit){p=T－>lchild;//T指向头结点

while(p!=T){

while(p－>LTag==0)p=p－>lchild;

if(!Visit(p－>data))returnERROR;

while(p－>RTag==1&&p－>rchild!=T)

{p=p－>rchild;Visit(p－>data);}

p=p－>rchild;}

returnOK;

}－＋

a

×

b－

c

d／

e

f000000001111001111111101T

93如何对二叉树进行线索化？94建立线索二叉树的过程，实质上就是在遍历的过程中，检查当前结点的左右指针是否为空，如果为空，将它们改为指向其前驱或后继的线索。设指针pre始终指向刚刚访问过的结点，指针p指向当前正在访问的结点。即pre为p的前驱结点，p为pre的后继结点，则在线索化的过程中，访问结点p所做的处理如下（以中序线索化为例）：建立p的前驱线索。若p->lchild为空，则将其左标志置1，并令p->lchild指向其前驱pre建立pre的后继线索。若pre->rchild为空，则将其右标志置1，并令pre->rchild指向其后继p。将pre指向p刚刚访问过的结点，即pre=pStatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){

if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))exit(OVERFLOW);

Thrt－>LTag=0;Thrt－>RTag=1;//

建头结点

Thrt－>rchild=Thrt;//右指针回指

if(!T)Thrt－>lchild=Thrt;//若二叉树空，则左指针回指

else{Thrt－>lchild=T;pre=Thrt;

InThreading(T);//中序遍历进行中序线索化

pre－>rchild=Thrt;pre－>RTag=1;//最后一个结点线索化

Thrt－>rchild=pre;}

returnOK;

}//InOrderThreadingvoidInThreading(BiThrTreep){

if(p){InThreading(p－>lchild);//左子树线索化

if(!p－>lchild)//前驱线索{p－>LTag=1;p－>lchild=pre;}

if(!pre－>rchild)//后继线索

{pre－>RTag=1;pre－>rchild=p;}pre=p;//保持pre指向p的前驱

//右子树线索化

InThreading(p－>rchild);}

}

}－＋

a

×

b－

c

d／

e

f111111111111T

0Thrt

pre

95中序线索化算法算法6.66.7▲StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){

if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))exit(OVERFLOW);

Thrt－>LTag=0;Thrt－>RTag=1;//

建头结点

Thrt－>rchild=Thrt;//右指针回指

if(!T)Thrt－>lchild=Thrt;//若二叉树空，则左指针回指

else{Thrt－>lchild=T;pre=Thrt;

InThreading(T);//中序遍历进行中序线索化

pre－>rchild=Thrt;pre－>RTag=1;//最后一个结点线索化

Thrt－>rchild=pre;}

returnOK;

}//InOrderThreading－＋

a

×

b－

c

d／

e

f1111111111111T

0Thrt

pre

96976.4树和森林

6.4.1树的存储结构1:双亲表示法#defineMaxTS100Typedefstructptnode{telemtypedata;intparent;}ptnode;Typedefstruct{ptnodenodes[MaxTS];intn;}Ptree;RABCDEFGHKR-1A0B0C0D1E1F3G6H6K60123456789数组下标结点双亲2:孩子表示法:(a)多重链表(链表中每个指针指向一棵子树的根结点);(b)把每个结点的孩子结点排列起来,看成一个线性表,且以单链表做存储结构.且N个头指针也组成一个线性表.RABCDEFGHKAB∧CD∧RE∧FG∧H∧K∧012345678935∧6∧012∧789∧983:孩子兄弟表示法:二叉树表示法或二叉链表表示法以二叉链表做树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点(fchild和nsibling)TypedefstructCSNode{ElemTypedata;StructCSNode*fchild,*nsibling;}CSNode,*CSTree;996.4.2森林与二叉树的转换二叉树和树都可用二叉链表作存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一一对应关系。也就是说，给定一个树，可以找到惟一一棵二叉树与之对应。从树的二叉链表表示定义知道：任何一棵和树对应的二叉树的右子树必空。若将森林中第二棵树的根结点看成第一棵树的根结点的兄弟，则可以导出森林和二叉树的对应关系。100^^ABKGCDH^TE^FIJ^^^^^^^^KEFJHIGBDCA1、树与二叉树的转换ABFEGCDHIJK101二叉树和树都可以采用二叉链表存储，以二叉链表作中介可以导出树与二叉树的转换。树与二叉树之间的转换规则：102KEFJHIGBDCAABFEGCDHIJK树根结点X的第一个孩子结点X紧邻的右兄弟二叉树根结点X的左孩子结点X的右孩子ABFEGCDHIJKACGIDHJBFEK二叉树转换为树1032、森林与二叉树的转换若把森林中第二棵树的根结点看成是第一棵树的兄弟，则可以得到森林与二叉树的转换。104BDCAKJHIGEFABJFEHGIKCD森林转换为二叉树105二叉树转换为森林二叉树转换为森林的规则：106森林第一棵树的根根节点的子树森林除第一棵树外形成的森林转换成的二叉树二叉树根左子树右子树ABJFEHGIKCDACDBKIHJGEF二叉树转换为森林107树:先根 //相当于二叉树的先序遍历后根 //相当于二叉树的中序遍历森林:先序

1.访问森林中第一棵树的根结点; 2.先序遍历第一棵树中根结点的子树森林; 3.先序遍历除去第一棵树之后剩余的树构成的森林.

中序

1.中序遍历第一棵树中根结点的子树森林; 2.访问森林中第一棵树的根结点; 3.中序遍历除去第一棵树之后剩余的树构成的森林.1086.4.3树和森林的遍历6.4.3树和森林的遍历1、树的遍历先根遍历：（二叉树的先序遍历）先访问根结点，然后依次先根遍历根的每棵子树。后根遍历：（二叉树的中序遍历）后根访问根的每棵子树，然后访问根结点。109KEFJHIGBDCAABECFGHD先根遍历序列KIJABFEGCDHIJK对应二叉树的先序遍历110KEFJHIGBDCAEFBCGKIH后根遍历序列JDAABFEGCDHIJK对应二叉树的中序遍历1112、森林的遍历先序遍历（二叉树的先序）若森林非空，则可按下述规则遍历之：（1）访问森林中第一棵树的根结点（2）先序遍历第一棵树中根结点的子树森林（3）先序遍历除去第一棵树之后剩余的树构成的森林中序遍历（二叉树的中序）若森林非空，则可按下述规则遍历之：（1）中序遍历第一棵树中根结点的子树森林（2）访问森林中第一棵树的根结点（3）中序遍历除去第一棵树之后剩余的树构成的森林112BDCAKJHIGEFABCEDFHG先序遍历序列KIJABJFEHGIKCD对应二叉树的先序遍历113BDCAKJHIGEFBCDFAEHK中序遍历序列IJGABJFEHGIKCD对应二叉树的中序遍历1146.6哈夫曼（Huffman）树及其应用6.6.1最优二叉树（哈夫曼树）问题：什么是哈夫曼树？例：将学生的百分制成绩转换为五分制成绩：≥90分:A，

80～89分:B，70～79分:C，60～69分:D，＜60分:E。转换程序可用条件语句实现：if(a<60)b==‘E’;elseif(a<70)b==‘D’;elseif(a<80)b==‘C’;elseif(a<90)b==‘B’;elseb==‘A’;a<60a<70a<80a<90EDCBAYYYYNNNN判别树：用于描述分类过程的二叉树。115若学生的成绩数据共10000个：5%15%40%30%10%如果每次的输入量很大，则应考虑程序的操作时间。31500次a<80a<90a<70a<60EYDCBANYYYNNN5%15%则5％的数据需