数据结构A第5章(南邮)

第5章树引言树形结构是元素之间具有分层关系的结构，它类似于自然界中的树，应用广泛，是一类很重要的非线性数据结构。在计算机应用中，常出现嵌套的数据，树结构提供了对该类数据的自然表示；利用树结构，可以有效地解决一些算法问题。由于结构特征，树形结构常采用递归方式定义。被称为递归数据结构。有关树的许多算法是递归的。数据结构DATASTRUCTURE南京邮电大学计算机学院内容提要1、树的基本概念；给出树的定义，关于树中的一些术语；2、二叉树的定义、性质及其规范；3、二叉树的遍历等算法的实现；4、树和森林的表示、存储和遍历；5、二叉树的应用实例——哈夫曼树和哈夫曼编码。南京邮电大学计算机学院层次结构的数据在现实自然界中大量存在。国家、省、市、县和区。书的章节、回目。上级和下级。整体和部分。祖先和后裔。5.1树的基本概念5.1.1树的定义课堂提要第5章树5.1树的基本概念5.2二叉树5.3二叉树的遍历5.5树和森林5.7哈夫曼树和哈夫曼编码南京邮电大学计算机学院图5-1西欧语言谱系图原始印欧语古意大利语日耳曼语西日耳曼语拉丁语西班牙语法语意大利语希腊语北日耳曼语冰岛语瑞典语挪威语英语荷兰语德语古希腊语南京邮电大学计算机学院树形结构操作系统的目录结构南京邮电大学计算机学院1.树的定义定义5.1有根数或树的定义

树是包括n（n1）个元素的有限非空集合D，R是D中元素的序偶的集合，R满足以下特性：（1）有且仅有一个结点r∈D，不存在任何结点v∈D，v≠r，使得<v,r>∈R，称r为树的根。（2）除根r以外的所有结点u∈D，都有且仅有一个结点v∈D，v≠u，使得<v,u>∈R。这样定义的树也称有根树，简称树。树不为空集合，树中至少有一个根结点，根结点没有前驱，其余结点都有唯一的前驱结点。因此树形成层次结构。南京邮电大学计算机学院2.树的递归定义定义5.2

树是包括n个结点的有限非空集合T，其中一个特定的结点r称为根，其余结点（T-{r}）划分成m（m≥0）个互不相交的子集T1，T2，...Tm，其中，每个子集都是树，被称为树根r的子树。定义5.2是递归的，用子树来定义树，也就是说，在树的定义中引用了树概念本身，所以，树被称为递归数据结构。EAFGBCDLJMN南京邮电大学计算机学院结点(node)：树中的元素。

E、A、F、B、G、C、D、L、J、M、N均为结点。5.1.2基本术语EAFGBCDLJMN路径(path)：从某个结点沿树中的边可到达另一个结点，则称这两个结点之间存在一条路径。E和N之间存在一条路径。根结点和它的子树根（如果存在）之间形成一条边。路径(path)：从某个结点沿树中的边可到达另一个结点，则称这两个结点之间存在一条路径。E和N之间存在一条路径。EAFGBCDLJMN路径(path)：从某个结点沿树中的边可到达另一个结点，则称这两个结点之间存在一条路径。E和N之间存在一条路径。南京邮电大学计算机学院双亲(parent)：若一个结点有子树，那么该结点称为子树根的双亲。A、F、B的双亲是E。C、D的双亲是F。孩子(child)：某结点子树的根是该结点的孩子。E有三个孩子：A、F、B。D有一个孩子：J。兄弟(sibling)：有相同双亲的结点互为兄弟。A、F、B互为兄弟，C和D互为兄弟。结点G和C互为兄弟否？EAFGBCDLJMN南京邮电大学计算机学院后裔(decendent)：一个结点的所有子树上的任何结点都是该结点的后裔。结点C的后裔为：L、M、N。EAFGBCDLJMN祖先(ancestor)：从根结点到某个结点的路径上的所有结点都是该结点的祖先。结点L的祖先为：E、F、C。南京邮电大学计算机学院结点的度(degree)：结点拥有的子树数。结点E的度为3，结点F的度为2，结点A的度为1，结点G的度为0。叶子(leaf)：度为零的结点。B、G、J、M、N均为叶子结点。EAFGBCDLJMN分支结点(branch)：度不为零的结点。E、A、F、C等为分支结点。树的度：树中结点的最大的度。该树的度为3。南京邮电大学计算机学院结点的层次：根结点的层次为1，其余结点的层次等于其双亲结点的层次加1。结点E的层次为1。结点M的层次为5。树的高度：树中结点的最大层次。∵树中结点的最大层次为5。∴树的高度为5。12345EAFGBCDLJMN南京邮电大学计算机学院AG无序树：如果树中结点的各子树之间的次序是不重要的，可以交换位置。下列是同一棵无序树：将左边树中所有结点的子树互换次序就是右边的树。EAFGBCDLJMNEFBCDLJNM南京邮电大学计算机学院有序树：如果树中结点的各棵子树看成是从左到右有次序的，则称该树为有序树。有序树的各子树从左到右为第一棵子树、第二棵，…如果下列是有序树，则二者是二棵不同的树AGEAFGBCDLJMNEFBCDLJNM南京邮电大学计算机学院森林：是树的集合。0个或多个不相交的树组成森林。果园或有序森林：有序树的有序集合。森林与树只有很小的差别，若将树中的根去掉，则得到根的子树组成的森林。BEAGFCDLJMNE若增加一个结点，将森林中各树的根作为新增结点的孩子，则森林即成为树。南京邮电大学计算机学院递归1.递归的定义函数直接（间接）调用自已，称为函数的递归调用。2.简单实例以下是一个最简单的递归函数。voidfunc(){func();}

修改为：voidfunc(intn){if(n<=0)return;func(n--);}南京邮电大学计算机学院3.递推关系可以把要解决的问题转化为一个新问题，而这个新的问题的解决方法仍与原来的解决方法相同，只是所处理对象的规模有规律地递增或递减，即要找到对象之间的递推关系。

方法相同，规模变化4.递归的结束条件要有一个明确的结束递归的条件，一定要能够在适当的地方结束递归调用，不然可能导致系统崩溃南京邮电大学计算机学院intfunc(intn){if(n==1)return1;returnfunc(n-1)*n;}例如：采用递归计算N！正整数N！＝N*(N-1)*(N-2)*…*2*1，

阶乘序列可转换为N！＝N*(N-1)!，而(N-1)!以可转换为(N-1)!=(N-1)*(N-2)!(N-2)!=(N-2)*(N-3)!，……2!=2*1!1!=1递推关系：N！＝N*(N-1)!结束条件：N等于1南京邮电大学计算机学院intfunc(intn){if(n==1)return1;returnfunc(n-1)*n;}n=3{if(n==1)…….func(n-1)*n}n=2{if(n==1)…….func(n-1)*n}n=1{if(n==1)return1}1func(n-1)func(n-1)n=2n=12执行过程：南京邮电大学计算机学院设计递归算法，求有n个元素的整数数组A中的最大值。

a0a1…ai…

an-2an-101…i…n-2n-1a(n-1)Max(n)Max(n-1)

a0a1…ai…

an-3an-2an-101…i…n-2n-1a(n-2)Max(n-1)Max(n-2)南京邮电大学计算机学院设计递归算法，求整数数组A[n]中的最大值。

a0a1…ai…

an-3an-2an-101…i…n-2n-1a(1)Max(2)Max(1)递推关系：max(n)等于max(n-1)与a[n-1]之间的大者结束条件：n等于1时，Max(1)的值即为a0，所以不再向下递推南京邮电大学计算机学院intMax(inta[],intn){inttemp;if(n==1)returna[0];else{temp=Max(a,n-1);if(temp<a[n-1])returna[n-1];elsereturntemp;}}递推关系：max(n)等于max(n-1)与a[n-1]之间的大者结束条件：n等于1时，Max(1)的值即为a0，所以不再向下递推南京邮电大学计算机学院intMax(inta[],intn){inttemp;if(n==1)returna[0];else{temp=Max(a,n-1);if(temp<a[n-1])returna[n-1];elsereturntemp;}}

8

9

10012n=3{if(n==1)…….Max(a,2)<a[2]}n=2{if(n==1)…….Max(a,1)<a[1]}n=1{if(n==1)returna[0]}89南京邮电大学计算机学院二叉树是非常重要的树形数据结构。很多从实际问题中抽象出来的数据是二叉树形的；以后我们将看到任意树或森林可方便地转换成二叉树，从而为一般树和森林的存储和处理提供了有效方法。5.2二叉树课堂提要第5章树5.1树的基本概念5.2二叉树5.3二叉树的遍历5.5树和森林5.7哈夫曼树和哈夫曼编码南京邮电大学计算机学院方法二：改进结构，组织成树形结构。比较次数不会超过树高，提高了效率。先看一个二叉树应用例子。设有序表为（21，25，28，33，36，45），现在要在表中查找元素33。282136253345方法一：顺序搜索。效率低，平均比较一半的元素。（21，25，28，33，36，45）比较了4次！比较了3次！3333南京邮电大学计算机学院定义5.3

二叉树(binarytree)是结点的有限集合，该集合或者为空集，或者是由一个根和两个互不相交的、称为该根的左子树和右子树的二叉树组成。上述定义表明二叉树可以为空集，因此，二叉树有5种基本形态。5.2.1二叉树的定义(a)(b)(c)(d)(e)图5-4二叉树的五种基本形态南京邮电大学计算机学院树与二叉树的区别：⑴树不能是空树，即至少有一个根结点。而二叉树可以是空树。⑵一般树的子树之间是无序的。而二叉树中结点的子树要区分左、右子树，即使只有一棵子树。⑶树中每个节点可有0棵或若干子树。而二叉树的每个节点最多只能有2棵子树。EFEF南京邮电大学计算机学院性质5.1二叉树的第i(i1)层上至多有2i-1个结点。可用归纳法证明之。当i=1时，二叉树至多只有一个结点，结论成立。设当i=k时结论成立，即二叉树上至多有2k-1个结点，当i=k+1时，∵每个结点最多只有两个孩子，∴第k+1层上至多有2*2k–1=2k个结点，性质成立。5.2.2二叉树的性质南京邮电大学计算机学院性质1、2的图形解释性质5.1二叉树的第i(i1)层上至多有2i-1个结点。南京邮电大学计算机学院性质5.2高度为h的二叉树上至多有2h–1个结点。当h=0时，二叉树为空二叉树。当h>0时，利用性质1，高度为h的二叉树中结点的总数最多为：南京邮电大学计算机学院性质1、2的图形解释南京邮电大学计算机学院性质5.3包含n个元素的二叉树的高度至少为

log2

(n+1)

根据性质2，高度为h的二叉树最多有2h–1个结点（性质2），因而n2h–1,则有hlog2(n+1)。由于h是整数，所以h

log2

(n+1)。南京邮电大学计算机学院性质5.4任意一棵二叉树中，若叶结点的个数为n0，度为2的结点的个数为n2，则必有n0=n2+1。设二叉树的度为1的结点数为n1，树中结点总数为n，则n=n0+n1+n2……①（∵二叉树中只有度为0、1、2三种类型的结点）设分支数为B，n个结点的二叉树，除了根结点外，每个结点都有一个分支进入，则B=n-1；分支是由度为1或者度为2的射出的，又有B=2n2+n1；则有：n-1=2n2+n1n=2n2+n1+1……②由①②可得到：n0+n1+n2=2n2+n1+1n0+n2=2n2+1 即n2=n0-1。南京邮电大学计算机学院定义5.4高度为h的二叉树恰好有2h–1个结点时称为满二叉树。01234567891011121314(a)满二叉树图5.6几种特殊的二叉树性质5.2高度为h的二叉树上至多有2h–1个结点。南京邮电大学计算机学院0123456789(b)完全二叉树图5.6几种特殊的二叉树9定义5.5一棵二叉树中，只有最下面两层结点的度可以小于2，并且最下一层的叶结点集中在靠左的若干位置上。这样的二叉树称为完全二叉树。南京邮电大学计算机学院定义5.6扩充二叉树也称2-树，其中除叶子结点外，其余结点都必须有两个孩子。532330111213173589南京邮电大学计算机学院完全二叉树的性质性质5.5具有n个结点的完全二叉树的高度为log2

(n+1)。证明：根据性质2高度为h-1的完全二叉树结点个数最多为2h-1-1高度为h的完全二叉树结点个数最多为2h-1高度为h的完全二叉树结点个数取值范围[2h-1,2h)2h-1-1＜n≤2h–1log2(n+1)≤h＜log2(n+1)+1h=log2

(n+1)结论：⑴n个结点的二叉树中完全二叉树最矮，高度为log2(n+1)。⑵n个结点的完全二叉树和二叉判定树的高度是一样的2h-1≤n＜2hh-1≤log2n＜h∵h是整数∴h=①①②②性质2高度为h的二叉树上至多有2h–1个结点。南京邮电大学计算机学院性质5.6假定对一棵有n个结点的完全二叉树中的结点，按从上到下、从左到右的顺序，从0到n-1编号（见图5.6(c)），设树中一个结点的序号为i，0i＜n，则有以下关系成立：（1）当i=0时，该结点为二叉树的根。（2）若i>0，则该结点的双亲的序号为(i-1)/2（3）若2i+1＜n，则该结点的左孩子的序号为2i+1，否则该结点无左孩子。（4）若2i+2＜n，则该结点的右孩子的序号为2i+2，否则该结点无右孩子。0123456789(b)完全二叉树南京邮电大学计算机学院ADTBinaryTree{Data:二叉树是结点的有限集合，该集合或者为空集，或者是由一个根和两个互不相交的称为该根的左子树和右子树的二叉树组成。

Operations:Create()：创建一棵空二叉树。Destroy():撤销一棵二叉树。IsEmpty()：若二叉树空，则返回true，否则返回false。Clear():移去所有结点，成为空二叉树。Root(x)：取x为根结点；若操作成功，则返回true，否则返回falseMakeTree(x,left，right)：创建一棵二叉树，x为根结点，left为左子树，right为右子树。BreakTree(x,left,right)：拆分二叉树为三部分，x为根的值，left和right分别为原树的左右子树PreOrder：使用函数Visit访问结点，先序遍历二叉树。InOrder：使用函数Visit访问结点，中序遍历二叉树。PostOrder：使用函数Visit访问结点，后序遍历二叉树。}

5.2.3二叉树ADT南京邮电大学计算机学院1.完全二叉树的顺序表示完全二叉树中的结点可以按层次顺序存储在一片连续的存储单元中。根结点保存在编号为0的位置上。注意：一般的二叉树不适合用这种存储结构。01234567890123456789图6.5图6.4(b)完全二叉树的顺序表示0123456789图6.4(b)完全二叉树5.2.4二叉树的存储表示南京邮电大学计算机学院element2.二叉树的链接表示ABCDEFAB^C^D^^E^^F^(a)二叉树 (b)二叉树的链接表示图6-6二叉树的链接表示lChildrChild二叉树的二叉链表结构有利于从双亲到孩子方向的访问。采取从根开始，遍历整个二叉树。root南京邮电大学计算机学院如果应用程序需要经常执行从孩子到双亲访问，可在二叉链表结点中增加一个parent域，令它指向该结点的双亲结点。这就实现了从孩子到双亲，以及从双亲到孩子的双向链接结构，形成多重链表。南京邮电大学计算机学院template<classT>structBTNode//树结点{BTNode(){lChild=rChild=NULL;}BTNode(constT&x){element=x;lChild=rChild=NULL;}BTNode(constT&x,BTNode<T>*l,BTNode<T>*r){element=x;lChild=l;rChild=r;}Telement;BTNode<T>*lChild,*rChild;};5.2.5二叉树类南京邮电大学计算机学院template<classT>classBinaryTree{public:BinaryTree(){root=NULL;}

~BinaryTree(){Clear();}boolIsEmpty()const;voidClear();boolRoot(T&x)const;voidMakeTree(constT&e,BinaryTree<T>&left,BinaryTree<T>&right);voidBreakTree(T&e,BinaryTree<T>&left,BinaryTree<T>&right);voidPreOrder(void(*Visit)(T&x));//公有函数，用户接口voidInOrder(void(*Visit)(T&x));voidPostOrder(void(*Visit)(T&x));

protected:BTNode<T>*

;//指向根结点

private:intSize(BTNode<T>*t);voidClear(BTNode<T>*t);voidPreOrder(void(*Visit)(T&x),BTNode<T>*t);//私有函数，实现遍历voidInOrder(void(*Visit)(T&x),BTNode<T>*t);voidPostOrder(void(*Visit)(T&x),BTNode<T>*t);};程序5.2二叉树类root南京邮电大学计算机学院本小节中，我们主要实现MakeTree、BreakTree和Root运算，而将二叉树遍历算法留待下一小节专门讨论。Clear()函数释放二叉链表中的所有结点，它需要通过遍历二叉树来实现。5.2.6实现二叉树基本运算南京邮电大学计算机学院程序5.3部分二叉树运算template<classT>boolBinaryTree<T>::Root(T&x)const//取根结点的数据值{if(root){x=root->element;returntrue;}elsereturnfalse;}ABCDEFroot南京邮电大学计算机学院template<classT>voidBinaryTree<T>::MakeTree(constT&x, BinaryTree<T>&left,BinaryTree<T>&right){if(root||&left==&right)return;root=newBTNode<T>(x,left.root,right.root);left.root=right.root=NULL;}DCEFBTNode(constT&x,BTNode<T>*l,BTNode<T>*r){element=x;lChild=l;rChild=r;}XleftrightnewBTNode<T>(x,left.root,right.root);函数功能：以x为根，left,right为左右子树构建一棵新二叉树南京邮电大学计算机学院template<classT>voidBinaryTree<T>::BreakTree(T&x, BinaryTree<T>&left,BinaryTree<T>&right){if(!root||&left==&root||left.root||right.root)return;x=root->element;left.root=root->lChild;right.root=root->rChild;deleteroot;root=NULL;}DCEFAleft.root→←right.rootroot=∧root函数功能：将二叉树左右子树拆分成二棵新的二叉树，根结点删除南京邮电大学计算机学院intmain(void){BinaryTree<char>a,b,x,y,z;chare;y.MakeTree('E',a,b);z.MakeTree('F',a,b);x.MakeTree('C',y,z);y.MakeTree('D',a,b);z.MakeTree('B',y,x);z.BreakTree(e,y,x);return0;}程序5.4main函数——一个测试程序abxyzEyCxFzDyBz南京邮电大学计算机学院ABDCEF5.3二叉树的遍历遍历（traverse）一个有限结点的集合，意味着对该集合中的每个结点访问且仅访问一次。二叉树遍历算法:

(I)先左后右：VLR，LVR，LRV(II)先右后左：VRL，RVL，RLV-逆课堂提要第5章树5.1树的基本概念5.2二叉树5.3二叉树的遍历5.5树和森林5.7哈夫曼树和哈夫曼编码南京邮电大学计算机学院⑴先序遍历（VLR）若二叉树为空，则空操作；否则访问根结点；

先序遍历左子树；

先序遍历右子树。ABDCEF5.3.1二叉树遍历算法先序遍历序列：ABDCEF

南京邮电大学计算机学院先序遍历序列：ABDGHECF

t→t→t→t→t→t→t=∧t=∧t=∧t=∧t→t→t=∧t=∧t=∧ABCDEFGH任意一个先序遍历序列中，根结点的位置在哪里？若二叉树为空，则空操作；否则访问根结点；

先序遍历左子树；

先序遍历右子树。南京邮电大学计算机学院⑵中序遍历（LVR）若二叉树为空，则空操作；否则中序遍历左子树；访问根结点；中序遍历右子树。

ABDCEF中序遍历序列：BDAECF

南京邮电大学计算机学院中序遍历ABCDEFGHIJK南京邮电大学计算机学院⑶后序遍历（LRV）若二叉树为空，则空操作；

否则

后序遍历左子树；

后序遍历右子树；

访问根结点。ABDCEF后序遍历序列：DBEFCA

南京邮电大学计算机学院后序遍历ABCDEFGHIJK南京邮电大学计算机学院层次遍历ABCDEFGHIJK南京邮电大学计算机学院对于遍历运算，设计了一个面向用户的公有成员函数和一个具体实现遍历操作的递归私有成员函数，两者共同完成遍历运算的功能。公有成员函数：非递归函数，作为与用户的接口。它调用私有的递归函数。私有成员函数：递归函数，具体实现遍历操作。被公有成员函数调用。5.3.2二叉树遍历的递归算法南京邮电大学计算机学院函数指针格式：函数返回类型(*函数指针名)(参数1，参数2…)#include<iostream.h>intmax(intx,inty){returnx>y?x:y;}intmin(intx,inty){returnx<y?x:y;}intadd(intx,inty){returnx+y;}voidprocess(intx,inty,int(*fun)(int,int)){intresult;result=fun(x,y);cout<<result<<endl;}intmain(void){intx=1,y=2;process(1,2,min);process(1,2,max);process(1,2,add);return0;}程序运行结果：123指向函数的指针保存一个函数的入口地址。函数返回类型(*函数指针名)(参数1,参数2)int(*fun)(int,int)南京邮电大学计算机学院程序5.5访问元素函数template<classT>voidVisit(T&x){cout<<x<<"\t";}程序5.6先序遍历template<classT>voidBinaryTree<T>::PreOrder(void(*Visit)(T&x))//非递归函数，作为与用户的接口，调用递归函数{PreOrder(Visit,root);}template<classT>voidBinaryTree<T>::PreOrder(void(*Visit)(T&x),BTNode<T>*t){if(t)//递归函数，实现遍历{Visit(t->element);PreOrder(Visit,t->lChild);PreOrder(Visit,t->rChild);}}注：1.函数名相同，但参数不同，不是同一个函数。2.使用函数指针(*Visit)(T&x)，只是为了增加程序的灵活性

南京邮电大学计算机学院template<classT>voidBinaryTree<T>::PreOrder(BTNode<T>*t){if(t){cout<<t->element;PreOrder(t->lChild);PreOrder(t->rChild);}}template<classT>voidBinaryTree<T>::PreOrder(void(*Visit)(T&x),BTNode<T>*t){if(t)//递归函数，实现遍历{Visit(t->element);PreOrder(Visit,t->lChild);PreOrder(Visit,t->rChild);}}除去函数指针，以上递归的PreOrder函数可以简化为：南京邮电大学计算机学院CEFt->c{if(t){cout<<c

PreOrder(t->lChild);PreOrder(t->rChild);}}t->E{if(t){cout<<E

PreOrder(t->lChild);PreOrder(t->rChild);}}t->^{if(t){cout…PreOrder(t->lChild);PreOrder(t->rChild);}}t->^{if(t){cout…PreOrder(t->lChild);PreOrder(t->rChild);}}t->F{if(t){cout<<F

PreOrder(t->lChild);PreOrder(t->rChild);}}t->^{if(t){cout…PreOrder(t->lChild);PreOrder(t->rChild);}}南京邮电大学计算机学院补充：中序遍历template<classT>voidBinaryTree<T>::InOrder(void(*Visit)(T&x)){InOrder(Visit,root);}template<classT>voidBinaryTree<T>::InOrder(void(*Visit)(T&x),BTNode<T>*t){if(t){InOrder(Visit,t->lChild);

Visit(t->element);InOrder(Visit,t->rChild);}}南京邮电大学计算机学院补充：后序遍历template<classT>voidBinaryTree<T>::PostOrder(void(*Visit)(T&x)){PostOrder(Visit,root);}template<classT>voidBinaryTree<T>::PostOrder(void(*Visit)(T&x),BTNode<T>*t){if(t){PostOrder(Visit,t->lChild);PostOrder(Visit,t->rChild);

Visit(t->element);}}南京邮电大学计算机学院显然，二叉树遍历算法基本操作是访问结点，不论按何种次序遍历，对含有n个结点的二叉树，其时间复杂度均为O(n)。南京邮电大学计算机学院关于三种遍历算法：1.给定一棵二叉树，能写出它的三种遍历序列。2.给出二叉树的先序遍历序列和中序遍历序列可以唯一确定一棵二叉树。3.给出二叉树的后序遍历序列和中序遍历序列可以唯一确定一棵二叉树。4.当n>1时，给出二叉树的先序遍历序列和后序遍历序列不可以唯一确定一棵二叉树。例如：先序序列：AB，后序序列：BA注意n>1的条件！例如：先序序列：A，后序序列：AAABAB南京邮电大学计算机学院例已知结点的先序序列和中序序列分别为：前序序列ABCDEFG中序序列CBEDAFG则可按上述分解求得整棵二叉树。其构造过程如下图所示。首先由前序序列得知二叉树的根为A，则其左子树的中序序列为（CBED），又右子树的中序序列为（FG）。反过来得知其左子树的前序序列必为（BCDE），右子树的前序序列为（FG）。类似地，可由左子树的前序序列和中序序列构造A的左子树，由右子树的前序序列和中序序列构造得A的右子树。南京邮电大学计算机学院1.计算二叉树的结点数程序5.7求二叉树的结点数template<classT>intBinaryTree<T>::Size(){returnSize(root);}template<classT>intBinaryTree<T>::Size(BTNode<T>*t){if(!t)return0;returnSize(t->lChild)+Size(t->rChild)+1;}利用二叉树遍历思想可以解决许多二叉树的应用问题。ABDCEF5.3.3二叉树遍历的应用实例南京邮电大学计算机学院2.二叉树复制程序5.8二叉树复制template<classT>BTNode<T>*BinaryTree<T>::Copy(BTNode<T>*t){if(!root)returnNULL;BTNode<T>*q=newBTNode<T>(t->element);q->lChild=Copy(t->lChild);q->rChild=Copy(t->rChild);returnq;}ABDCEFtABDCEFq==>南京邮电大学计算机学院3.补充：Clear函数template<classT>voidBinaryTree<T>::Clear(BTNode<T>*t){if(t){Clear(t->lChild);Clear(t->rChild);cout<<"delete"<<t->element<<"..."<<endl;deletet;}}南京邮电大学计算机学院二叉树在很多领域都有着广泛的应用——编译原理中的表达式树专家系统中的决策树猜谜游戏的决策树南京邮电大学计算机学院先序遍历前缀表达式中序遍历中缀表达式后序遍历后缀表达式编译原理中的表达式树编译原理中还用了语法树(d)a*(b+c*d)/e/*+eb*ab*(c)a*(b+c)*aceb(b)a*b+c+*bca(a)a/b/ab南京邮电大学计算机学院5.4二叉树遍历的非递归算法南京邮电大学计算机学院

前两几节中，我们已介绍了树和森林的定义和概念，并对二叉树作了详细介绍，现在再回过头来讨论森林和二叉树的转换、树或森林的存储表示及其遍历算法。5.5树和森林课堂提要第5章树5.1树的基本概念5.2二叉树5.3二叉树的遍历5.5树和森林5.7哈夫曼树和哈夫曼编码南京邮电大学计算机学院为什么要将森林转换为二叉树

如果树和森林能够用二叉树表示，则前面对二叉树的讨论成果可应用于一般树和森林。注意：树和二叉树的区别—二叉树有左右孩子之分，而树没有左右孩子之分。5.5.1森林与二叉树的转换南京邮电大学计算机学院2.森林(Forest)转换成二叉树(BTree)可以将任何森林唯一地表示成一棵二叉树。方法如下：(1)若F为空，则B为空二叉树(2)若F非空，则B的根是F中第一棵子树T1的根R1，B的左子树是R1的子树森林（T11，T12，…，T1m），B的右子树是森林（T2，…，Tn）所对应的二叉树最后所形成的二叉树就是森林所对应的二叉树。南京邮电大学计算机学院1.树(Tree)转换为二叉树(BTree)算法树可以唯一地表示成一棵二叉树：⑴兄弟手拉手----将树中的兄弟用线连接；⑵断绝非长子之间的父子关系----对各结点，保留最左孩子的连线，去掉其余孩子的连线；⑶最后抖一抖----调整为习惯的二叉树形(水平右斜，垂直左斜)。GDEFHJDEHFJG(a)树(b)对应的二叉树5.5.1森林与二叉树的转换南京邮电大学计算机学院DEFGHJABCKDEFGHJABCKGACKGA==>CK==>再看一例⑴兄弟手拉手⑵断绝非长子之间的父子关系⑶最后抖一抖左孩子右兄弟树转换为二叉树南京邮电大学计算机学院注意：⑴左孩子右兄弟。(树→二叉树)

二叉树中有两个结点X和Y，且X是Y的双亲

⑵树的根结点没有兄弟，所以树对应的二叉树根结点没有右子树二叉树中树中Y是X左孩子Y是X孩子Y是X右孩子Y是X兄弟南京邮电大学计算机学院森林转换成二叉树的具体做法：１.将森林中各树的根用线连起来，２.在树中，凡是兄弟用线连起来--兄弟手拉手；３.去掉从双亲到除了第一个孩子以外的孩子的连线，只保留双亲到第一个孩子的连线--断绝非长子之间的父子关系；4.使之稍微倾斜成习惯的二叉树形--最后抖一抖。其实，这里讨论的森林是指有序森林，也可将一般的森林视为有序森林来对待。

5.5.1森林与二叉树的转换南京邮电大学计算机学院ABCFFDEGHJABCFFDEGHJABCFFDEGHJ森林转换为二叉树南京邮电大学计算机学院3.二叉树转换成森林(B→F)左孩子右兄弟ABCKDEFGHJADEHFJGBCK左孩子仍是孩子，右孩子变为兄弟××××南京邮电大学计算机学院一棵二叉树B转换成的森林中有多少棵树？一棵二叉树转化成的森林中所具有的树的数目，等于二叉树从根结点开始沿右链到第一个没有右孩子的结点所经过的结点数目。ABECDFGHIJ经过3个结点，故森林中3棵树南京邮电大学计算机学院ABCDEFGHIJABCDEFGHIJ南京邮电大学计算机学院1.多重链表表示法其中m是树的度。每个结点的指针域个数均为m，故又称为等长的多重链表。优点：处理简单。 缺点：空指针域多，有浪费。设树中有n个结点，总共有n*m个指针域，其中，只有n-1个非空指针域，故空指针域个数为：n*m-(n-1)=n(m-1)+15.5.2树和森林的存储表示elementchild1child2……childm南京邮电大学计算机学院2.孩子兄弟表示法孩子兄弟(左子/右兄弟)表示法实质上就是树所对应的二叉树的二叉链表表示法。其每个结点为：leftChildelementrightSiblingDEFGHJDEFGHJ∧J∧∧G∧F

∧H∧E

D∧南京邮电大学计算机学院3.双亲表示法每个结点有两个域：element和parent。parent域为指向该结点的双亲结点的下标。可以对树中结点按自上而下、自左向右(按层次)的次序顺序存储起来。思考：如何查找结点的双亲和孩子？012345DEFGHJ-100012elementparent顺序存储的双亲表示法DEFGHJ双亲表示法南京邮电大学计算机学院4.三重链表表示法优点：可以很方便地得到节点的双亲和孩子信息。leftChildelementrightSiblingparentDEFGHJ∧J∧∧G

∧F

∧

H

∧

D

∧∧

E南京邮电大学计算机学院5.带右链的先序表示法数据元素有三个数据项，element,lTag,sibling。

1.sibling指向结点的兄弟

2.lTag为0表示有孩子，孩子存于相邻单元lTag为1表示无孩子3.数据元素按对应二叉树的先序遍历的顺序存储结点。南京邮电大学计算机学院南京邮电大学计算机学院

1．按深度方向遍历对森林的深度遍历与二叉树类似，根据树的递归定义，可以有两种遍历次序：先序遍历和中序遍历。森林(F)对应二叉树(B)先序遍历等价于先序遍历中序遍历等价于中序遍历5.5.3树和森林的遍历南京邮电大学计算机学院

对上图（a)的森林的先序遍历的结果是：ABCKDEHFJG它等同于对(b)的二叉树的先序遍历。⑴先序遍历

若森林为空，则遍历结束。否则

a)访问第一棵树的根；

b)按先序遍历第一棵树的根结点的子树组成的森林；

c)按先序遍历其余树组成的森林。南京邮电大学计算机学院⑵中序遍历若森林为空，则遍历结束否则a)按中序遍历第一棵树的根结点的子树组成的森林；b)访问第一棵树的根；c)按中序遍历其余树组成的森林。南京邮电大学计算机学院2．按宽度方向遍历首先访问处于第一层的结点，然后访问处于第二层的结点，再访问第三层，…，等，最后访问最下层的结点。对上图的森林按宽度方向的遍历结果是：ADBCEFGKHJ南京邮电大学计算机学院5.6堆和优先权队列

堆是一种很有用的数据结构，它可以用于高效地实现优先权队列。

优先权队列中的元素，按其优先级的高低而不是按元素进入队列的次序，来确定出队列的次序。南京邮电大学计算机学院5.6.1堆

一个大小为n的堆是一棵包含n个结点的完全二叉树，该树中每个结点的关键字值大于等于其双亲结点的关键字值。完全二叉树的根称为堆顶。它的关键字值是整棵树上最小的。这样定义的堆称为最小堆。也可构建最大堆。012345堆底堆顶南京邮电大学计算机学院最小堆的特点：堆顶元素是整个堆的最小元素南京邮电大学计算机学院（2）最小堆的另一定义当完全二叉树以顺序方式存储时，实际上得到的是结点序列，所以最小堆又可以定义为：堆是n个元素的序列（k0,k1,…,kn-1），当且仅当满足kik2i+1且kik2i+2,(i=0,1,2,…,(n-2)/2)时称为最小堆。例１：判断序列（23，53，34，65，83，74）是最小堆吗

南京邮电大学计算机学院例２：判断序列（23，98，34，65，83，74）是最小堆吗？

98南京邮电大学计算机学院如何将给定的任意序列调整成最小堆？1.将序列写成堆（完全二叉树）的形式2.将堆调整为最小堆。整个调整过程：从下标（n-2）/2处的元素开始，调整（n-2）/2到0的每个元素。在每个元素调整的过程中，要逐个判断每个元素是否满足最小堆的条件，（即当前元素的值要小于等于孩子），若不满足则此元素向下调整，即此元素要与左右孩子中的小者交换，交换后再与它的左右孩子中的小者比较，若不满足条件则再交换，直到不再需要调整。南京邮电大学计算机学院例１：一个元素92向下调整的过程南京邮电大学计算机学院例2:将序列(36,91,24,12,47,30,52,85）调整为最小堆

2６４３１０７５从（n-2）/2处的元素开始，调整（n-2）/2到0的每个元素。南京邮电大学计算机学院1南京邮电大学计算机学院０南京邮电大学计算机学院template<classT>voidAdjustDown(Theap[],intr,intj){//对下标为r的元素调整，使其满足最小堆的条件intchild=2*r+1;//child是r的左孩子Ttemp=heap[r];while(child<=j){if((child<j)&&(heap[child]>heap[child+1]))child++;//child指向左右孩子中的小者if(temp<=heap[child])break;heap[(child-1)/2]=heap[child];child=2*child+1;}heap[(child-1)/2]=temp;}程序中包含temp<=heap[child]的元素比较要求元素类型Ｔ已实现从元素类型Ｔ到可比较类型关键字的转换，重载类型转换符可实现这种转换child//孩子上移到双亲的位置childr南京邮电大学计算机学院template<classT>voidAdjustDown(Theap[],intr,intj){//对下标为r的元素调整，使其满足最小堆的条件intchild=2*r+1;//child是r的左孩子Ttemp=heap[r];while(child<=j){if((child<j)&&(heap[child]>heap[child+1]))child++;//child指向左右孩子中的小者if(temp<=heap[child])break;heap[(child-1)/2]=heap[child];child=2*child+1;}heap[(child-1)/2]=temp;}程序中包含temp<=heap[child]的元素比较要求元素类型Ｔ已实现从元素类型Ｔ到可比较类型关键字的转换，重载类型转换符可实现这种转换child//孩子上移到双亲的位置childr南京邮电大学计算机学院template<classT>voidCreateHeap(Theap[],intn){for(inti=(n-2)/2;i>-1;i--)AdjustDown(heap,i,n-1)；}建堆的时间为O(nlog2n)。更深入分析可知，建堆时间复杂度为O(n)。

r0123456789此例从下标（n-2）/2开始调整此函数功能是建立最小堆，它通过从第（n-2）/2位置开始，直到第一个元素，重复调用AdjustDown函数实现之。南京邮电大学计算机学院5.6.2优先权队列ADT

1．优先权队列优先权队列不同于先进先出（FIFO）队列，优先权队列中的元素，按其优先级的高低而不是按元素进入队列的次序，来确定出队列的次序。最小值为最高优先权。优先级的最高的元素放在队首，最先出队。2．堆是实现优先权队列的有效的数据结构。

南京邮电大学计算机学院5.6.2优先权队列ADTADTPrioQueue{数据：n0个元素的最小堆。运算：Create()：建立一个空队列。Destroy()：撤消一个队列。IsEmpty()：若队列空，则返回true；否则返回false。IsFull()：若队列满，则返回true；否则返回falseAppend(x):元素值为x的新元素入队列。

Serve(x):在x中返回具有最高优先权的元素值,并从优先权队列中删除该元素。}

南京邮电大学计算机学院5.6.3优先权队列类template<classT>classPrioQueue{public: PrioQueue(intmSize=20); ~PrioQueue(){delete[]q;}; boolIsEmpty()const{returnn==0;} boolIsFull()const{returnn==maxSize;} voidAppend(constT&x); voidServe(T&x);private: voidAdjustDown(intr,intj); voidAdjustUp(intj);

T*q;

intn,maxSize;};南京邮电大学计算机学院优先权队列的构造函数和析构函数template<classT>PriorityQueue<T>::PriorityQueue(intmQSize){maxSize=mSize;n=0;q=newT[maxSize];}~PriorityQueue(){delete[]q;};南京邮电大学计算机学院

优先权队列中插入一个新元素的算法步骤：

1.首先将新元素插入到优先权队列的最后

2.插入元素后，此队列应保持优先权队列的特点，所以，当新元素不满足条件时，须进行调整，调整过程是由下向上，与双亲结点比较，若双亲结点大则新元素上浮，双亲结点下沉。

注：这一过程中与５.６.１节堆中的AdjustDown相反的比较路径

南京邮电大学计算机学院例１：向优先权队列中插入一个新元素２４南京邮电大学计算机学院AdjustUp函数AdjustUp(intj)设数组中0到j-1，这j个位置上的元素已满足kik2i+1且kik2i+2,(i=0，1,2,…,（n-2）/2)条件，运行AdjustUp(intj)将使得增加一个元素q[j],这0-j个元素也满足堆的特性。南京邮电大学计算机学院AdjustUp函数template<classT>voidPriorityQueue<T>::AdjustUp(intj){//将新元素q[j]向上调整inti=j;Ttemp=q[i];while(i>0&&temp<q[(i-1)/2]){ q[i]=q[(i-1)/2];//双亲下移 i=(i-1)/2;//i上移}q[i]=temp;}iii南京邮电大学计算机学院Append和Serve函数

template<classT>voidPriorityQueue<T>::Append(constT&x)//插入新元素到优先权队列中{if(IsFull()){cerr<<"OverFlow"<<endl;exit(1);}q[n++]=x;AdjustUp(n-1);}0１３５４２南京邮电大学计算机学院从空队列开始，依此向队列中插入元素的过程南京邮电大学计算机学院

设从空队列开始，依此向队列中插入元素：71，74，2，72，54，93，52，28，则每次插入后队列的状态如下表南京邮电大学计算机学院template<classT>voidPriorityQueue<T>::Serve(T&x){if(IsEmpty()){cerr<<"UnderFlow"<<endl;exit(1);}x=q[0];q[0]=q[--n];

AdjustDown(0,n-1);}0１３５４２66５４３２0１7南京邮电大学计算机学院Append和Serve函数的时间

容易分析优先权队列的插入和删除运算的时间复杂度。由于具有n个结点的完全二叉树的高度为

log2

(n+1)，所以AdjustDown和AdjustUp两个算法中，比较和移动元素的次数均不会超过该高度。Append和Serve运算分别用一常数阶调用上述两个运算，所以它们的时间复杂度为O(log2n)。南京邮电大学计算机学院

本节将讨论：

树的路径长度哈夫曼树和哈夫曼算法5.7哈夫曼树和哈夫曼编码课堂提要第5章树5.1树的基本概念5.2二叉树5.3二叉树的遍历5.5树和森林5.7哈夫曼树和哈夫曼编码南京邮电大学计算机学院定义5.7从根到树中任意结点的路径长度是指从根结点到该结点的路径上所包括的边的数目。

5.7.1树的路径长度路径(path)：从某个结点沿树中的边可到达另一个结点，则称这两个结点之间存在一条路径。E和N之间存在一条路径。EAFGBCDLJMNEAFGBCDLJMN南京邮电大学计算机学院定义5.8如果叶子结点是带权的，则叶子结点的加权路径长度是从根到该叶子的路径长度与叶子的权的乘积。树的带权路径长度为树中所有叶子结点的加权路径长度之和，记作其中，m是叶子结点的个数，wk是第k个叶子结点的权，lk是该叶子结点的路径长度。南京邮电大学计算机学院(1)WPL=2*2+1*3+2*3+6*1=19(2)WPL=2*2+6*3+2*3+1*1=29南京邮电大学计算机学院一般地，权越大的叶子离根越近，则二叉树的加权路径长度越小。哈夫曼给出了求具有最小加权路径长度二叉树的算法，称为哈夫曼算法。用哈夫曼算法构造的二叉树称为哈夫曼树。5.7.2哈夫曼树和哈夫曼算法南京邮电大学计算机学院哈夫曼算法可以描述如下：⑴用给定的一组权值{w1,w2,…,wn}生成一个森林F={T1，T2，…，Tn},其中每棵二叉树Ti只有一个权值为wi的根结点，其左、右子树均为空。⑵从F中选择两棵根结点权值最小的树作为新树根的左、右子树，新树根的权值是左、右子树根结点的权值之和。(约定左子树根权值小)⑶从F中删除这两棵树，另将新二叉树加入F中。⑷重复⑵和⑶，直到F中只包含一棵树为止。此树即为哈夫曼树。（重复执行几次？）南京邮电大学计算机学院构造哈夫曼树的过程(约定左小右大)重复执行几次？南京邮电大学计算机学院⑵W={3，5，9，11，12，13}南京邮电大学计算机学院构造哈夫曼树的步骤：

1.准备工作：首先构造n棵哈夫曼树对象，每棵树只有一个权值为w[i]的根结点，且该对象的weight为w[i]，将它们逐一加入优先权队列。２.构建哈夫曼树：从优先权队列中取出两棵根结点值最小和次最小的哈夫曼树x和y。以它们根的权值之和为根的权值，x和y为左、右子树构造一棵新哈夫曼树，并将新树对象进优先权队列。重复执行n-1次，此时，队列中只剩下合并完成的哈夫曼树。３.从队列中取出构造完毕的哈夫曼树，函数返回该哈夫曼树。⑵W={3，5，9，11，12，13}南京邮电大学计算机学院5.7.3

哈夫曼树类template<classT>classHfmTree:publicBinaryTree<T>{public:

operatorT()const{returnweight;}//重载类型转换运算符，为了方便优先权队列中，对象间的比较 TgetW(){returnweight;} voidputW(constT&x){weight=x;}SetNull(){root=NULL;}private:

Tweight;};南京邮电大学计算机学院5.7.4

构造哈夫曼树HfmTree<T>CreateHfmTree(Tw[],intn)设数组w[]中保存n个元素类型为T的权值，函数返回一棵构造成功的哈夫曼树。南京邮电大学计算机学院template<classT>HfmTree<T>CreateHfmTree(Tw[],intn){PrioQueue<HfmTree<T>>pq(n);

//空优先权队列HfmTree<T>x,y,z,zero;//空哈夫曼树for(inti=0;i<n;i++){//初始化z.MakeTree(w[i],x,y);//构造只有一个结点的哈夫曼树对象

z.putW(w[i]);//将W[i]的值写入wight域pq.Append(z);//将哈夫曼树对象加入优先权队列z.SetNull();//将z置空 }for(i=1;i<n;i++){ pq.Serve(x);//取出根结点权值最小的哈夫曼树对象pq.Serve(y);/取出根结点权值次小的哈夫曼树对象

z.MakeTree(x.getW()+y.getW(),x,y); z.putW(x.getW()+y.getW()); pq.Append(z); z.SetNull();}pq.Serve(z);returnz;}

W={3，5，9，11，12，13}南京邮电大学计算机学院1.等长编码

A:00,B:01,C:10,D:11.

电文：ABACABDA.编码：0001001000011100

译码：两位一个字符。ASCII编码是等长编码。2.不等长编码

A:0,B:01,C:10,D:101.

电文：ABACABDA.编码：0010100011010

译码：产生二义性。原因：一个字符的编码是另一个字符编码的前缀。前缀编码：一个字符的编码不是另一个字符编码的前缀。5.7.5哈夫曼编码南京邮电大学计算机学院可以利用哈夫曼树得到前缀编码，即哈夫曼编码。

方法如下：1.用权值构造哈夫曼树2.约定左分支为0，右分支为1。3.哈夫曼编码电文：

ABF编码：1100110110

即左0右1南京邮电大学计算机学院5.8并查集与等价关系

首