数据结构第6章树南京工程学院通信工程学院.ppt

前面我们学习的线性数据结构，每个元素都有唯一的前驱（第一个除外）和后继（最后一个除外），但是在现实应用中，一些问题的数据元素之间的关系就不这样简单，例如在编译程序中，用树表示源程序的语法结构。 本章学习一种非线性数据结构树，数据元素之间是一种层次关系，元素有且只有一个前驱，但可以有多个后继。,第六章 树和二叉树,树的概念和基本术语 二叉树 二叉树遍历 线索二叉树 树与森林 霍夫曼树,第六章 树和二叉树,6.1树的概念和基本术语,树的定义 树是由 n (n 0) 个结点的有限集合。如果 n = 0，称为空树；如果 n 0，则 有且仅有一个特定的称之为根(Root)的结点，它只有直接后继，但没有直接前驱； 当n 1，除根以外的其它结点划分为 m (m 0) 个互不相交的有限集 T1, T2 , Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。,例如,A,只有根结点的树,有13个结点的树,其中:A是根,其余结点分成三个互不相交的子集， T1=B,E,F,K,L； T2=C,G； T3=D,H,I,J,M, T1,T2,T3都是根A的子树，且本身也是一棵树,树的基本术语 树的结点：包含一个数据元素及若干指向子树的分支； 孩子结点：结点的子树的根称为该结点的孩子 双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；,兄弟结点：同一双亲的孩子结点； 堂兄结点：双亲在同一层的结点互为堂兄弟。 结点的层次：根结点的层定义为1；根的孩子为第二层结点，依此类推；,树的高度：树中结点的最大层次. 结点的度：结点子树的个数 树的度： 树内各结点的度的最大值。 叶子结点：也叫终端结点，是度为0的结点； 分枝结点：度不为0的结点； 有序树：子树有序的树，（子树不能互换）如：家族树； 无序树：不考虑子树的顺序；,任何一棵非空树是一个二元组 Tree = （root，F） 其中：root 被称为根结点， F 被称为子树森林,森林：,是m（m0）棵互 不相交的树的集合,A,root,F,路径：树中的k 个结点n1,n2， ，nk，满足ni 是ni + 1 的双亲，n1到nk有一条路径 路径长度：分支数路径上结点个数一1,根没有双亲，叶子没有孩子； vi是vj 的双亲，则L ( vi ) = L(vj)- 1 ; 堂兄弟的双亲是兄弟关系吗？ 有序树和无序树的区别；,注意,对比树型结构和线性结构的结构特点,线性结构,树型结构,第一个数据元素 (无前驱),根结点 (无前驱),最后一个数据元素 (无后继),多个叶子结点 (无后继),其它数据元素 (一个前驱、 一个后继),其它数据元素 (一个前驱、 多个后继),树的常见表示方法,1.直观表示法：用圆圈表示结点，元素写在圆圈中，连线表示元素之间的关系.根在上，叶子在下（即树向下生长）,2 、集合表示法： 根据树的集合定义，写出集合划分。 3 、文氏图表示法： 集合表示的一种直观表示，用图表示集合。,4 、目录表示法： 将一棵树描述为一本书，书-章-节-小节,5 、广义表表示法： 将一棵树描述为一个广义表，子树就对应子表。,人们最常用的是第一种，但是不适合计算机！,基本操作,InitTree（T）； 操作结果：构造空树T。 DestroyTree（T）； 初始条件：树T存在。 操作结果：销毁树T。 CreateTree（T，definition） 初始条件：definition给出树T的定义。 操作结果：按definition构造树T。 ClearTree（T）； 初始条件：树T存在。 操作结果：将树T清为空树。 TreeEmpty（T） 初始条件：树T存在。 操作结果：若T为空树，则返回ture，否则false。,TreeDepth（T） 初始条件：树T存在。 操作结果：返回T的深度。 Root（T） 初始条件：树T存在。 操作结果：返回T的根。 Value（T, Cur_e） 初始条件：树T存在，cure是T中某 个结点。 操作结果：返回cure的值。 Assign（T，cur_e，value） 初始条件：树T存在，cure是T中某个结点。 操作结果：结点cur_e赋值 为value。 Parent（T，cure） 初始条件：树T存在，cure是T中某个结点。 操作结果：若cure是T的非根结点，则返回它的双亲，否则函数值为“空”。 Rightsibling（T，cure） 初始条件：树T存在，cure是T中某个结点 操作结果：若cure有右兄弟，则返回它的右兄弟，否则函数值为“空”。,LeftChild（T，cure） 初始条件：树T存在，cure是T中某个结点。 操作结果：若cure是T的非叶子结点，则返回它的最左孩子，否则返回“空”。 InsertChild（T，p，i，c）； 初始条件：树T存在，p指向T中某个结点，1ip所指结点的度1，非空树c与T不相交。 操作结果：插入c为T中p指结点的第i棵子树。 DeleteChild（T，p，i）； 初始条件：树T存在，p指向T中某个结点，1ip指结点的度。 操作结果：删除T中p所指结点的第i棵子树。 TraverseTree（T，visit（）； 初始条件：树T存在，visit是对结点操作的应用函数。 操作结果：按某种次序对T的每个结点调用函数visit() 一次且至多一次.一旦visit（）失败，则操作失败,6.2 二叉树 6.2.1 二叉树的概念 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构,定义:二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。,A,B,C,D,E,F,G,H,K,根结点,左子树,右子树,6.2.1二叉树定义 (Binary Tree),二叉树的五种基本形态：,N,空树,只含根结点,N,N,N,L,R,R,右子树为空树,L,左子树为空树,左右子树均不为空树,应用举例 例 可以用二叉树表示表达式,a+b*(c-d)-e/f,性质1 在二叉树的第 i 层上至多有 2i 1个结点。(i 1) 证明用归纳法 证明：当i=1时，只有根结点，2 i-1=2 0=1。 假设对所有j，ij1，命题成立，即第j层上至多有2 j-1 个结点。 由归纳假设第i-1 层上至多有 2i 2个结点。 由于二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，即2* 2i 2= 2 i-1。,6.2.6 二叉树的性质,性质2 深度为 k 的二叉树至多有 2 k-1个结点(k 1)。 证明：由性质1可见，深度为k的二叉树的最大结点数为,性质3 对任何一棵二叉树T, 如果其叶结点数为 n0, 度为2的结点数为 n2,则n0n21. 证明：若度为1的结点有 n1 个，总结点个数为 n，总边数为 e，则根据二叉树的定义， n = n0 + n1 + n2 e = 2n2 + n1 = n - 1 因此，有 2n2 + n1 = n0 + n1 + n2 - 1 n2 = n0 - 1 n0 = n2 + 1,定义1 满二叉树 (Full Binary Tree) 一棵深度为k且有2 k-1个结点的二叉树称为满二叉树。,两种特殊形态的二叉树,满二叉树,非完全二叉树,定义2 完全二叉树 (Complete Binary Tree) 若设二叉树的高度为h，则共有h层。除第 h 层外，其它各层 (0 h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。,完全二叉树,性质4 具有 n (n 0) 个结点的完全二叉树的深度为log2(n) 1 证明： 设完全二叉树的深度为 h，则根据性质2和完全二叉树的定义有 2h1 - 1 n 2h- 1或 2h1 n 2h 取对数 h1 log2n h，又h是整数， 因此有 h = log2(n) 1,性质5 如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号0, 1, 2, , n-1，则有以下关系： 若i = 0, 则 i 无双亲 若i 0, 则 i 的双亲为(i -1)/2 若2*i+1 n, 则 i 的左子女为 2*i+1，若2*i+2 n, 则 i 的右子女为2*i+2 若结点编号i为偶数，且i!=0,则左兄弟结点i-1. 若结点编号i为奇数，且i!=n-1,则右兄弟结点为i+1.,性质5：在完全二叉树中编号（1开始）为i的结点， 1）若有左孩子，则左孩编号为2i； 2）若有右孩子，则有孩子结点编号为2i+1； 3）若有双亲，则双亲结点编号为 i/2；,2i +2,2i 2i+1 2i+2 2i+3 i+1 2i 2i+1,i,i i+1,6.2.3 二叉树的存储结构 二叉树也可以采用两种存储方式：顺序存储结构和链式存储结构。,顺序存储结构 其存储形式为：用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。,# define MAX_TREE_SIZE 100 /二叉树的最大结点数 typedef TElemType SqBiTreeMAX_TREE_SIZE; /0号单元存放根结点 SqBiTree bt;,一般二叉树 的顺序表示,顺序表示,完全二叉树 的顺序表示,请分析：深度为k的且只有k个结点的单支树需要长度为？,2. 链式存储结构 在顺序存储结构中，利用编号表示元素的位置及元素之间孩子或双亲的关系，因此对于非完全二叉树，需要将空缺的位置用特定的符号填补，若空缺结点较多，势必造成空间利用率的下降。在这种情况下，就应该考虑使用链式存储结构。 常见的二叉树结点结构如下所示：,其中，Lchild和Rchild是分别指向该结点左孩子和右孩子的指针，data是数据元素的内容。,typedef struct BiTNode TElemType data; struct BiTNode Lchild,*Rchlid; BTNode,*BTree;,G H,D E F,B C,A,举例,这种存储结构的特点是寻找孩子结点容易，双亲比较困难。因此，若需要频繁地寻找双亲，可以给每个结点添加一个指向双亲结点的指针域，其结点结构如下所示。,typedef struct TriTNode / 结点结构 TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指针 struct TriTNode *parent; /双亲指针 TriTNode, *TriTree;,二叉树链表表示的示例,三叉链表,二叉树,二叉链表,三叉链表的静态结构,上面们二叉链表或三叉链表是用指针实现，是一种动态的 链式存储结构，链式存储结构也可用一维数组来实现， 用一维数组表示的二叉链表或三叉链表，称为静态链表,6.3 二叉树的遍历,遍历：按某种搜索路径访问二叉树的每个结点，而且每个结点仅被访问一次。 访问：含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据。 遍历是各种数据结构最基本的操作，许多其他的操作可以在遍历基础上实现。 对于线性结构由于每个结点只有一个直接后继，遍历是很容易的事,二叉树是非线性结构，每个结点可能有两个后继，如何访问二叉树的每个结点，而且每个结点仅被访问一次？,6.3.1 二叉树的遍历方法 二叉树由根、左子树、右子树三部分组成 二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树,令：L：遍历左子树 D：访问根结点 R：遍历右子树 有六种遍历方法： DLR，LDR，LRD， DRL，RDL，RLD,约定先左后右,有三种遍历方法： DLR、LDR、LRD ,分别称为 先序遍历、中序遍历、后序遍历,先序遍历（DLR） 若二叉树非空 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树；,先序遍历序列：A,B,D,E,G,C,F,例：先序遍历右图所示的二叉树 （1）访问根结点A （2）先序遍历左子树：即按DLR的顺序遍历左子树 （3）先序遍历右子树：即按DLR的顺序遍历右子树,中序遍历（LDR） 若二叉树非空 （1）中序遍历左子树 （2）访问根结点 （3）中序遍历右子树,中序遍历序列： D,B,G,E,A,C,F,例：中序遍历右图所示的二叉树 （1）中序遍历左子树：即按LDR的顺序遍历左子树 （2）访问根结点A （3）中序遍历右子树：即按LDR的顺序遍历右子树,后序遍历（LRD） 若二叉树非空 （1）后序遍历左子树 （2）后序遍历右子树 （3）访问根结点,后序遍历序列： D,G,E,B,F,C,A,例：后序遍历右图所示的二叉树 （1）后序遍历左子树：即按LRD的顺序遍历左子树 （2）后序遍历右子树：即按LRD的顺序遍历右子树 （3）访问根结点A,后序遍历序列：a,b,c,d,-,*,+,e,f,/,-,中序遍历序列：a,+,b,*,c,-,d,-,e,/,f,先序遍历序列：-,+,a,*,b,-,c,d,/,e,f,例：先序遍历、中序遍历、后序遍历下图所示的二叉树,这实际上是先序遍历的递归定义，我们知道递归定义包括两个部分： 1）基本项（也叫终止项）； 2）递归项,若二叉树非空 （1）访问根结点； （2）先序遍历左子树 （3）先序遍历右子树；,先序遍历递归定义 递归项,二. 遍历的递归算法 上面介绍了三种遍历方法，显然是用递归的方式给出的三种遍历方法，以先序为例： 先序遍历（DLR）的定义：,该定义隐含着若二叉树为空，结束,上面先序遍历的定义等价于： 若二叉树为空，结束 基本项（也叫终止项） 若二叉树非空 递归项 （1）访问根结点； （2）先序遍历左子树 （3）先序遍历右子树；,下面给出先序、中序、后序遍历递归算法，为了增加算法的可读性，这里对书上算法作了简化，没有考虑访问结点出错的情况（即我们假设调用函数visit( )访问结点总是成功的。,先序遍历递归算法 void PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e) /采用二叉链表存贮二叉树, visit( )是访问结点的函数。本算法先序遍历以为根结点指针的二叉树，对每个数据元素调用函数Visit( ) if (T) /若二叉树不为空，访问根结点；遍历左子树,遍历右子树 Visit(T-data)； PreOrderTraverse(T-lchild, Visit); PreOrderTraverse(T-rchild, Visit); /PreOrderTraverse,最简单的Visit函数是： Status PrintElement(TElemType e) /输出元素e的值 printf(e); return OK;,2 中序遍历递归算法 void InOrderTraverse(BiTree T, Status(*Visit)(TElemType e) /采用二叉链表存贮二叉树， visit( )是访问结点的 /数。本算法中序遍历以为根结点指针的二叉树，/对每个数据元素调用函数Visit( ) if (T) /若二叉树为空，结束返回 / 若二叉树不为空，遍历左子树，访问根结点，/遍历右子树 InOrderTraverse(T-lchild, Visit); Visit(T-data)； InOrderTraverse(T-rchild, Visit); / InOrderTraverse,3 后序遍历递归算法 void PostOrderTraverse(BiTree T, Status(* Visit)(TElemType e) /采用二叉链表存贮二叉树， visit( )是访问结点的/函数。本算法中序遍历以为根结点指针的二叉/树，对每个数据元素调用函数Visit( ) if (T) /若二叉树为空，结束返回 / 若二叉树不为空，遍历左子树，遍历右子树， /访问根结点 PostOrderTraverse(T-lchild, Visit); PostOrderTraverse(T-rchild, Visit); Visit(T-data)； /PostOrderTraverse,例: 已知一棵二叉树的中根序列和先根序列分别为ABCDEFGHIJK和EBADCFHGIKJ，试画出这棵二叉树。,4.中序遍历二叉树(非递归算法)用栈实现,b a,a b入栈,b退栈 访问,d入栈,d退栈 访问,e 退栈 访问,e c,栈空,a退栈 访问,c e 入栈,c 退栈 访问,void InOrder ( BinTree T ) stack S; InitStack( ,线索二叉树 遍历是二叉树最基本最常用的操作。 1）对二叉树所有结点做某种处理可在遍历过程中实现; 2）查找二叉树某个结点，可通过遍历实现； 与线性表相比，对二叉树的遍历存在如下问题： 1）遍历算法要复杂的多，费时的多； 2）为检索或查找二叉树中某结点在某种遍历下的后继，必须从根开始遍历，直到找到该结点及后继； 如果能将二叉树线性化，就可以减化遍历算法，提高遍历速度。,5.4 线索二叉树 (Threaded Binary Tree),如何将二叉树线性化？ 以中序遍历为例，我们看到通过遍历可以得到二叉树结点的中序序列。若能将中序序列中每个结点前趋、后继信息保存起来，以后再遍历二叉树时就可以根据所保存的结点前趋、后继信息对二叉树进行遍历。,加上结点前趋后继信息（线索）的二叉树 称为线索二叉树,中序遍历序列：D,B,H,E,A,F,C,G 在中序序列中，D的后继是B，H的前趋是B，后继是E,加上结点前趋后继信息（结索）的二叉树称为线索二叉树,孩子指针 前趋指针 后继指针,2线索链表 线索二叉树的存贮方法： 1） 为每个结点增加二个标志域。 缺点：要点用较多的内存空间。 有n个结点的二叉链表，有n+1个空指针域,故可利用这些的空指针域存放结点的前趋和后继指针，以这种结点的构成二叉链表称为线索链表,对线索链表中结点的约定：,在二叉链表的结点中增加两个标志域， 并作如下规定： 若该结点的左子树不空， 则Lchild域的指针指向其左子树， 且左标志域的值为“指针 Link”； 否则，Lchild域的指针指向其“前驱”， 且左标志的值为“线索 Thread” 。 若该结点的右子树不空， 则rchild域的指针指向其右子树， 且右标志域的值为 “指针 Link”； 否则，rchild域的指针指向其“后继”， 且右标志的值为“线索 Thread”。,Ltag=0, lchild为左子女指针 Ltag=1, lchild为前驱线索 Rtag=0, rchild为右子女指针 Rtag=1, rchild为后继指针,结点结构,线索链表的类型说明 typedef enumlink,threadPointerTag; /link=0, thread=1 typedef struct BiThrNode TElemType data; Struct BiThrNode *lchild, *rchild; /左右指针域 PointerTag Ltag, Rtag; /左右标志域，标志域为0时表示左右指针域存储的是左右孩子的指针，标志域为1时表示左右指针域存储的是前趋后继结点的指针 BiThrNode，*BiThrTree,为简化线索链表的遍历算法，仿照线性链表，为线索链表加上一头结点.约定：,头结点的lchild域：存放线索链表的根结点指针 头结点的rchild域: 中序序列最后一个结点指针 中序序列第一结点lchild域指向头结点; 中序序列最后一个结点的rchild域指向头结点;,如图标出的中序二叉树结点的顺序，可看出 1）中序序列的第一结点，是二叉树的最左下结点； 2）若p所指结点的右孩子域为线索，则p的右孩子结点即为后继结点； 3）若p所指结点的右孩子域为孩子指针，则p的后继结点为其右子树的最左下结点；,中序遍历序列：D,B,H,E,A,F,C,G,3线索二叉树的遍历 在二叉树上加上结点前趋、后继线索后，可利用线索对二叉树进行遍历。 基本步骤： 1） p=T-lchild; p指向线索链表的根结点； 2）若线索链表非空，循环： （a）循环，顺着p左孩子指针找到最左下结点；访问 之 （b）若p所指结点的右孩子域为线索， p的右孩子结点即为后继结点循环： p=p-rchild； 并访问p所指结点；（在此循环中，顺着后继线索访问二叉树中的结点） （c） 一旦线索“中断”，p所指结点的右孩子域为右孩子指针，p=p-rchild，使 p指向右孩子结点； 3）返回OK；结束,线索链表的遍历算法 Void InOrderTraverse_Thr(BiThrTree T, Status (* Visit) (TE1emType e) / T指向头结点，头结点的左链lchild指向根结点， / 中序遍历二叉线索树T算法，对每个数据元素调用函数Visit。 P=T-lchild; /p指向根结点 While(p!=T) / 空树或遍历结束时，p= =T While(p-Ltag= =Link) p= p-lchild; /找到最左下结点；访问之 Visit(p-data) while (p-Rtag= =Thread /InOrderTraverse_Thr,树的存储结构在树中，每个结点即可能有孩子也可能有双亲，所以既可以通过保存每个结点的孩子结点位置来表示结点之间的结构关系，也可以通过保存每个结点的双亲结点位置来表示结点之间的结构关系。 1.双亲表示：通过保存每个结点的双亲结点的位置，表示树中结点之间的结构关系。 以一组连续空间存储树的结点，同时在结点中附设一个指针，存放双亲结点在链表中的位置。,树与森林,* 便于涉及双亲的操作； * 求结点的孩子时需要遍历整棵树。,特点:,用双亲表示实现的树定义,#define MaxSize /最大结点个数 typedef char TreeData; /结点数据 typedef struct /树结点定义 TreeData data; int parent; /双亲位置域 TreeNode; typedef TreeNode TreeMaxSize; /树,2、孩子表示法 孩子表示法：通过保存每个结点的孩子结点的位置，表示树中结点之间的结构关系。,方法一: 顺序 存储,#define MAX_TREE_SIZE 100 typedef struct PTNode TElemType data; int child1; /第1个孩子位置域 int child2; /第2个孩子位置域 int childd; /第d个孩子位置域 PTNode; typedef struct PTNode nodesMAX_TREE_SIZE; int n; /结点数 PTree;,孩子表示法举例,* 便于涉及孩子的操作；求双亲不方便； * 采用同构的结点，空间浪费。,方法二:链式存储：对树的每个结点用线性链表存贮它的孩子结点,树的孩子链表类型定义 typedef struct CTNode /孩子结点 int child; struct CTNode * next; * ChildPtr; typedef struct TElemType data; ChildPtr firstchild; /孩子链表头指针 CTBox; typedef struct CTBox nodesMAX_TREE_SIZE; Int n, r; /结点数和根的位置； CTree;,孩子链表存储表示举例,* 便于涉及孩子的操作； * 求结点的双亲时不方便。,T.nodes ; T.n=10; T.r = 0;,结点结构,3 孩子兄弟表示法(二叉链表示法) 孩子兄弟表示法用二叉链表作为树的存贮结构,typedef struct CSNode ELemType data; struct CSNode *firstchild,*nextsibling; CSNode, *CSTree;,类型定义:,孩子兄弟表示法示例：,树与二叉树的转换 二叉树与树都可用二叉链表存贮，以二叉链表作中介，可导出树与二叉树之间的转换。 树与二叉树转换方法,特点：一棵树转换成二叉树后，根结点没有右孩子。,此二叉链表既是树(a) 的孩子兄弟表示又是二叉树(b)的二叉链表,由此可将 树与二叉树 对应起来,森林 森林：树的集合 将森林中树的根看成兄弟，可用树孩子兄弟表示法存储森林；用树与二叉树的转换方法，进行森林与二叉树转换；可用树的遍历方法对森林进行遍历；,包含两棵树的森林,如果F=T1,T2, ,Tm是森林,则可按如下规则转换成一棵二叉树B=(root,LB,RB)。 (1)若F为空，即m=0,则B为空树； (2)若F非空，则B的根root即为森林中第一棵树的根ROOT(T1)； B的左子树LB是从T1中根结点的子树森林F1=T11,T12, ,T1m1转换而成的二叉树; 其右子对RB是从森林F=T2,T3, ,Tm 转换而成的二叉树.,森林与二叉树的转换,二叉树转换成森林,如果B=(root,LB,RB)是一棵二叉树,则可按如下规则转换成森林F=T1,T2, ,Tm： (1)若B为空，则F为空； (2)若B非空，则F中第一棵树T1的根ROOT(T1)即为二叉树B的根root； T1中的根结点的子树森林 F1是由B的左子树LB转换而成的森林; F中除T1之外其余树组成的森林F=T2,T3, ，Tm是由B的右子树RB转换而成的森林。,当树非空时 访问根结点 依次先根遍历根的各棵 子树 树先根遍历 ABEFCDG 对应二叉树前序遍历 ABEFCDG 树的先根遍历结果与其对应二叉树 表示的前序遍历结果相同 树的先根遍历可以借助对应二叉树 的前序遍历算法实现,树的先根次序遍历,树的遍历,树的后根次序遍历:,当树非空时 依次后根遍历根的各棵 子树 访问根结点 树后根遍历 EFBCGDA 对应二叉树中序遍历 EFBCGDA 树的后根遍历结果与其对应二叉树 表示的中序遍历结果相同 树的后根遍历可以借助对应二叉树 的中序遍历算法实现,森林的两种遍历方法：,一、先序遍历森林： 若森林非空，则 （1）访问森林中第一棵树的根结点； （2）先序遍历第一棵树的根结点的子树森林； （3）先序遍历除去第一棵树之后的森林。 二、中序遍历森林： 若森林非空，则 （1）中序遍历第一棵树的根结点的子树森林； （2）访问森林中第一棵树的根结点； （3）中序遍历除去第一棵树之后的森林。,霍夫曼树 (Huffman Tree),在二叉树中，一个结点到另一个结点之间 的分支构成这两个结点之间的路径。 在路径上的分支数目被称为路径长度。 树的带权 路径长度是树的各叶结点所带的权值 wi 与该结点到根的路径长度 li 的乘积的和。 用公式可表示为：,WPL = 2*2+ WPL = 2*1+ WPL = 7*1+ 4*2+5*2+ 4*2+5*3+ 5*2+2*3+ 7*2 = 36 7*3 = 46 4*3 = 35,带权路径 长度达到最小,霍夫曼树,假设有n个权值1, 2, , n，试构造一棵有n个叶子结点的二叉树,每个叶子结点带权为i, 则其中： 带权路径长度WPL最小的二叉树称做 最优二叉树 或赫夫曼树. 在霍夫曼树中，权值大的结点离根最近。,构造赫夫曼树的算法思想,(1) 根据给定的n个权值w1,w2, ,wn构成n棵二叉树的集合F=T1,T2, ,Tn其中每棵二叉树Ti中只有一个带权为Wi的根结点,其左右子树均空. (2) 在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为其左.右子树根结点的权值之和. (3) 在F中删除这两棵树,同时将新得到的二叉树加入F中. (4) 重复(2)和(3),直到F只含一棵树为止.这棵树便是赫夫