数据结构与算法6

数据结构（数据结构及其算法）

冯耀霖1.

Chap6

树（二）

树与森林

搜索二叉树

哈夫曼树

堆

2.§1树与森林

▲树的存储结构▲树的实现3.1.1树的存储结构

关于树的存储结构有许多种，这里介绍常用的两种。■父结点数组表示法■左孩子右兄弟表示法4.1.

父结点数组表示法

这是一种顺序结构与链结构相结合的树存储方法，它以一组连续的存储单元（数组）来存放树中的结点。每个结点有两个域：data域，存放数据元素；parent域，存放其父结点在数组中的位置序号（下标），相当于父结点的指针，其数值为0（或-1），则表示该结点无父结点，即它是根结点。如图6-1所示树，图6-2所示该树的父结点数组表示法结构。树中结点的存放顺序一般不做特殊要求。如图6-2中使用的是层次方法。5.ABCDEFGIHJdataparentA0B1C1D1E2F3G4H7I7J7下标12345678910

图6.1树

图6.2树的父结点表示法6.2.左孩子右兄弟表示法左孩子右兄弟表示法是目前已知的最节省存储空间的树的链式存储结构方法，它是一种基于递归的定义方式。它的每一个结点由三个域组成：data、leftChild和rightSibling。leftChild域存放的是该结点最左（第一个）孩子的地址，rightSibling域存放的是该结点右兄弟的地址。

leftChilddatarightSibling7.在图6-1中，树的根结点是A，它没有兄弟，所以它的rightSibling值为空。A有三个孩子，分别为B、C和D，因此它的leftChild值是其最左孩子——结点B的地址。B既有孩子又有兄弟，它的rightSibling指向的是右邻兄弟C，而leftChild指向的是其孩子E。结点E是B的唯一孩子且为叶子，所以它的leftChild值和rightSibling值均为空。依照上述规则可以很方便地建立起树形结构的存储模式。理解该表示方法的关键在于理解它的递归本质。为了帮助理解为什么仅通过每个结点的3个域就能实现整棵树的存储，下面给出对以图6-1中树的基于先序的遍历过程。8.→先访问根结点A。A无兄弟有左孩子，所以A不入栈，并访问A的左孩子B；→结点B既有孩子也有兄弟，于是B入栈，并访问它的左孩子E；→结点E是叶子，且无兄弟，所以遍历过程回退到结点B；→访问B的右兄弟C，C既有兄弟又有孩子，所以C入栈，并访问C的左孩子F；→结点F是叶子，且无兄弟，所以遍历过程回退到结点C；→访问C的右兄弟D，D无兄弟但有孩子，所以D不入栈，并访问D的左孩子G；9.→结点G无兄弟有孩子，所以G不入栈，并访问G的左孩子H；→结点H是叶子，但有兄弟，所以H不入栈，并访问H的右兄弟I;→结点I是叶子，但有兄弟，所以I不入栈，并访问I的右兄弟J；→结点J是叶子，也无兄弟，且此时栈为空，至此整个遍历过程结束。

由此可见，尽管左孩子右兄弟表示法的每个结点单元仅有3个域，但它们对构建树形结构的复杂模型已经足够了。10.1.2树的实现

以左孩子右兄弟树为例。

1.树结点template<typenameType>structTreeNode{Typedata;TreeNode*leftChild,*rightSibling;//左孩子右兄弟指针};11.2.树类

template<typenameType>classTree{private:TreeNode<Type>*root,*current;//根指针与当前指针<基本操作的内部成员函数原型声明>public:<基本操作的外部成员函数原型声明>};

12.3.基本操作的算法

SetCurNodeParentElemLeftChildRightSiblingAddNewChildInsertLeftChildInsertSibling13.算法6.1SetCurNode

功能：设置当前结点boolSetCurNode(Typee){//将值为e的结点设置为当前结点returnCurNode(root,e);}

算法6.2CurNode

功能：设置当前结点14.boolCurNode(TreeNode*r,Typee){//在根为r的树中查找值为e的结点，将其设置为当前结点if(r==NULL)returnFALSE;if(r->data==e){current=r;returnTRUE;}if(CurNode(r->leftChild,e)==TRUE)//递归遍历r的左孩子returnTRUE;TreeNode*p=r->rightSibling;while(p!=NULL){//递归遍历r的右兄弟if(CurNode(p,e)==TRUE)returnTRUE;p=r->rightSibling;}returnFALSE;}15.算法6.3ParentElem

功能：查找父结点并读取其元素boolParentElem(Typev,Type&e){//查找v结点的父结点，并读取其元素if(v==root->data)returnFALSE;if(CurNode(root,v)==FALSE)returnFALSE;if(Parent(root,current)==FALSE)returnFALSE;e=current->data;returnTRUE;}16.算法6.4Parent

功能：查找父结点boolParent(TreeNode*r,TreeNode*k){//在根为r的树中查找结点k的父结点，使其成为当前结点if(r==NULL)returnFALSE;TreeNode*cp=r->leftChild,*sp=cp->rightSibling;if(cp==k){current=r;returnTRUE;}if(Parent(cp->leftChild,k)==TRUE)//左孩子递归查找returnTRUE;17.while(sp!=NULL){if(sp==k){current=r;returnTRUE;}

//右兄弟的孩子的递归查找if(Parent(sp->leftChild,k)==TRUE)returnTRUE;sp=sp->rightSibling;}returnFALSE;}18.算法6.5LeftChild

功能：查找左孩子boolLeftChild(){//查找当前结点的左孩子，使其成为当前结点if((current!=NULL&¤t->leftChild!=NULL){current=current->leftChild;returnTRUE;}returnFALSE;}19.算法6.6RightSibling

功能：查找右兄弟boolRightSibling(){//查找当前结点的右兄弟，使其成为当前结点if(current!=NULL&¤t->rightSibling!=NULL){current=current->rightSibling;returnTRUE;}returnFALSE;}20.算法6.7AddNewChild

功能：添加孩子

boolAddNewChild(Typev,Typee){//元素e添加为元素v的结点的孩子if(CurNode(root,v)==FALSE)returnFALSE;

//设置元素为v的结点为当前结点AddChild(current,e);returnTRUE;}21.算法6.8AddChild

功能：添加孩子22.voidAddChild(TreeNode*x,Typee){//为结点x添加元素为e的孩子TreeNode*p=newTreeNode,*t;p->data=e;p->leftChild=p->Sibling=NULL;if(x->leftChild==NULL)x->leftChild=p;else{t=x->leftChild;while(t->rightSibling!=NULL)t=t->rightSibling;t->rightSibling=p;}}23.算法6.9InsertLeftChild

功能：插入左孩子voidInsertLeftChild(TreeNode*x,Typee){//将元素为e的结点插入为结点x的左孩子TreeNode*p=newTreeNode,*t;p->data=e;p->leftChild=NULL;p->Sibling=x->leftChild;x->leftChild=p;}24.算法6.10AddRightSibling

功能：添加右兄弟boolAddRightSibling(Typev,Typee){//元素e添加为元素v的右兄弟TreeNode*p;if(CurNode(root,v)==FALSE)returnFALSE;InsertSibling(current,e);returnTRUE;}25.算法6.11InsertSibling

功能：插入右兄弟voidInsertSibling(TreeNode*x,Typee){//将元素为e的结点插入为结点x的右兄弟TreeNode*p=newTreeNode;p->data=e;p->leftChild=NULL;if(x->rightSibling!=NULL)p->rightSibling=x->rightSibling;x->rightSibling=p;}26.1.3树与森林的遍历

树的遍历方式有两种：深度优先遍历和广度优先遍历。森林的遍历主要采用的是深度优先方式。27.1.树的深度优先遍历可以分为两种具体的形式：先序遍历和后序遍历。先序遍历的规则：如果树非空，则访问其根结点，然后从左到右先序遍历根的每棵子树。后序遍历的规则：如果树非空，则从左到右后序遍历根的每棵子树，然后访问根结点。28.ACBDEFGIHJADCBGFEJIH图6.3树的深度优先遍历

先序遍历ABECFDGHIJ(b)后序遍历EBFCHIJGDA

29.算法6.12PreTreeOrder

功能：树的先序深度优先遍历

voidPreTreeOrder(TreeNode<Type>*r,void(*Visit)(Type&))//private{if(r!=NULL){Visit(r->data);TreeNode*p=r->leftChild;PreTreeOrder(p,Visit);//递归遍历左孩子while(p->rightSibling!=NULL){//递归遍历右兄弟PreTreeOrder(p->rightSibling,Visit);p=p->rightSibling;}}}30.2.广度优先遍历遵循的是分层访问原则。首先访问树中深度为0的那一层中的结点，然后访问深度为1的那一层中的结点，……，在访问每一层结点的时候，遵循的原则是从左向右，直到树中所有的结点都被访问过。31.3.森林的遍历主要采用的是深度优先方式，同样可分为先序遍历和后序遍历两种。森林的先序遍历规则是：当森林非空时，按从左向右原则访问森林的第一棵树（最左树）的根结点，然后先序遍历第一棵树的子森林，再以先序次序遍历其他树组成的森林。如果森林为空，则执行空操作。32.ABCDEFGIHJ图6.4森林的先序遍历

33.1.4森林与二叉树的转换二叉树是一种结构最简单、运算最简便的树形结构。但对许多问题来讲，其自然的描述形态是树或森林。因此，研究树、森林和二叉树之间的关系是有意义的。树的左孩子右兄弟表示法就是将一棵树表示成二叉树的形态，这样就可以将二叉树中的许多方法应用在树的处理中。反之，将一棵二叉树的左孩子看成是树的第一个孩子，右孩子看成是树的第一个孩子的兄弟，可以将一棵二叉树还原成一棵普通的树。34.1.树转化为二叉树

从左孩子右兄弟表示法可知，树中每个结点最多只有一个最左的孩子和一个右邻的兄弟，这就是两者转化操作实现的原理所在。将一棵树转化为二叉树的方法如下：(1)树中所有兄弟之间加一条连线；(2)对树中的每个结点，只保留它与第一个孩子之间的连线，删去它与其他孩子结点之间的连线；(3)以树的根结点为轴心，将整棵树顺时针转动一定的角度（使每个弟弟都变成其哥哥的右孩子），以使其结构层次分明。35.ABCEDFGHIACBEDFGHIABCDEGGFHI图6.5树与二叉树的转换36.2.森林转化为二叉树森林是若干棵树的集合，只要将森林中各棵树的根视为兄弟，每棵树又可以用二叉树表示（左孩子右兄弟），这样森林也可以用二叉树表示。将森林转化为二叉树的方法如下：(1)将森林中的每棵树转化成相应的二叉树；(2)第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树。37.ACBDEFGHIJABCDEFGHIJ图6.6(a)森林与二叉树的转换38.ABCDEFGHIJ图6.6(b)森林与二叉树的转换39.

§2哈夫曼树

▲哈夫曼树的应用▲哈夫曼树的基本概念▲哈夫曼树的构造算法▲哈夫曼编码▲哈夫曼树的实现40.2.1哈夫曼树的应用

在数据膨胀、信息爆炸的今天，数据压缩的意义不言而喻。谈到数据压缩，就不能不提到哈夫曼／霍夫曼（Huffman）编码。哈夫曼编码是一种有关数据压缩的算法，它也是首个实用的压缩编码方案，该算法由哈夫曼（D.A.Huffman）于1952年提出。当时，哈夫曼就读于麻省理工学院，为了向老师证明自己可以不参加某门功课的期末考试，他设计了这个看似简单却影响深远的编码方法。哈夫曼编码效率高，运算速度快，实现方式灵活。从20世纪60年代开始，哈夫曼编码在数据压缩领域得到了广泛应用。而20世纪80年代初，哈夫曼编码又出现在CP/M和DOS系统中，即使在当今的许多知名的压缩工具和压缩算法里，依然可以见到哈夫曼编码的影子。41.文本处理是计算机的重要应用之一。文本由字符组成。在计算机中每个字符用一个由0，1组成的二进制串表示，称之为编码。大多数计算机采用ASCII编码。ASCII编码是一种等长的编码，每个字符的编码长度是相同的。为了提高文本存储和处理的效率，在某些场合希望采用不等长的编码，让使用频率较高的字符有较短的编码，而使用频率较低的字符有较长的编码，总体来讲，保存文本的空间总量会减少，传送文本的速度也会提高。42.例如给出一段文本：ABCDEACBDBDBDBCB在该文本中出现的字符集合为｛A,B,C,D,E｝，其中B出现的次数最多，为6次；其它依次为D＝4次，C=3次，A=2次，E=1次。首先采用定长编码方法。要给5个字符进行编码，最少需要三位二进制码。可以给每个字符赋一个等长的三位二进制的编码为A:000B:001C:010D:011E:100，将原始文本进行编码后所得结果如下：000001010011100000010001011001011001011001010001编码长度为57(bit)43.另一种方案是采用非等长编码，将出现频率最高的B用最少的编码来表示，D用次少的编码来表示，依次类推。如上述5个字符的二进制编码为B:0D:10C:110A:1110E:1111，将原始文本进行编码后所得结果如下：11100110101111111011001001001001100编码长度为41(bit)显然，采用非等长编码可以减少文本占用的存储空间。但怎样找出这种优化的编码呢？44.哈夫曼提出可用一种特定的二叉树来生成优化编码，这种二叉树被称为哈夫曼树，也称最优二叉树，由哈夫曼树生成的编码称为哈夫曼编码。哈夫曼编码不仅可应用于文本编码，也同样可应用于图象编码等领域中。45.2.2哈夫曼树的基本概念■路径：从树的一个结点到另一个结点的分支（边）构成这两个结点之间的路径。对于哈夫曼树特指从根结点到某结点的路径。■路径长度：路径上的分支数目（边数）。树的路径长度：从树根到每一结点的路径长度之和。■权：赋予某个事物的一个量，是对事物的某个（些）属性的数值化描述。在数据结构中，包括结点权和边权两类，它们的具体意义由具体情况决定。■结点的带权路径长度：结点的路径长度与结点上权的乘积。46.■树的带权路径长度：树中所有叶子结点的带权路径长度（weightedpathlength）之和。记做WPL＝∑wili其中，wi是第i个叶子的权值，li是第i个叶子的路径长度（i=1,2,…,n）。■哈夫曼树：设有结点集合K={k1,k2,…,kn}，并以k1,k2,…,kn为叶子结点构造二叉树，如果它们的权值分别为w1,w2,…,wn，那么称使得该二叉树的WPL值最小的二叉树为哈夫曼树（最优二叉树）。47.例如，有4个权值分别为1、6、8、9的结点A、B、C、D，可以构造出以它们为叶子结点的多个二叉树，如图6.7。对于这三棵二叉树，它们的带权路径长度如下：(a)WPL=9×2＋8×2＋1×2＋6×2＝48(b)WPL=9×3＋8×3＋1×1＋6×2＝64(c)WPL=9×1＋8×2＋1×3＋6×3＝46

可见二叉树(c)的WPL值最小，这正是一棵哈夫曼树。48.918616896981ABCDDACBBACD图6.7具有不同带权路径长度的二叉树(a)WPL=48(b)WPL=64(c)WPL=4649.由此可见，由相同权值的一组叶子接点所构成的二叉树有不同的形态和不同的带权路径长度WPL。那么，如何找到WPL最小的二叉树（哈夫曼树）呢？根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶子接点越靠近根接点，而权值越小的叶子结点越远离根结点。50.2.3哈夫曼树的构造算法算法可描述如下：(1)根据给定的n个权值w1,w2,…,wn，构造由n棵二叉树构成的森林F={T1,T2,…,Tn}，其中每棵二叉树Ti

都是只含有一个带权值为wi的根结点。(2)从森林f中选取两棵权值最小的二叉树Ti

和Tj，分别作为左右子树构造一棵新的二叉树，并置新二叉树的根结点r的权值为wr=wi+wj

。(3)从森林F中删去Ti和Tj

，而把新二叉树r加入到F中。(4)重复步骤2和步骤3，直到F中只含一棵二叉树为止。这棵二叉树便是所要建立的哈夫曼树。51.9816987169158716249158716图6.8哈夫曼树的构造过程

52.2.4哈夫曼编码

哈夫曼树是哈夫曼编码的基础，利用哈夫曼树可以构造哈夫曼编码。哈夫曼编码的基本原理是：对频繁使用的字符用较短的代码代替，而对较少使用的字符用较长的代码代替，这样就可以使文件中的编码数减少到最小。因此，哈夫曼编码是一种非等长的并使文件的编码总长为最短的编码方案。53.利用构建哈夫曼树的方法可以得到文件的哈夫曼编码。下面给出哈夫曼编码算法的基本思路：(1)对需要编码的文件统计出它的字符集{C1,C2,…,Cn}，并统计出各个字符在文件中出现的次数或频率，如为｛w1,w2,…,wn｝。(2)以C1,C2,…,Cn作为叶子结点，w1,w2,…,wn作为结点的权值，构造一棵哈夫曼树。(3)规定哈夫曼树中的左分支代表0，右分支代表1，则从根结点到每个叶子结点所经过的路径分支组成的0和1的序列便为该叶子结点所对应字符的哈夫曼编码。54.例如，某文本的字符集及各自的频率为：A(1),B(9),C(6),D(8)，将它们构造成一棵哈夫曼树，于是便可得到A、B、C、D的哈夫曼编码，如图6.9所示。55.8169249158716图6.9哈夫曼编码的生成过程

BDAC100011哈夫曼编码

A:110B:0C:111D:1056.

在构建编码的二叉树时必须将字符结点作为叶子结点，否则会产生具有二义性的编码。例如，有人为字符集合A(1),B(9),C(6),D(8)建立了如下图所示的一棵二叉树，从而得到的编码是A:01B:010C:001D:10198657.在该方案中，字符A的编码01是字符B的编码010的前缀部分，这样对于代码串0101001，既是AAC的代码，也是ABD和BDA的代码，因此，这样的编码不能保证译码的唯一性，被称之为具有二义性的编码。然而，采用哈夫曼编码则不会产生二义性问题。因为，在哈夫曼树中每个字符结点都是叶子结点，它们不可能在根结点到其他字符结点的路径上，所以一个字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀，从而保证了译码的非二义性。58.2.5哈夫曼树类的实现

1.基本思路为了找出一组符号（字符、图象符号等）的哈夫曼编码，可以定义一个哈夫曼树类。哈夫曼树类的对象可以接受一组符号以及对应的权值，并返回每个符号的哈夫曼编码。因此，哈夫曼树类应该提供两个public操作：MakeHfmTree和GetHfmCode。MakeHfmTree操作接受一组待编码的符号以及相应的权值，构造一棵哈夫曼树。GetHfmCode操作根据生成的哈夫曼树为每个叶子结点生成并返回哈夫曼编码。59.实现哈夫曼树类的两个重要问题是：■如何设计哈夫曼树结点?■如何构造并保存哈夫曼树?

下面给出解决上述问题的一种方案。(1)哈夫曼树结点可包括：符号值、符号的权值、左孩子指针、右孩子指针及父结点指针。60.(2)在哈夫曼树中，每个待编码的符号对应的是一个叶子结点，其他结点都是度为2的结点。只要给定了待编码的符号个数n，由n0=n2+1可知哈夫曼树的规模为2n-1。鉴于这些特性，可以考虑用一个长度为2n-1的结点数组forest来构造哈夫曼树。初始时，叶子结点依次存放在forest中的n到2n-1的数组元素中，它们的parent值均为0，表示所有的树都只有根结点。第一次归并在n到2n-1的数组元素中查找权值最小和次小的树，归并后的树的根结点存放在数组元素forest[n-1]中，并设置父子关系。第二次归并后的树的根结点存放在数组元素forest[n-2]中……。最后一次归并的结果存放在数组元素forest[1]中。至此，在forest中便生成了一棵哈夫曼树，数组元素forest[1]是该哈夫曼树的根结点。61.2.哈夫曼树类的定义

template<typenameType>structHfmNode{//哈夫曼树结点的类型Typedata;//符号值intweight;//符号的权值intparent,leftChild,rightChild;//父及左右孩子的下标值};template<typenameType>structHfmCode{//哈夫曼编码的类型Typedata;//待编码的符号stringcode;//对应的哈夫曼编码};62.template<typenameType>classHfmTree{//哈夫曼树类private:HfmNode*forest;//哈夫曼树结点数组，用于构造并保存哈夫曼树intsize;//待编码的符号个数（叶子结点个数）HfmCode*hfm_code;//哈夫曼编码数组intMinTree(intpos);//查找森林中的最小树public:HfmTree(intn){//n为待编码的符号个数size=n;forest=newHfmNode<Type>[size*2-1];//为森林分配空间hfm_code=newHfmCode<Type>[size];//为编码数组分配空间}~HfmTree(){delete[]forest;}voidMakeHfmTree(Type*datas,int*w);//构造哈夫曼树voidGetHfmCode(stringcode[]);//生成并返回哈夫曼编码}63.3.构造哈夫曼树的算法实现voidMakeHfmTree(Type*datas,int*w){//datas为待编码的符号数组，w为权值数组intx,y;//最小树、次最小树的下标intk=size*2-1;//初始化森林for(inti=size;i<=k;i++){forest[i].weight=w[i-size+1];forest