数据结构（C语言版）（第三版）（微课版）第5章 树和二叉树

第5章树教学要求相关知识点常用术语：树、二叉树、完全二叉树、满二叉树、节点、节点的度、树的高度、有序树、无序树、Huffman树树及二叉树的存储结构二叉树的遍历树和二叉树之间的转换Huffman树学习重点二叉树的存储结构二叉树的遍历Huffman树目录二叉树树和森林哈夫曼树5树的概念126本章小结7二叉树的存储结构二叉树的遍历345.1树的概念5.1树的概念树的定义1.树的定义树（Tree）是n（n≥0）个有限数据元素的集合。当n＝0时，称这棵树为空树。在一棵非空树T中：有一个特殊的数据元素称为树的根节点，根节点没有前驱。若n>1，除根节点之外的其余数据元素被分成m（m>0）个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤i≤m）又是一棵树，称为根节点的子树。2.树的特点树的根节点没有前驱节点，除根节点之外的所有节点有且只有一个前驱节点。树中所有节点可以有零个或多个后继节点。5.1树的概念树的基本术语（1）节点表示树中的元素，包括数据项及若干指向其子树的分支。如图5.1中的A~M均为节点。5.1树的概念（2）节点的宽度节点所拥有的子树的个数称为该节点的宽度（简称为度）。如图5.1中A的度为3，B的度为2，C的度为1，D的度为3，E的度为0。5.1树的概念（3）叶节点或终端节点度为0的节点称为叶节点，或者称为终端节点。如图5.1中的E、K、L、G、H、M、J为叶节点。5.1树的概念（4）分枝节点或非终端节点度不为0的节点称为分支节点，或者称为非终端节点。一棵树的节点除叶节点外，其余的都是分支节点。如图5.1中的A、B、C、D、F、I为分支节点。5.1树的概念（5）树的宽度树的度是指树中各节点度的最大值。如图5.1中的树的宽度为3。5.1树的概念（6）孩子节点或子节点一个节点含有的子树的根节点称为该节点的孩子节点或子节点。图5.1中的A节点含有的子树T1的根节点B就为A节点的一个孩子节点。5.1树的概念（7）双亲节点或父节点若一个节点含有子节点，则这个节点称为其子节点的双亲节点或父节点。图5.1中的A节点含有子节点B，则A节点称为B节点的父节点。5.1树的概念（8）兄弟节点有相同父节点的节点互称为兄弟节点。如图5.1中的B、C、D为兄弟节点，有相同的父节点A。5.1树的概念（9）节点的祖先指从根到该节点所经分支上的所有节点。如图5.1中K节点的祖先为A、B、F。5.1树的概念（10）子孙以某节点为根的子树中的任一节点都称为该节点的子孙。如图5.1中B节点的子孙为E、F、K、L。5.1树的概念（11）节点的层数规定树的根节点的层数为1，其余节点的层数等于它的双亲节点的层数加1。如图5.1中A节点的层次为1，B、C、D节点的层次为2，以此类推。5.1树的概念（12）堂兄弟节点双亲节点在同一层且双亲节点不相同的节点互为堂兄弟。如图5.1中的E与G为堂兄弟，其双亲节点B与C在同一层但不相同。5.1树的概念（13）树的度(高度或深度)树中所有节点的最大层数称为树的度，如图5.1中树的度为4。5.1树的概念（14）路径、路径长度如果一棵树的一串节点n0，n1，…，nk-1有如下关系：节点ni是ni+1的父节点(0≤i<k-1)，就把n0，n1，…，nk-1称为一条由n0至nk-1的路径。这条路径的长度是k-1。（15）有序树和无序树如果一棵树中节点的各子树丛左到右是有次序的，即若交换了某节点各子树的相对位置，则构成不同的树，称这棵树为有序树；反之，则称为无序树。5.1树的概念（16）森林零棵或有限棵不相交的树的集合称为森林。自然界中树和森林是不同的概念，但在数据结构中，树和森林只有很小的差别。任何一棵树，删去根节点就变成了森林。5.2二叉树5.2二叉树二叉树的定义1.二叉树的递归形式定义二叉树（BinaryTree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。5.2二叉树2.二叉树具有五种基本形态5.2二叉树3.两类特殊的二叉树（1）满二叉树在一棵二叉树中，如果所有分支节点都存在左子树和右子树，并且所有叶子节点都在同一层上。5.2二叉树（2）完全二叉树一棵深度为k的有n个节点的二叉树，对树中的节点按从上至下、从左到右的顺序进行编号，如果编号为i(0≤i≤n-1)的节点与满二叉树中编号为i的节点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。特点：叶子节点只能出现在最下层和次下层，且最下层的叶子节点集中在树的左部。5.2二叉树二叉树的性质性质1

一棵非空二叉树的第i层上最多有2i-1个节点（i≥1）。性质2

一棵深度为k的二叉树中，最多具有2k-1个节点。

性质3

对于一棵非空的二叉树，如果叶子节点数为n0，度数为2的节点数为n2，则有:n0＝n2＋1。

性质4

具有n个节点的完全二叉树的深度k为。

5.2二叉树二叉树的性质性质5

对于具有n个节点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有节点从1对n顺序编号，则对于任意的序号为i的节点，有：（1）若i=1，则该节点是二叉树的根节点，无双亲节点，否则，编号为

i/2

的节点为其双亲节点。（2）如果2i≤n，则序号为i的节点的左孩子节点的序号为2i；如果2i>n，则序号为i的节点无左孩子。（3）如果2i＋1≤n，则序号为i的节点的右孩子节点的序号为2i＋1；如果2i＋1>n，则序号为i的节点无右孩子。5.3二叉树的存储结构5.3二叉树的存储结构二叉树的顺序存储结构用一组连续的存储单元存放二叉树中的节点。一般是按照二叉树节点从上至下、从左到右的顺序存储。增添一些并不存在的空节点，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。5.3二叉树的存储结构二叉树的顺序存储表示可描述为：#defineMaxNode10/*二叉树的最大节点数*/typedefelemtypeSqBiTree[MaxNode]/*0号单元存放根节点*/SqBiTreebt;5.3二叉树的存储结构二叉树的链式存储与操作1.二叉链表存储每个节点由三个域组成，除了数据域外，还有两个指针域，给出该节点左孩子和右孩子所在的节点的存储地址。5.3二叉树的存储结构二叉树的链式存储与操作1.二叉链表存储用C语言的类型描述二叉链表结构如下:typedefstructBiTNode/*节点结构*/{TElemTypedata;structBiTNode*lchild,*rchild; /*左右孩子节点指针*/}BiTNode,*BiTree;

5.3二叉树的存储结构2.三叉链表存储每个节点由四个域组成，除了data、lchild以及rchild三个域外，增加parent域指向该节点双亲节点的指针。lchilddatarchildparent5.3二叉树的存储结构3.二叉树的基本操作(1)Initiate(bt)建立一棵空二叉树。intInitiate(BiTreebt)/*建立二叉树，0表示建立失败，1表示成功*/{if((*bt=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)return0;

*bt->lchild=NULL;

*bt->rchild=NULL;return1;}5.3二叉树的存储结构(2)Create(x)生成以x为根节点数据域的二叉树。算法5.2生成一棵二叉树BiTreeCreate(elemtypex){BiTreep;if((p=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)returnNULL;p->data=x;p->lchild=NULL;p->rchild=NULL;returnp;}5.3二叉树的存储结构(3)InsertL(bt，x，parent)将数据域为x的节点插入到二叉树bt中作为节点parent的左孩子节点。如果节点parent原来有左孩子节点，则将节点parent原来左孩子节点作为节点x左孩子节点。

BiTreeInsertL(BiTreebt,elemtypex,BiTreeparent)/*在bt的节点parent的左子树中插入节点数据元素x*/{BiTreep;if(parent==NULL){printf(“\n插入出错”);returnNULL;}5.3二叉树的存储结构if((p=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)returnNULL;p->data=x;p->lchild=NULL;p->rchild=NULL;if(parent->lchild==NULL)parent->lchild=p;else{p->lchild=parent->lchild;parent->lchild=p;}returnbt;}5.3二叉树的存储结构(4)InsertR(bt，x，parent)将数据域为x的节点插入到二叉树bt中作为节点parent的右孩子节点。如果节点parent原来有右孩子节点，则将节点parent原来的右孩子节点作为节点x的右孩子节点。5.3二叉树的存储结构(5)DeleteL(bt，parent)在二叉树bt中删除节点parent的左子树。算法5.4在二叉树中删除节点BiTreeDeleteL(BiTreebt，BiTreeparent){BiTreep;if(parent==NULL||parent->lchild==NULL){printf("\n删除出错")；returnNULL;}p=parent->lchild;parent->lchild=NULL;free(p);returnbr;}5.3二叉树的存储结构(6)DeleteR(bt，parent)在二叉树bt中删除节点parent的右子树。(7)Search(bt，x)在二叉树bt中查找数据元素x。(8)Traverse(bt)按某种方式遍历二叉树bt的全部节点。5.4二叉树的遍历5.4二叉树遍历遍历算法二叉树的遍历是指按照某种顺序访问二叉树中的每个节点，使每个节点被访问一次且仅被访问一次。1.深度优先遍历深度优先遍历是指从根节点开始，以递归的形式一棵子树一棵子树的遍历。一棵树由根节点、根节点的左子树和根节点的右子树三部分组成。若以D、L、R分别表示访问根节点、遍历根节点的左子树、遍历根节点的右子树，并规定先左后右，则二叉树的遍历方式有三种方式，即DLR(称为先序遍历)、LDR(称为中序遍历)和LRD(称为后序遍历)。5.4二叉树遍历（1）先序（根）遍历（DLR）先序遍历的递归过程为：若二叉树为空，遍历结束。否则，访问根节点；先序遍历根节点的左子树；先序遍历根节点的右子树。5.4二叉树遍历算法5.5DLR先序(根)遍历voidPreOrder(BiTreebt)/*先序遍历二叉树bt*/{if(bt==NULL)return;//递归调用结束条件Visit(bt->data); /*访问节点的数据域*/PreOrder(bt->lchild);//先序递归遍历bt左子树PreOrder(bt->rchild);//先序递归遍历bt右子树}5.4二叉树遍历【例5.1】对如图5.11所示的二叉树进行先序遍历。解答：第一步：先访问根节点A。第二步：发现A节点有左右子树，遵循先左后右的原则进入A的左子树，访问左子树的根B。以B为根的子树只有右子树D，所以访问D。第三步：至此，A的左子树已经访问完了，接着进入A的右子树，访问C。所以，先序遍历上述二叉树的顺序为ABDC。5.4二叉树遍历（2）中序遍历（LDR）中序遍历的递归过程为：若二叉树为空，遍历结束。否则，（1）中序遍历根节点的左子树；（2）访问根节点；（3）中序遍历根节点的右子树。5.4二叉树遍历算法5.6LDR中序(根)遍历voidMidOrder(BiTreebt)/*中序遍历二叉树bt*/{if(bt==NULL)return;//递归调用结束条件MidOrder(bt->lchild);//中序递归遍历bt左子树Visit(bt->data);/*访问节点的数据域*/MidOrder(bt->rchild);//中序递归遍历bt右子树}5.4二叉树遍历【例5.2】对图5.11所示的二叉树

进行中序遍历。解答：第一步：发现A节点有左右子树，进入A的左子树，由于A的左子树无左子树，所以访问左子树的根B。再访问以B为根的子树的右子树，所以访问D。第二步：再访问根节点A。第三步：接着进入A的右子树，访问C。所以，中序遍历图5.11所示的二叉树的顺序为BDAC。5.4二叉树遍历（3）后序遍历（LRD）后序遍历的递归过程为：若二叉树为空，遍历结束。否则，（1）后序遍历根节点的左子树；（2）后序遍历根节点的右子树；（3）访问根节点。5.4二叉树遍历算法5.7LRD后(根)序遍历voidPostOrder(BiTreebt){if(bt==NULL)return;//递归调用的结束条件PostOrder(bt->lchild);//后序递归遍历bt左子树PostOrder(bt->rchild);//后序递归遍历bt右子树

Visit(bt->data);/*访问节点的数据域*/}5.4二叉树遍历【例5.3】对如图5.11所示的

二叉树进行后序遍历。解答：第一步：发现A节点有左右子树，进入A的左子树，由于A的左子树无左子树，所以遍历A的左子树的右子树，即访问D，再访问A的左子树的根B。第二步：接着进入A的右子树，访问C。第三步：最后访问根节点A。所以，后序遍历图5.11所示的二叉树的顺序为DBCA。5.4二叉树遍历【例5.4】对如图5.12所示的二叉树进行先序遍历、中序遍历、后序遍历。ABEFGHICD解答：先序遍历结果：中序遍历结果：后序遍历结果：BDCAEHGIFDCBHIGFEA5.4二叉树遍历2.广度优先的层次遍历所谓二叉树的层次遍历，是指从二叉树的第一层（根节点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对节点逐个访问。遍历算法如下：(1)将根节点入队；(2)若队列为空，则结束；(3)否则队首节点出队并访问，再将其左右孩子节点按照先左后右的顺序分别入队，继续执行(2)。5.4二叉树遍历算法5.8层次遍历二叉树voidLevelOrder(BiTreebt){BiTreeQueue[MaxNode];

intfront,rear;

if(bt==NULL)exit(0);

front=-1;/*front为队头元素的前一个位置*/

rear=-1;/*rear为队尾当前位置*/

Queue[++rear]=bt;/*树根入队(先修改rear再入队)*/5.4二叉树遍历

while(front!=rear)

{

/*访问队首节点的数据域，队头出队(先修改front再访问)*/

Visit(Queue[++front]->data);

/*将队首节点的左孩子节点入队*/

if(Queue[front]->lchild!=NULL)

{Queue[++rear]=Queue[front]->lchild;}

/*将队首节点的右孩子节点入队*/

if(Queue[front]->rchild!=NULL)

{Queue[++rear]=Queue[front]->rchild;}

}}5.4二叉树遍历【例5.5】对图5.12所示的二叉树进行层次遍历。rearAfront-15.4二叉树遍历【例5.5】对图5.12所示的二叉树进行层次遍历。

解答：层次遍历结果：ArearEBfront-15.4二叉树遍历【例5.5】对图5.12所示的二叉树进行层次遍历。

解答：层次遍历结果：ABrearCEfront-15.4二叉树遍历【例5.5】对图5.12所示的二叉树进行层次遍历。

解答：层次遍历结果：ABErearFCfront-15.4二叉树遍历【例5.5】对图5.12所示的二叉树进行层次遍历。

解答：层次遍历结果：ABECrearDFfront-15.4二叉树遍历【例5.5】对图5.12所示的二叉树进行层次遍历。

解答：层次遍历结果：ABECFrearGDfront-15.4二叉树遍历【例5.5】对图5.12所示的二叉树进行层次遍历。

解答：层次遍历结果：ABECFDrearGfront-15.4二叉树遍历【例5.5】对图5.12所示的二叉树进行层次遍历。

解答：层次遍历结果：ABECFDGrearIHfront-15.4二叉树遍历【例5.5】对图5.12所示的二叉树进行层次遍历。

解答：层次遍历结果：ABECFDGHrearIfront-15.4二叉树遍历【例5.5】对图5.12所示的二叉树进行层次遍历。

解答：层次遍历结果：ABECFDGHIrearfront-15.4二叉树遍历线索二叉树1.线索二叉树节点结构线索二叉树是给二叉链表的左右孩子链表域赋予新的含义并增加两个标志域使得结构如图5.13所示。lchildltagdatartagrchild当节点有左子树，即lchild域不为空时，ltag为0。当节点没有左子树，即lchild为空时，令lchild域指向该节点的前驱，ltag为1。当节点有右子树，即rchild域不为空时，rlag为0。当节点没有右子树，即rchild为空时，令rchild域指向该节点的后继，rtag为1。5.4二叉树遍历2.线索二叉树结构体描述typedefstructBiThrNode{ElemTypedata;

BiThrNode*lchild,*rchild;

intltag,rtag;}BiThrNode,*BiThrTree以此节点构成的二叉链表作为二叉树的存储结构，叫作线索链表，其中指向节点前驱和后继的指针称作线索。加上线索的二叉树叫线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程称作线索化。5.4二叉树遍历3.线索二叉树的实现线索二叉树的表示方法：当节点有左右子树时，用实线箭头指向其左右孩子节点；当节点没有左右子树时，用虚线箭头指向该节点的前驱或后继。序列中最后一个节点的右指针可以为空。【例5.6】画出如图5.14所示的二叉树的先序、中序、后序线索化后的线索二叉树。5.4二叉树遍历(1)该二叉树的先序遍历的结果是abdce先序线索二叉树如图5.15所示。5.4二叉树遍历(2)该二叉树中序遍历的结果是bdaec中序线索二叉树如图5.16所示。5.4二叉树遍历(3)该二叉树后序遍历的结果是dbeca后序线索二叉树如图5.17所示。5.4二叉树遍历(1)中序线索二叉树的建立算法5.9中序线索二叉树的建立BiThrTreeInOrderThr(BiThrTreeT)/*中序遍历二叉树T，中序线索化，*head指向头节点*/{BiThrTreehead;

if(!(head=(BiThrNodeType*)malloc(sizeof(BiThrNodeType))))returnNULL;

head->ltag=0;

head->rtag=1; /*建立头节点*/head->rchild=head; /*右指针回指*/5.4二叉树遍历

if(!T)head->lchild=head;/*若二叉树为空，则左指针回指*/

else

{head->lchild=T;pre=head;

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

pre->rchild=head;

pre->rtag=1;/*最后一个节点线索化*/

head->rchild=pre;

}

returnhead;}5.4二叉树遍历(2)中序线索二叉树的遍历算法5.10中序线索二叉树的遍历voidInThreading(BiThrTreep)/*中序遍历进行中序线索化*/{if(p)

{InThreading(p->lchild);//左子树线索化if(!p->lchild)/*对无左孩子的节点p进行前驱线索化到节点pre*/{p->ltag=1;p->lchild=pre;}5.4二叉树遍历if(!pre->rchild)/*对无右孩子的节点pre进行后继线索化到节点p*/{pre->rtag=1;pre->rchild=p;}pre=p;//pre保存刚访问过的节点，p为下一个要访问的节点InThreading(p->rchild);/*右子树线索化*/}}5.4二叉树遍历(3)在中序线索二叉树上查找中序前驱节点算法5.11在中序线索二叉树上查找中序前驱节点BiThrTreeInPreNode(BiThrTreep)/*在中序线索二叉树上查找节点p的中序前驱节点*/{BiThrTreepre;pre=p->lchild;//中序线索p节点若有左孩子，则其前驱一定是其左孩子的最深层的右孩子节点if(p->ltag!=1) while(pre->rtag==0)pre=pre->rchild;

return(pre);}5.4二叉树遍历(4)在中序线索二叉树上查找中序后继节点算法5.12中序线索二叉树上查找中序后继节点BiThrTreeInPostNode(BiThrTreep)/*在中序线索二叉树上查找节点p的中序后继节点*/{BiThrTreepost;post=p->rchild;//中序线索p节点若有右孩子，则其后继一定是其右孩子的最深层的左孩子节点if(p->rtag!=1) while(post->ltag==0)post=post->lchild;

return(post);}5.5树和森林5.5树和森林树和森林的存储1.双亲存储法双亲存储法：用一组连续的存储空间(一维数组)存储树中的各个节点，数组中的一个元素表示树中的一个节点，数组元素为结构体类型，其中包括节点本身的信息以及节点的双亲节点在数组中的序号。双亲存储法的实现：定义数组结构存放树的节点，每个节点含有两个域，分别为数据域和双亲域。数据域存放节点本身的信息，双亲域存放该节点的父节点的位置。

5.5树和森林typedefstructnode{ElemTypedata;

intparent;}TreeNode;TreeNodetree[M];5.5树和森林图5.18所示的树对应的双亲存储法的存储结构如图5.19所示。

dataparent01a2b

3c4d5e6f7g8

h011225555.5树和森林2.孩子链表存储法孩子链表存储法：使用一个与节点个数相同大小的一维数组，数组的每一个元素由两个域组成，一个域用来存放节点信息，另一个用来存放指针，该指针指向由该节点的孩子节点组成的单链表的首位置。单链表结构由两个域组成，一个存放孩子节点在一维数组中的序号，另一个是指针域，指向下一个孩子节点。用一组连续的空间存储树的所有节点，然后给每个节点加上一个单链表，单链表是由其孩子节点组成的。每个节点的孩子节点用单链表存储，再用含M个元素的结构数组指向每个孩子链表。5.5树和森林2.孩子链表存储法(1)孩子节点typedefstructChildNode{intChild;/*节点在表头数组中的下标*/

structChildNode*next;/*指向下一个孩子节点在表头数组中的下标位置*/};5.5树和森林2.孩子链表存储法(2)表头节点typedefstructHeadNode{ElemTypedata;/*数据域*/

structChildNode*firstchild;/*指向第一个孩子节点*/};HeadNodet[M];5.5树和森林图5.18所示的树对应的孩子链表存储法的存储结构如图5.20所示。5.5树和森林3.双亲孩子存储法双亲孩子存储法：将双亲存储法和孩子链表存储法相结合的结果。其仍将各节点的孩子节点分别组成单链表，同时用一维数组顺序存储树中的各节点，数组元素除了包括节点本身的信息和该节点的孩子节点链表的头指针之外，还增设了一个域，用来存储该节点双亲节点在数组中的序号。每个节点的孩子节点用单链表存储，再用含M个元素的结构数组指向每个孩子链表。结构数组存放树的节点，每个节点含有三个域，分别为数据域、双亲域和第一个孩子节点的地址。5.5树和森林3.双亲孩子存储法(1)孩子节点typedefstructChildNode{intChild;/*节点在表头数组中的下标*/

structChildNode*next;/*指向下一个孩子节点在表头数组中的下标位置*/};5.5树和森林3.双亲孩子存储法(2)表头节点typedefstructHeadNode{ElemTypedata;/*数据域*/

intparent;/*双亲域*/

structChildNode*firstchild;/*指向第一个孩子节点*/};HeadNodet[M];5.5树和森林图5.18所示的树对应的双亲孩子存储法的存储结构如图5.21所示。5.5树和森林4.孩子兄弟存储法孩子兄弟存储法:用二叉链表存储树和森林，在树中，每个节点除其信息域外，再增加了两个指针，分别指向该节点的第一个孩子节点和下一个兄弟节点的指针。树中节点的存储表示可描述为：typedefstructTreeNode{ElemTypedata;

structNode*firstchild;structNode*nextsibling;}TreeNode;5.5树和森林图5.18所示的树对应的孩子兄弟存储法的存储结构如图5.22所示。5.5树和森林二叉树、树和森林的转换1.树转换为二叉树在树中所有相邻兄弟之间加一条连线。对树中的每个节点，只保留它与第一个孩子节点之间的连线，删去它与其他孩子节点之间的连线。以树的根节点为轴心，将整棵树顺时针转动一定的角度，使之结构层次分明。5.5树和森林2.森林转换为二叉树

将森林中的每棵树转换成相应的二叉树；将森林中第一棵二叉树不动，第一棵树的根节点作为二叉树的根节点；将森林中第一棵树的子孙节点作为二叉树的左子树；从第二棵二叉树开始，依次把后一棵二叉树的根节点作为前一棵二叉树根节点的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树。5.5树和森林【例5.7】将如图5.23所示的森林转换为对应的二叉树转换的二叉树如右图所示5.5树和森林3.二叉树转换为树和森林由二叉树的根节点作为森林中第一棵树的根节点；二叉树的左子树作为森林中第一棵树的子孙；二叉树的右子树作为森林中第一棵树的兄弟。可以依据二叉树的根节点有无右分支，将一棵二叉树还原为树或森林，具体方法如下：(1)若某节点是其双亲的左孩子，则把该节点的右孩子、右孩子的右孩子都与该节点的双亲节点用线连起来；(2)删去原二叉树中所有双亲节点与右孩子节点的连线；(3)整理由(1)、(2)两步所得到的树或森林，使之结构层次分明。5.5树和森林树和森林的遍历1.树的遍历(1)先根遍历访问根节点；按照从左到右的顺序先根遍历根节点的每一棵子树。树的先根遍历与其转换的相应二叉树的先序遍历的结果序列相同。5.5树和森林1.树的遍历(2)后根遍历按照从左到右的顺序后根遍历根节点的每一棵子树；访问根节点。树的后根遍历与其转换的相应二叉树的中序遍历的结果序列相同。5.5树和森林2.森林的遍历(1)先序遍历访问森林中第一棵树的根节点；先序遍历第一棵树的根节点的子树；先序遍历去掉第一棵树后的子森林。森林的先序遍历与所转换的二叉树的先序遍历的结果序列相同。5.5树和森林2.森林的遍历(2)中序遍历中序遍历第一棵树的根节点的子树；访问森林中第一棵树的根节点；中序遍历去掉第一棵树后的子森林。森林的中序遍历与所转换的二叉树的中序遍历的结果序列相同。5.6哈夫曼树5.6哈夫曼树哈夫曼树的定义哈夫曼（Haffman）树也称最优二叉树，是指对一组带权的叶节点，构造的具有最小带权路径长度的二叉树。节点的路径长度：从根节点到该节点的路径上分支数。

节点权值：附加在节点上的信息。

节点带权路径：节点上权值与该节点到根之间的路径长度的乘积。

二叉树的路径长度：由根节点到所有叶节点的路径长度之和。

5.6哈夫曼树二叉树的带权路径长度：设二叉树具有n个带权的叶节点，那么从根节点到各个叶节点的路径长度与相应节点权值的乘积之和称作二叉树的带权路径长度，记为：WPL(T)=

wklk(权重为wk，路径为lk)哈夫曼(Huffman)树：使WPL取最小值的二叉树，又称最优二叉树。5.6哈夫曼树【例5.10】计算如图5.25所示二叉树的WPL。解答：WPL(T)=1×2+8×2+5×3+7×4+2×2=655.6哈夫曼树哈夫曼树的存储定义哈夫曼树的存储定义如下：typedefstruct{intweight;intparent;intlchild;intrchild;}HNodeType;5.6哈夫曼树哈夫曼树的构造算法哈夫曼提出哈夫曼树的构造算法，也叫哈夫曼算法。(1)由给定的n个权值{w1，w2，…，wn}构成n棵只有一个节点的二叉树的集合F={T1，T2，…，Tn}，即每棵二叉树Ti只有一个权值为Wi的根节点，其左右子树均空；(2)在F中选两棵根节点的权值最小和次小的两棵二叉树作为左右子树构成一棵新的二叉树，且根节点的权值为其左右子树根节点的权值之和；(3)在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中；(4)重复步骤(2)和(3)，直到F只含一棵二叉树，这棵二叉树便是所要构造的哈夫曼树。5.6哈夫曼树【例5.9】已知权值W={5，6，3，10，7}，请构造一棵哈夫曼树。解答：第1步：根据给定的5个权值构成5棵只有一个节点的二叉树，如图5.26(a)所示；第2步：选择权值为3、5的节点构成一棵新的二叉树，如图5.26(b)所示；5.6哈夫曼树第3步：在F中删除权值分别为3、5两个二叉树，并将新二叉树权8加入到F中，得F={7、6、10、8}；第4步：在F={7、6、10、8}中选择6、7的节点树作为左右子树构成一棵新的二叉树，如图5.26(c)所示；5.6哈夫曼树第5步：在F中删除权值分别为6、7两个二叉树，并将新二叉树权13加入到F中，得F={13、10、8}；第6步：在F={13、10、8}中选择8、10的节点作为左右子树构成一棵新的二叉树，如图5.27(a)所示；5.6哈夫曼树第7步：在F中删除权值分别为8、10两个二叉树，并将新二叉树权183加入到F中，得F={13、18}；第8步：在F={13、18}中只能选择13、18的节点作为左右子树构成一棵新的二叉树，如图5.27(b)所示；5.6哈夫曼树第9步：在F中删除权值分别为13、18两个二叉树，并将新二叉树权31加入到F中，得F={31}；第10步：至此，F={31}仅含有一棵树，所以该树即为哈夫曼树。由上述构造算法可知，哈夫曼树的形式不唯一。5.6哈夫曼树哈夫曼树的建立过程5.6哈夫曼树哈夫曼树的构造算法已知n个字符的权值，生成一棵哈夫曼树。算法5.13哈夫曼树的构造voidHaffmanTree(HNodeTypeHuffNode[MAXLEAF]){inti,j,m1,m2,x1,x2;