《数据结构教程》-第六章

第6章树6.3遍历二叉树和线索二叉树

6.3.1遍历二叉树

6.3.2恢复二叉树

6.3.3线索二叉树6.4二叉树的转换

6.4.1一般树转换为二叉树

6.4.2森林转换为二叉树

6.4.3二叉树转换为树和森林下一页返回上一页第6章树6.5二叉树的应用

6.5.1二叉树的基本应用

6.5.2标识符树与表达6.6哈夫曼树及其应用

6.6.1哈夫曼树的引入

6.6.2哈夫曼树的建立

6.6.3哈夫曼编码返回上一页6.1树的定义和术语6.1.1树的定义1.树的定义树(Tree)是n(n≥0)个有限数据元素的集合。在任意一棵非空树T中:(1)有且仅有一个特定的称为树根(Root)的结点，根结点无前趋结点;(2)当n>1时，除根结点之外的其余结点被分成m(m>0)个互不相交的集合T1,T2,…,Tm，其中每一个集合Ti(1≤i≤m)本身又是一棵树，并且称为根的子树。树的定义采用了递归定义的方法，即在树的定义中又用到树的概念，这正好反映了树的固有特性下一页返回6.1树的定义和术语2.树的其他表示法图6-2是树的结构表示法，是一种直观的画法，其特点是对树的逻辑结构的描述非常直观、清晰，是使用最多的一种描述方法。除此以外，还有以下几种描述树的方法。(1)嵌套集合法嵌套集合法，一也称为文氏图法(VennDiagram)，它是用集合以及集合的包含关系来描述树形结构，每个圆圈表示一个集合，套起来的圆圈表示包含关系。图6-3(a)就是一棵树的嵌套集合表示。(2)圆括号表示法圆括号表示法一也称为广义表表示法，它是使用括号将集合层次与包含关系显示出来。下式即是图6-2所示树的圆括号表示法。下一页返回上一页6.1树的定义和术语(A(B(D，E(I，J)，F)，C(G，H)))(3)凹入法凹入法是用不同宽度的行来显示各结点，而行的凹入程度体现了各结点集合的包含关系，图6-2所示树的凹入表示法如图6-3(b)所示。树的凹入表示法主要用于树的屏幕显示和打印输出。下一页返回上一页6.1树的定义和术语6.1.2基木术语(1)结点—树的结点包含一个数据及若干指向其子树的分支。(2)结点的度—结点所拥有的子树数称为该结点的度(Degree)。(3)树的度—树中各结点度的最大值称为该树的度。(4)叶子(终端结点)—度为零的结点称为叶子结点。(5)分支结点—度不为零的结点称为分支结点。(6)兄弟结点—同一父亲结点下的子结点称为兄弟结点。(7)层数—树的根结点的层数为1，其余结点的层数等于其双亲结点的层数加1。(8)树的深度—树中结点的最大层数称为树的深度(或高度)。下一页返回上一页6.1树的定义和术语(9)森林—零棵或有限棵互不相交的树的集合称为森林。在数据结构中，树和森林并不像自然界里有一个明显的量的差别。任何一棵树，只要删去根结点就成了森林，如图6-4所示。(10)有序树和无序树—树中结点的各子树从左到右是有次序的(即不能互换位置)，称这样的树为有序树;否则称为无序树。返回上一页6.2二叉树6.2.1二叉树的定义1.定义二叉树是有n(n>=o)个结点的有限集合。(1)该集合或者为空(n=o);(2)或者由一个根结点及两个不相交的分别称为左子树和右子树组成的非空树;(3)左子树和右子树又同样都是二叉树。通俗地讲:在一棵非空的二叉树中，每个结点至多只有两棵子树，分别称为左子树和右子树，且左右子树的次序不能任意交换。所以，二叉树是特殊的有序树。下一页返回6.2二叉树2.二叉树的形态根据定义，二叉树可以有五种基本形态，如图6-5所示。其中:图6-5(a)表示空二叉树;

图6-5(b)表示仅有根结点的二叉树;

图6-5(c)表示右子树为空的二叉树;

图6-5(d)表示左子树为空的二叉树;

图6-5(e)表示左、右子树均非空的二叉树。下一页返回上一页6.2二叉树3.二叉树的基本操作(1)CreateBT():创建一棵二叉树。(2)ShowTree(BT*T):按凹入法显示二叉树。(3)Preorder(BT*T):按先序(根、左、右)遍历二叉树上所有结点。(4)Inorder(BT*T):按中序(左、根、右)遍历二叉树上所有结点。(5)Poatorder(BT*T):按后序(左、右、根)遍历二叉树上所有结点。(6)Levelorder(BT*T):按层次遍历二叉树上所有结点。(7)Leafnum(BT*T):求二叉树叶结点总数。(8)TreeDepth(BT*T):求二叉树的深度。下一页返回上一页6.2二叉树6.2.2二叉树的性质性质1一棵非空二叉树的第i层上最多有2i-1个结点(i≥1)。一棵非空二叉树的第一层有1个结点，第二层最多有2个结点，第三层最多有4个结点……，利用归纳法即可证明第i层上最多有2i-1个结点。性质2深度为h的二叉树中，最多具有2h-1个结点(h≥1)。1.满二叉树一棵深度为h，且有2h-1个结点的二叉树称为满二叉树。图6-6所示是一棵深度为4的满二叉树，其特点是每一层上的结点都具有最大的结点数。如果对满二叉树的结点进行连续编号，约定编号从根结点起，自上向下、自左向右(如图6-6所示)，由此可以引出完全二叉树的定义。下一页返回上一页6.2二叉树2.完全二叉树深度为h，有n个结点的二叉树，当且仅当每一个结点都与深度为h的满二叉树中编号从1至n的结点一一对应时，称此二叉树为完全二叉树。如图6-7(a)所示为一棵完全二叉树。如图6-7(b)所示则不是完全二叉树。完全二叉树除最后一层外，其余各层都是满的，并且最后一层或者为满，或者仅在右边缺少连续若干个结点。性质3对于一棵有n个结点的完全二叉树，若按满二叉树的方法对结点进行编号(见图6-6所示)，则对于任意序号为i的结点，有下一页返回上一页6.2二叉树(1)若i>1，则序号为i的结点的父结点的序号为i/2;若i=1，则序号为i的结点是根结点。(2)若2i≤n，则序号为i的结点的左孩子结点的序号为2i;若2i>n，则序号为i的结点无左孩子。(3)若2i+1≤n，则序号为i的结点的右孩子结点的序号为2i+1;若2i+1>n，则序号为i的结点无右孩子。证明略。下一页返回上一页6.2二叉树性质4具有n(n>0)个结点的完全二叉树(包括满二叉树)的深度(h)为[log2n]+1证由性质2和完全二叉树定义可知，当完全二叉树的深度为h、结点个数为n时对不等式取对数有h-1≤log2n<h由于h是整数，所以有h=[log2n]+1。下一页返回上一页6.2二叉树性质5对于一棵非空的二叉树，设n0,n1,n2分别表示度为0,1,2的结点个数，则有n0=n2+1。证(1)设n为二叉树的结点总数，则有n=n0+n1+n2(6-1)(2)根据假设，各结点的子结点总数(C)为C=n1+2n2(6-2)(3)因二叉树中只有根结点不是任何结点的孩子，所以由式(6-2)推出的二叉树中的结点总数又可表示为n=n1+2n2+1(6-3)下一页返回上一页6.2二叉树式综合式(6-1)、式(6-2)、式(6-3)可以得到n0+n1+n2=n1+2n2+1n0=n2+1所以命题正确。下一页返回上一页6.2二叉树6.2.3二叉树的存储1.顺序存储结构二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。一般可以采用一维数组或二维数组的方法进行存储。(1)一维数组存储法二叉树中各结点的编号与等深度的完全二叉树中对应位置上结点的编号相同。其编号过程为:首先把根结点的编号定为1，然后按照层次从上至下、从左到右的顺序，对每一个结点编号。当双亲结点为i时，其左孩子的编号为2i，其右孩子的编号为2i+1。在图6-8(a)中，各结点右边的数字就是该结点的编号。下一页返回上一页6.2二叉树对于一般的二叉树，如果按从上到下、从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系，只有增加一些并不存在的空结点，使之成为一棵完全二叉树的形式才能用一维数组进行存储。图6-8(a)经过改造以后成为图6-8(b)所示的完全二叉树。其顺序存储状态示意图如图6-8(c)所示。显然，这种存储结构会造成空间的大量浪费，如图6-9(a)所示，一棵4个结点的二叉树，却要扩充为图6-9(b)所示的完全二叉树，分配14个存储单元后如图6-9(b)。可以证明，深度为h的(右向)单支二叉树，虽然只有h个结点，却需分配2h-1个存储单元。下一页返回上一页6.2二叉树对于完全二叉树和满二叉树。这种顺序存储结构既能够最大限度地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，因为完全二叉树上编号为i的结点元素存储在一维数组下标为i-1的分量中，如图6-9(c)所示。(2)二维数组存储法设二叉树的结点数为n，可以将二维数组的容量定义为[n][3],即n行3列。仍以图6-7(a)所示的二叉树为例，并按二维数组存储的下标重新对结点编号如图6-10(a)所示，设data为结点数据，leftno为结点左子树号，rightno为结点右子树号，则其存储如图6-10(b)所示。下一页返回上一页6.2二叉树顺序存储小结:(1)当二叉树为满二叉树或完全二叉树时，采用一维数组可以节省存储空间;(2)当二叉树层数高而结点较少时，采用二维数组比较好，只要n行3列存储空间;(3)顺序存储的优点是找父结点的位置方便;(4)顺序存储的缺点是进行插人或删除操作要进行大量的数据移动，且存储空间的扩充不方便。2.链式存储结构二叉树的链式存储结构是用链表来表示二叉树，即用链指针来指示结点的逻辑关系。通常有下面两种形式。下一页返回上一页6.2二叉树(1)二叉链表存储二叉链表结点由一个数据域和两个指针域组成，其结构如下:其中，data为数据域，存放结点的数据信息;lchild为左指针域，存放该结点左子树的存储地址;rchild为右指针域，存放该结点右子树的存储地址。当左子树或右子树不存在时，相应指针域值为空，用符号八表示。设一棵二叉树如图6-11所示，其二叉链表的存储如图6-12所示。下一页返回上一页6.2二叉树容易证明，在含有n个结点的二叉链表中有n+1个空指针域。利用这些空指针域存储其他有用信息，从而可以得到另外一种存储结构—线索化链表，关于这一概念将在6.3.3节介绍。下面给出二叉树的二叉链表描述:下一页返回上一页6.2二叉树(2)三叉链表存储三叉链表结点由一个数据域和三个指针域组成，其结构如下:其中，data为数据域，存放结点的数据信息;lchild为左指针域，存放该结点左子树的存储地址;rchild为右指针域，存放该结点右子树的存储地址。parent为父指针域，存放结点的父结点存储地址。这种存储结构既便于查找左、右子树的结点，又便于查找父结点;但付出的代价是增加了存储空间的开销。图6-13给出了二叉树的三叉链表存储示意图。返回上一页6.3

遍历二叉树和线索二叉树6.3.1遍历二叉树二叉树的遍历是指按某种顺序访问二叉树中的所有结点，使得每个结点都被访问，且仅被访问一次。通过一次遍历，使二叉树中结点的非线性序列转变为线性序列。也就是说，使遍历的结点序列之间有一个一对一的关系。由二叉树的递归定义可知，一棵二叉树由根结点(D)、根结点的左子树(L)和根结点的右子树(R)三部分组成。因此，只要依次遍历这三个部分，就可以遍历整个二叉树。若以D,L,R分别表示访问根结点、遍历根结点的左子树、遍历根结点的右子树，则二叉树的遍历方式有六种不同的组合:DLR,LDR,LRD,DRL,RDL和RLD。下一页返回6.3

遍历二叉树和线索二叉树一般限定先左后右的次序，那么只有三种遍历:DLR(根左右)、LDR(左根右)、LRD(左右根)。1.先序遍历(DLR)的递归过程若二叉树为空，遍历结束。否则，(1)访问根结点;(2)先序遍历根结点的左子树;(3)先序遍历根结点的右子树。下一页返回上一页6.3

遍历二叉树和线索二叉树图6-11所示的二叉树，按先序遍历所得到的结点序列为:ABDGCEFH2.中序遍历(LDR)的递归过程若二叉树为空，遍历结束。否则，(1)中序遍历根结点的左子树;(2)访问根结点;(3)中序遍历根结点的右子树。下一页返回上一页6.3

遍历二叉树和线索二叉树图6-11所示的二叉树，按中序遍历所得到的结点序列为:DGBAECHF3.后序遍历(LRD)的递归过程若二叉树为空，遍历结束。否则，(1)后序遍历根结点的左子树;(2)后序遍历根结点的右子树。(3)访问根结点;下一页返回上一页6.3

遍历二叉树和线索二叉树图6-11所示的二叉树，按后序遍历所得到的结点序列为:GDRFHFCA4.层次遍历按照自上而下(从根结点开始)，从左到右(同一层)的顺序逐层访问二叉树上的所有结点，这样的遍历称为按层次遍历。按层次进行遍历时，当一层结点访问完成后，接着访问下一层的结点，先遇到的结点先访问，这与队列的操作原则是一致的。因此，在进行层次遍历时，可设置一个数组来模拟队列，用于保存被访问结点的子结点的地址。遍历从二叉树的根结点开始，首先将根结点指针送人队列，然后从队头取出一个元素，每取一个元素，执行下面两个操作。(1)访问该元素所指结点。下一页返回上一页6.3

遍历二叉树和线索二叉树(2)若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针依次入队。此过程不断进行，直到队空为止。在下面的层次遍历算法中，以二叉链表方式存储，一维数组q[MAXLEN]用以实现队列，lchild和rhild分别是被访问结点的左、右指针。下一页返回上一页6.3

遍历二叉树和线索二叉树下一页返回上一页6.3

遍历二叉树和线索二叉树图6-11所示的二叉树，按层次遍历所得到的结果序列为:ARCDFFGH[例6-1]二叉树，如图6-14所示，求它的先序遍历、中序遍历、后序遍历和层次遍历。先序遍历的序列:ABDGEHCFIK;中序遍历的序列:DGBHEAFKIC后序遍历的序列:GDHEBKIFCA;层次遍历的序列:ABCDEFGHIK[例6-2]设表达式A-B*(C+D)+E/(F+G)的二叉树表示如图6-15所示。试写出它的先序遍历、中序遍历和后序遍历。下一页返回上一页6.3

遍历二叉树和线索二叉树先序遍历的结果(即前缀表达):+-A*R+CD/E+FG;中序遍历的结果:A-B*C+D+E/F+G;后序遍历(即后缀表达式):ABCD+*-EFG+/+。6.3.2恢复二叉树任意一棵二叉树结点的先序序列和中序序列都是唯一的，那么能否根据结点的先序序列和中序序列，来唯一确定一棵二叉树呢?回答是肯定的。二叉树的先序遍历是先访问根结点，然后再遍历根结点的左子树，最后遍历根结点的右子树。即在先序序列中，第一个结点必定是二叉树的根结点。下一页返回上一页6.3

遍历二叉树和线索二叉树中序遍历则是先遍历左子树，然后访问根结点，最后再遍历右子树。这样，根结点在中序序列中必然将中序序列分割成两个子序列，前一个子序列是根结点左子树的中序序列，而后一个子序列是根结点右子树的中序序列。根据这两个子序列，先由先序序列确定第一个结点为根结点;知道根结点后，按中序序列可以划分左、右子树。在先序序列中，左子树序列的第一个结点是左子树的根结点，右子树序列的第一个结点是右子树的根结点。这样，就确定了二叉树的三个结点。同时，左子树和右子树的根结点又可以分别把中序序列中的左子序列和右子序列划分成两个子序列，如此递归下去，当取尽先序序列中的结点时，便可以恢复一棵二叉树。下一页返回上一页6.3

遍历二叉树和线索二叉树1.由先序和中序恢复二又树(1)根据先序序列确定树的根(第一个结点)，根据中序序列确定左子树和右子树;(2)分别找出左子树和右子树的根结点，并把左、右子树的根结点连到父(father)结点上去;(3)再对左子树和右子树按此法找根结点和左、右子树，直到子树只剩下1个结点或2个结点或空为止。[例6-3]由下列前序序列和中序序列恢复二叉树。先序序列:ACBRSEDFMLK中序序列:RBSCEAFDLKM下一页返回上一页6.3

遍历二叉树和线索二叉树首先，由先序序列可知，结点A是二叉树的根结点;其次，根据中序序列，在A之前的所有结点都是根结点左子树的结点，在A之后的所有结点都是根结点右子树的结点。继续对左、右子树进行分解。下一页返回上一页6.3

遍历二叉树和线索二叉树再按同样的方法继续分解下去，最后得到图6-16所示的整棵二叉树。上述过程是一个递归过程，其递归算法的思想是:首先根据先序序列的第一个元素建立根结点;其次在中序序列中找到该元素，确定根结点的左、右子树的中序序列;再次在先序序列中确定左、右子树的先序序列;最后由左子树的先序序列与中序序列建立左子树，由右子树的先序序列与中序序列建立右子树。2.由中序和后序恢复二又树由二叉树的后序序列和中序序列一也可唯一地确定一棵二叉树。其方法为:(1)根据后序序列找出根结点(最后一个)，根据中序序列确定左、右子树;下一页返回上一页6.3

遍历二叉树和线索二叉树(2)分别找出左子树和右子树的根结点，并把左、右子树的根结点连到父(father)结点上去;(3)再对左子树和右子树按此法查找根结点和左、右子树，直到子树只剩下1个结点或2个结点或空为止。[例6-4]由下列中序序列和后序序列恢复二叉树。中序序列:CBEDAGHFJI后序序列:CEDBHGJIFA首先，由后序序列可知，结点A是二叉树的根结点;其次，根据中序序列，在A之前的所有结点都是根结点左子树的结点，在A之后的所有结点都是根结点右子树的结点。下一页返回上一页6.3

遍历二叉树和线索二叉树下一页返回上一页6.3

遍历二叉树和线索二叉树再按同样的方法继续分解下去，最后得到图6-17所示的整棵二叉树。思考:根据二叉树的前序序列和后序序列能唯一恢复一棵二叉树吗?6.3.3线索二叉树1.什么是线索二叉树遍历二叉树是按一定的规则将二叉树中所有结点排列为一个有序序列，实质上是对一个非线性的数据结构进行线性化的操作。经过遍历的结点序列，除第一个结点和最后一个结点以外，其余每个结点都有且仅有一个直接前驱结点和一个直接后继结点。下一页返回上一页6.3

遍历二叉树和线索二叉树当以二叉链表作为存储结构时，只能找到结点的左、右孩子的信息，而不能直接得到结点任意一个序列中的直接前趋结点和直接后继结点是什么，这种信息只有在对二叉树遍历的动态过程中才能得到。若增加前趋和后继指针将使存储密度进一步降低。在用二叉链表存储的二叉树中，单个结点的二叉树有两个空指针域，如图6-18(a)所示，两个结点的二叉树有三个空指针域，如图6-18(b)所示。不难证明:n个结点的二叉树有n+1个空指针域。一也就是说一个具有n个结点的二叉树，若采用二叉链表存储结构，在其总共2n个指针域中只有n-1个指针域是用来存储结点子树的地址，而另外n+1个指针域存放的都是空指针域。可以充分利用二叉链表存储结构中的那些空指针域，来保存结点在某种遍历序列中的直接前趋和直接后继的地址信息。下一页返回上一页6.3

遍历二叉树和线索二叉树指向直接前趋结点或指向直接后继结点的指针称为线索(Thread)，带有线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。2.线索二叉树的方法由于二叉树结点的序列可由不同的遍历方法得到，因此，线索二叉树也有先序线索二叉树中序线索二叉树和后序线索二叉树三种。在三种线索二叉树中一般以中序线索化用得最多,所以下面以图6-19所示的二叉树为例，说明中序线索二叉树的方法。(1)先写出原二叉树的中序遍历序列:DGBAECHF;(2)若结点的左子树为空，则此线索指针将指向前一个遍历次序的结点;(3)若结点的右子树为空，则此线索指针将指向下一个遍历次序的结点。下一页返回上一页6.3

遍历二叉树和线索二叉树其中，序线索二叉树的结果如图6-19所示。其中实线表示指针，虚线表示线索。3.线索二叉树的优点任意一个结点都能找到它的前一个或后一个遍历顺序的结点。4.线索二叉树的缺点(1)结点的插入和删除麻烦，且速度也较慢。(2)线索子树不能共用。返回上一页6.4

二叉树的转换6.4.1一般树转换为二叉树如果对树或森林采用链表存储并设定一定的规则，就可用二叉树结构表示树和森林。这样，对树的操作实现就可以借助二叉树存储，利用二叉树上的操作来实现。1.一般树和二又树的二又链表存储结构比较一般树是无序树，树中结点各孩子的次序是无关紧要的;二叉树中结点的左、右孩子结点是有区别的。为避免发生混淆，约定树中每一个结点的孩子结点按从左到右的次序排列。如图6-20所示为一棵一般树。根结点A有B,C,D三个孩子，可以认为结点B为A的长子，结点C为B的次弟，结点D为C的次弟。一般树和二叉树的二叉链表有储结构示意图如图6-21所示。下一页返回6.4

二叉树的转换2.将一棵树转换为二又树的方法只要把一般树的长子作为其父结点的左子树;把一般树的次弟作为其兄结点的右子树，即可以把一棵一般树转换为一棵二叉树。整个转换可以分为三步:(1)连线—链接树中所有相邻的亲兄弟之间连线。(2)删线—保留父结点与长子的连线，打断父结点与非长子结点之间的连线。(3)旋转—以根结点为轴心，将整棵树顺时针旋转一定的角度，使之层次分明。可以证明，树作这样的转换所构成的二叉树是唯一的。图6-22(a),(b),(c)给出了图6-20所示的一般树转换为二叉树的转换过程。下一页返回上一页6.4

二叉树的转换结论:(1)在转换产生的二叉树中，左分支上的各结点在原来的树中是父子关系;而右分支上的各结点在原来的树中是兄弟关系。(2)由于树的根结点无兄弟，所以转换后的二叉树的根结点必定无右子树。(3)一棵树采用长子、兄弟表示法所建立的存储结构与它所对应的二叉树的二叉链表存储结构是完全相同的。(4)一般树转换为二叉树以后，将使树的深度增加。如图6-20所示的树深度为4，转换为二叉树以后，深度就变成7了，如图6-22(c)所示。下一页返回上一页6.4

二叉树的转换6.4.2森林转换为二叉树森林是若干棵树的集合。只要将森林中的每一棵树的根视为兄弟，而每一棵树又可以用二叉树表示，这样，森林也同样可以用二叉树来表示了。森林转换为二叉树的方法如下:(1)将森林中的每一棵树转换成相应的二叉树。(2)第一棵二叉树保持不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右子树，直到把最后一棵二叉树的根结点作为其前一棵二叉树的右子树为止。[例6-5]将图6-23给出的森林转换为二叉树。[例6-6]将图6-25(a)给出的二叉树转换为一般树。下一页返回上一页6.4

二叉树的转换6.4.3二叉树转换为树和森林树转换为二叉树以后，其根结点必定无右子树;而森林转换为二叉树以后，其根结点有右分支。显然这一转换过程是可逆的，即可以依据二叉树的根结点有无右子树，将一棵二叉树还原为树或森林。二叉树转换为树或森林的方法如下(图6-24):(1)若某结点是其父结点的左孩子，则把该结点的右孩子、右孩子的右孩子，直到最后一个右孩子都与该结点的父结点连起来;(2)删掉原二叉树中所有的父结点与右孩子结点的连线;(3)整理使之层次分明，显示出树或森林的形状。返回上一页6.5

二叉树的应用6.5.1二叉树的基木应用1.统计二叉树叶子结点数(1)基本思想若二叉树结点的左子树和右子树都为空，则该结点为叶子结点，count+1;递归统计T的左子树叶结点数;递归统计T的右子树叶结点数。(2)算法下一页返回6.5

二叉树的应用下一页返回上一页6.5

二叉树的应用2.求二又树结点总数(1)基本思想若二叉树根结点不为空，则计数器count加1;递归统计T的左子树结点数;递归统计T的右子树结点数。(2)算法下一页返回上一页6.5

二叉树的应用3.求二叉树的深度(1)基本思想若二叉树为空，则返回0，否则递归统计左子树的深度;递归统计右子树的深度;递归结束，返回其中大的一个加1,即为二叉树的深度。(2)算法下一页返回上一页6.5

二叉树的应用下一页返回上一页6.5

二叉树的应用4.查找数据元素在bt为根结点指针的二叉树中查找数据元素x。查找成功时返回该结点的指针;查找失败时返回空指针。(1)基本思想先判别二叉树的根结点是否与x相等，若相等则返回，否则递归在bt->lchild为根结点指针的二叉树中查找数据元素x;递归在bt->rchild为根结点指针的二叉树中查找数据元素x。(2)算法下一页返回上一页6.5

二叉树的应用下一页返回上一页6.5

二叉树的应用6.5.2标识符树与表达将算术表达式用二叉树来表示，称为标识符树，一也称为二叉表示树。1.标识符树的特点(1)运算对象(标识符)都是叶结点;(2)运算符都是根结点。2.从表达式产生标识符树的方法(1)读入表达式的一部分产生相应二叉树后，再读入运算符时，运算符与二叉树根结点的运算符比较优先级的高低。①读入优先级高于根结点的优先级，则读入的运算符作为根的右子树，原来二叉树的右子树，成为读入运算符的左子树;下一页返回上一页6.5

二叉树的应用②读入优先级不高(等于或低于根结点的优先级)，则读入运算符作为树根，而原来二叉树作为它的左子树;(2)遇到括号，先使括号内的表达式产生一棵二叉树，再把它的根结点连到前面已产生的二叉树根结点的右子树上去;(3)单目运算符+、-，加运算对象(表示0)。3.应用举例[例6-7]画出表达式:A*B*C的标识符树，并求它的前序序列和后序序列。前序序列:**ABC后序序列:AB*C*。如图6-26所示。[例6-8]画出表达式:A*(B*C)的标识符树，并求它的前序序列和后序序列。前序序列:*A*BC;后序序列:ABC**。如图6-27所示。下一页返回上一页6.5

二叉树的应用[例6-9]画出表达式:-A+B-C+D的标识符树，并求它的前序序列和后序序列。前序序列:+-+-ABCD;后序序列:A-B+C-D+。如图6-28所示。[例6-10]画出(A+(B-C))/((D+E)*(F+G-H))的标识符树，并求它的前序序列和后序序列。前序序列:/+A-BC*+DE-+FGH;后序序列:ABC-+DE+FG+H-*/。返回上一页6.6

哈夫曼树及其应用哈夫曼(Hafftnan)树，是一种带权路径长度最小的二叉树，也称最优二叉树。6.6.1哈夫曼树的引入1.几个术语(1)路径长度—从树中的一个结点到另一个结点之间的分支构成两个结点间的路径，路径上的分支数日，称作路径长度。(2)树的路径长度—从树根到每个结点的路径长度之和称为树的路径长度。(3)结点的带权路径长度—从该结点到树根之间路径长度与该结点上权的乘积。下一页返回6.6

哈夫曼树及其应用(4)树的带权路径长度—树中所有叶子结点的带权路径长度之和，称为树的带权路径长度。(5)最优二叉树—带权路径长度最小的二叉树，称为最优二叉树。2.如何求树的带权路径长度设二叉树具有n个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度(WPL)，记为下一页返回上一页6.6

哈夫曼树及其应用其中,Wk为第k个叶结点的权值;Lk为第k个叶结点到根结点的路径长度。[例6-11]设给定权值分别为2,3,5,9的四个结点，图6-30构造了5个形状不同的二叉树。请分别计算它们的带权路径长度。五棵树的带权路径长度分别为图6-29(a)WPL=2x2+3x2+5x2+9x2=38图6-29(b)WPL=2x3+3x3+5x2+9x1=34图6-29(c)WPL=2x2+3x3+5x3+9x1=37图6-29(d)WPL=9x3+5x3+3x2+2x1=50图6-29(e)WPL=2x1+3x3+5x3+9x2=44下一页返回上一页6.6

哈夫曼树及其应用五个图的叶结点具有相同权值，由于其构成的二叉树形态不同，则它们的带权路径长度也各不相同。其中以图6-30(b)的带权路径长度最小，它的特点是权值越大的叶结点越靠近根结点，而权值越小的叶结点则远离根结点，事实上它就是一棵最优二叉树。由于构成最优二叉树的方法是由D.Haffman最早提出的，所以又称为哈夫曼树。下一页返回上一页6.6

哈夫曼树及其应用6.6.2哈夫曼树的建立1.哈夫曼树构成的基本思想(1)由给定的n个权值{W1,W2,…，Wn}构造n棵只有一个叶结点的二叉树，从而得到一个二叉树的集合

F={T1，T2，…，Tn};(2)在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和;(3)在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加人到集合F中;(4)重复(2),(3)两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。下一页返回上一页6.6

哈夫曼树及其应用以例6-11的叶结点权值2、3、5、9为例，介绍哈夫曼树的构造过程，如图6-31所示。带权路径长度为：WPL=9*1+5*2+3*3+2*3=34对于同一组给定叶结点权值所构造的哈夫曼树，树的形状可能不同，但其带权路径长度值是相同的，而且必定是最小的。[例6-12]设结点的权集W={10,12,4,7,5,18,2}，建立一棵哈夫曼树，并求出其带权路径长度。如图6-32所示。下一页返回上一页6.6

哈夫曼树及其应用6.6.3哈夫曼编码1.什么是哈夫编码在数据通信中，经常需要将传送的文字转换成由二进制字符n和1组成的二进制代码，称为编码。如果在编码时考虑字符出现的频率，让出现频率高的字符采用尽可能短的编码，出现频率低的字符采用稍长的编码，构造一种不等长编码，则电文的代码就可能更短。哈夫曼编码是一种用于构造使电文的编码总长最短的编码方案。2.求哈夫曼编码的方法(1)构造哈夫曼树下一页返回上一页6.6

哈夫曼树及其应用设需要编码的字符集合为{d1，d2，...，dn}，它们在电文中出现的次数集合为{w1,w2,...,wn}，以d1，d2，...，dn作为叶结点，w1,w2,...,wn作为它们的权值，构造一棵哈夫曼树。[例6-13]设有A,B,C,D,E,F共6个数据项，其出现的频度分别为6,5,4,3,2,1，构造一棵哈夫曼树，并确定它们的哈夫曼编码。(2)在哈夫曼树上求叶结点的编码规定哈夫曼树中