《山东大学《数据结构》讲义04树和二叉树》由会员分享，可在线阅读，更多相关《山东大学《数据结构》讲义04树和二叉树（26页珍藏版）》请在金锄头文库上搜索。
1、第四章 树和二叉树内容概述树是一种非线性数据结构。树结构经常用于描述和处理数据元素的层次关系，尤其适用于大规模的信息处理任务，例如建立数据库管理系统时所用的层次模型就是一种树型结构。本章主要以二叉树为例，讲述树结构及其应用，主要内容包括：（1）树的定义、术语及性质；（2）二叉树的定义、性质，二叉树的存储结构及二叉树的遍历等各种操作的算法实现；（3）线索二叉树；（4）树、森林与二叉树的转化；（5）赫夫曼树及其应用。重点与难点重点包括：二叉树的性质及遍历算法，线索二叉树的运算，树、森林与二叉树之间的转换，Huffman树的构造算法及Huffman编码、译码。难点包括：二叉树的遍历算法，尤其是非递归
2、遍历算法，线索二叉树的运算，Huffman编码、译码。思考1树型结构的结构特点2树和二叉树的主要差别表现在哪些方面？3二叉树具有那些重要特性？4二叉树有哪些遍历策略？如何利用算法实现？5已知某二叉树的后序遍历序列和中序遍历序列，如何求解出其前序遍历序列。6已知一棵二叉树的中序序列为cbedahgijf，后序序列为cedbhjigfa，画出该二叉树的先序线索二叉树。7有一份电文中共使用5个字符：a、b、c、d、e，它们的出现频率依次为4、7、5、2、9，试画出对应的赫夫曼树（请按左子树根结点的权小于等于右子树根结点的权的次序构造），并求出每个字符的赫夫曼编码。第一节树树是一种非线性数据结构，这种
3、非线性结构有哪些特点？具有那些特有性质？如何描述树结构？本节从树的定义、抽象类型定义、树的基本概念与相关术语、树的性质、树的表示等方面阐述上述问题。1、树的递归与非递归定义1.树的递归定义树(Tree)是n(n0)个结点的有限集合T，不含有任何结点（元素）的树称为空树，否则它满足如下两个条件：有且仅有一个称为根(Root)的结点；其余所有结点被分成m(m0)个互不相交的集合T1,T2,T3,Tm，其中每个集合又构成一棵树，称其为根结点的子树(SubTree)。树的根结点Root是每棵子树根结点的前驱，每棵子树的根结点是根结点Root的后继。例如，在图4.1中，(a)表示只有一个根结点的树；(b
4、)表示有8个结点的树，其中A是根结点，其余结点分成3个互不相交的子集：T1=B,E,F,G,T2=C,T3=D,H。T1、T2和T3都是根结点A的子树，且本身也是一棵树。如T1的根结点为B，其余结点分为3个互不相交的子集：T11=E,T12=F,T13=G。T11、T12和T13都是T1的根结点B的子树。2.树的非递归定义树是n(n0)个结点的有限集合T，不含有任何结点（元素）的树称为空树，而在任一非空树中定义了一个关系，它满足：（1）T中存在唯一的一个结点，它没有前驱，称为树的根；（2）除根结点外，T中每一个结点都有且仅有一个前驱结点；（3）除根结点外，T中每一个结点a，都存在一个从根结点到
5、a的结点序列a1ak,使得a1为根结点，ak=a，而结点ai+1是ai的后继（1ik-1），这个结点序列称为从根结点到结点a的路径。例如，在图4.1(b)中，A为树的根结点。对于结点G，存在一个结点序列ABG，使得A为根结点，B为A的后继，G为B的后继，这个序列就是从根结点A到结点G的路径。2、树的抽象数据类型2、树的抽象数据类型树的抽象数据类型定义如下：ADTTree数据对象D：D=ai|aiElemSet,i=1,2,n,n0数据关系R：若D为空集，则称为空树。若D仅含一个数据元素，则R为空集，否则RH，H满足关系：(1)T中存在唯一的一个结点，它没有前驱，称为树的根，用root表示，在集
6、合D中用a1表示；(2)若D中元素个数大于1，对于任意的数据元素ajD且j2，存在唯一的数据元素aiD，有H；(3)若D中元素个数大于1，对于任意的数据元素ajD，存在k个(k0)数据元素aiD且ij，有H；(4)对于任意的数据元素ajD且j2，存在DjD，Dj=|ElemSet,k=1,2,m,m0，有唯一的Pj=,，这个集合Pj表示从根结点到结点aj的一条路径。基本操作P：InitTree(&T);操作结果：构造空树T。CreateTree(&T,tree);初始条件：tree给出T的表示形式。操作结果：按tree构造T。TreeEmpty(T);初始条件：树T存在。操作结果：若T为空树，
7、则返回TRUE，否则返回FALSE。TreeDepth(T);初始条件：树T存在。操作结果：返回T的深度。Root(T);初始条件：树T存在。操作结果：返回T的根。Value(T,e);初始条件：树T存在，e是需寻找的结点的值。操作结果：若找到该结点，则函数返回TRUE，否则返回FALSE。Assign(T,e,value);初始条件：树T存在，e是需寻找的结点的值。操作结果：若找到该结点，则结点e赋值为value，函数返回TRUE，否则返回FALSE。Parent(T,e,&P);初始条件：树T存在，e是需寻找的结点的值。操作结果：若树中存在值为e的结点，则函数返回TRUE，否则返回FALS
8、E；若存在该结点，用P返回双亲结点的位置，若结点为根结点，则P返回空。DelTreeNode(&T,P);初始条件：树T存在，P指向该二叉树中的一个结点。操作结果：删除P所指向的结点及其子树。TraverseTree(T,visit();初始条件：树T存在，visit是对结点操作的应用函数。操作结果：按某种次序对T的每个结点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败。ClearTree(&T);初始条件：树T存在。操作结果：将树T清空。DestroyTree(&T);初始条件：树T存在。操作结果：将树T销毁。ADTTree该抽象数据类型中，定义了树的若干基本操作，
9、另外，对树的操作还可有插入结点操作、插入子树操作、旋转树操作等3、树的基本术语3、树的基本术语（树结点、叶子结点、分支结点、度、深度）树的结点树的结点包含一个数据元素及若干指向其子树的分支。结点的度和树的度树中每个结点所拥有的非空子树数称为结点的度（Degree）。树的度是树中所有结点的度的最大值。如在图4.1(b)中，结点A、B的度均为3，结点D的度为1，其余结点的度均为0。因为所有结点的度的最大值为3，故树的度为3。叶子结点和分支结点树中度为0的结点称为叶子结点或终端结点，度大于0的结点称为分支结点或非终端结点。除根结点以外，分支结点也称为内部结点。在分支结点中，每个结点的分支数就是该结点
10、的度数。度为1的结点，其分支数为1，称为单分支结点；度为2的结点，其分支数为2，称为双分支结点，其余类推。如在图4.1(b)中，结点C、E、F、G、H都是叶子结点，A、B、D都是分支结点，其中A和B是多分支结点，D是单分支结点。子结点、双亲结点和兄弟结点树中每个结点的子树的根（即每个结点的后继）称为该结点的孩子、儿子或子女（Child），相应地，该结点称为子结点的双亲（Parent）。具有同一个双亲的孩子之间互称兄弟（Brothers）。双亲在同一层上的结点互称为堂兄弟。以某结点为根的子树中任一结点都称为该结点的子孙，相应地，结点的祖先是从根到该结点的路径上经过的所有分支结点。在一棵树中，根结
11、点没有双亲结点，叶子结点没有子结点，其余结点都既有双亲结点也有子结点。如在图4.1(b)中，结点B的孩子为结点E、F、G，双亲为结点A；而E、F、G互为兄弟，结点B的子孙为结点E、F、G，结点E的祖先为结点A、B。结点的层数和树的深度树既是一种递归结构，也是一种层次结构。结点的层数（Level）从根开始定义起，根结点为第一层，它的子结点为第二层，以此类推。如果某个结点在第k层，则其子树的根位于第k+1层。树中结点的最大层数称为树的深度（Depth）或高度。如在图4.1(b)中，结点A为第一层，B、C、D为第二层，E、F、G、H为第三层，树中结点的最大层数是3，故树的深度为3。有序树和无序树如果
12、树中各结点的子树是按照一定的次序从左向右安排的，则称该树为有序树，否则称之为无序树。在有序树中，最左边的子树的根称为第一个孩子，最右边的子树的根称之为最后一个孩子。任何无序树都可以当作是任一次序的有序树来处理，如一个单位的机构设置可用树来表示，若各层机构是按照一定的次序排列的，则为一棵有序树，否则为无序树。森林（Forest）是m（m0）棵互不相交的树的集合。对于树中每个分支结点来说，其子树的集合就是森林。如在图4.1(b)中，由结点A的子树所构成的森林为T1,T2,T3，由结点B的子树所构成的森林为T11,T12,T13。4、树的性质4、树的性质性质1：树中的结点数等于所有结点的度数加1。根
13、据树的定义，在一个树中，除了根结点以外，其他每个结点都有且只有一个前驱结点，即每个结点与指向它的一个分支一一对应，所以除了根结点以外的结点数等于所有结点的分支数（即度数），因此可得出树中的结点数等于所有结点的度数加1。性质2：度为k的树中第i层上至多有ki-1个结点（i1）。利用数学归纳法可以证明此性质。对于第一层显然是成立的。因为树中的第一层上只有根结点，而i=1时，ki-1=k0=1，同样也得到只有一个结点。假设对于第i-1层（i1）命题成立，即度为k的树中第i-1层上至多有k(i-1)-1=ki-2个结点，则根据树的度的定义，度为k的树中每个结点至多有k个孩子，所以第i层上的最大结点数为
14、第i-1层上的最大结点数的k倍，即ki-2k=ki-1个，故结论成立。性质3：深度为h的k叉树至多有（kh-1）/（k-1）个结点。由性质2可知，当深度为h的k叉树（即度为k的树）上每一层都达到最多结点数时，所有结点的总和为：，故深度为h的k叉树至多有个结点。当一棵k叉树上的结点数等于时，即k叉树的结点数达到了最大值时，则称该树为满k叉树。这种树的特点是每一层上的结点数都是最大结点数。性质4：具有n个结点的k叉树的最小深度为。（其中符号表示对x进行向上取整，如。）假设具有n个结点的k叉树的深度为h，若在该树中前h-1层都是满的，即第i层的结点数等于ki-1个（1ih-1），最后一层即第h层的结
15、点数可能满也可能不满，则该树具有最小的深度。根据性质3有：，即。以k为底取对数后得。所以，。因此得到具有n个结点的一般k叉树的最小深度是。第二节二叉树二叉树是使用最广泛的树型结构，这是因为一方面应用中有许多问题都可以通过二叉树来解决，另一方面一般树的问题也可转化为二叉树的问题来简便处理。那么，二叉树具有那些性质？如何存储表示和实现二叉树？1、二叉树的抽象数据类型定义1、二叉树的抽象数据类型定义所谓二叉树，是指结点的一个有限集合，它或为空集，或为满足下列性质的非空集合：有且只有一个根结点，其余结点分成左右两个互不相交的集合TL、TR，且TL、TR均为二叉树。直观上，二叉树就是一个最多有两个分支的树。在二叉树中，每个结点的左子树的根结点被称为该结点的左孩子（LeftChild），右子树的根结点被称为该结点的右孩子（RightChild）。二叉树的左右子树次序不能任意颠倒。二叉树与一般树的区别在于二叉树的子树有左右之分，以及二叉树定义中对树的度数的限制（即二叉树中不存在度大于
