《李学俊201320141数据结构课件数据结构chapt6一》由会员分享，可在线阅读，更多相关《李学俊201320141数据结构课件数据结构chapt6一（22页珍藏版）》请在金锄头文库上搜索。
1、第六章 树和二叉树,数据结构: 线性结构(线性表, 栈,队列等) 非线性结构: 至少存在一个数据元素有不止一个直接前驱或后继(树,图等),6.1 树的定义和基本概念 6.2 二叉树 6.2.1 树的定义和基本术语 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.3 遍历二叉树 6.3.1 遍历二叉树 6.3.2 线索二叉树 6.4 树和森林 6.4.1 树的存储结构 6.4.2 森林与二叉树的转换,第六章 树和二叉树,6.4.3树和森林的遍历 6.6 赫夫曼树及其应用 6.6.1 最优二叉树（赫夫曼树） 6.6.2 赫夫曼编码,第六章 树和二叉树,树型结构是一类重要的非线性结构。树
2、型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界国是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。等等。,第六章 树和二叉树,6.1 树的定义 树(tree)是n个数据元素的有限集(记为T)，对任意一棵树T有： 存在唯一一个称为根(root) 的数据元素； 当n1时，其它数据元素可分为m(m0) 个互不相交的有限集T1,T2,Tm，其中每个集合Ti(i=1,2,m)本身又是一棵树，并称树
3、Ti是根的子树(subtree).,第六章 树和二叉树,树的表示法 1. 分支图表示法 2. 嵌套集合表示法,A,B,C,D,3. 广义表表示法 (A(B(D),C),第六章 树和二叉树,树的基本术语 1. 树的结点:包含一个DE和指向其子树的所有分支; 2. 结点的度:一个结点拥有的子树的个数,度为零的结点称为叶结点或终端结点。度不为零的结点称为分支结点或非终端结点。除根结点外，树的其它分支结点称为树的内部结点。 3. 树的度:树中所有结点的度的最大值Max(D(I) 含义:树中最大分支数为树的度; 4. 结点的层次及树的深度:根为第一层,根的孩子为第二层,若某结点为第k层,则其孩子为k+1
4、层. 树中结点的最大层次称为树的深度或高度,第六章 树和二叉树,5.森林:是m(m=0)棵互不相的树的集合 森林与树概念相近,相互很容易转换. 6.孩子:一个结点的子树的根称为该结点的孩子。相应的，该结点称为孩子的双亲。仿此不难理解祖先结点、子孙结点、兄弟结点的称呼。 7.有序树、无序树:如果树中各结点的子树从左到右看成是有序且不能交换则此树称为有序树，否则称为无序树。 树的抽象数据类型定义：见教材P.118-119。,第六章 树和二叉树,6.2 树的基本运算 初始化操作InitTree(&T)：创建一棵空树。 求根函数Root(T)：求树T的根； 求双亲函数Parent(T,cur_e)：在
5、树T中求x的双亲。 判树空函数TreeEmpty(T)：若树T为空树，则返回TRUE，否则返回FALSE。 求兄弟函数： 在T中求x的左兄弟LeftChild(T,cur_e) 在树T中求x的右兄弟RightChild(T,cur_e)。,第六章 树和二叉树, 建树函数CreateTree(&T,definition)：按definitio构造树T。 插入子树操作InsertChild(&T,&P,i,c)：插入c为T P所指结点的第i棵子树。 删除子树操作DeleteChild(&T,&P,i)：删除T中P所指结点的第i棵子树。 遍历树操作TraverseTree(T,visit()：按某种
6、顺序按visit()访问树T中各个结点。 置空树操作ClearTree(&T)：将树T置为空树。,第六章 树和二叉树,6.3 二叉树概念及性质 一. 二叉树概念 二叉树是结点数为0或每个结点最多只有左右两棵子树的树。二叉树是一种特殊的树，它的特点是： 每个结点最多只有两棵子树，即不存结点度大于2的结点； 子树有左右之分，不能颠倒。,6.3 二叉树,二. 二叉树性质 性质1. 在二叉树的第i层上至多有2i-1个结点(i1)。 性质2. 深度为k的二叉树至多有2k-1个结点(k)。 （深度一定，二叉树的最大结点数也确定） 性质3. 二叉树中,终端结点数n0与度为2的结点数n2有如下关系: n0=n
7、2+1,6.3 二叉树,满二叉树:深度为k，且有2k-1个结点的二叉树。 特点：（1）每一层上结点数都达到最大 （2）度为1的结点n1=0 结点层序编号方法：从根结点起从上到下逐层（层内从左到右）对二叉树的结点进行连续编号。,证明： 设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点均小于或等于2，所以有： Nn0n1n2 (6-1) 再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设B为二叉树中的分支总数， 则有：NB1。 由于这些分支都是由度为1和2的结点射出的，所有有： Bn1+2*n2 NB1n12n21 （62) 由式（61）和（62）得到： n0
8、+n1+n2=n1+2*n2+1 n0n21 命题得证 下面介绍两种特殊形态的二叉树：满二叉树和完全二叉树。,6.3 二叉树,6.3 二叉树,满二叉树:深度为k，且有2k-1个结点的二叉树。 特点：（1）每一层上结点数都达到最大 （2）度为1的结点n1=0 结点层序编号方法：从根结点起从上到下逐层（层内从左到右）对二叉树的结点进行连续编号。,6.3 二叉树,完全二叉树:深度为k，结点数为n的二叉树，当且仅当每个结点的编号都与相同深度的满二叉树中从1到n的结点一一对应时，称为完全二叉树。,6.3 二叉树,完全二叉树的特点: （1）每个结点i的左子树的深度Lhi-其结点i的右子树的深度Rhi等于0
9、或1，即叶结点只可能出现在层次最大或次最大的两层上。 （2）完全二叉树结点数n满足2k-1-1n2k-1 （3）满二叉树一定是完全二叉树，反之不成立。,6.3 二叉树,LH2=0 RH2=1,LH1=3 RH1=1 LH1 -RH1=2,非完全二叉树 非完全二叉树,LH2-RH2=0-1=-1,6.3 二叉树,性质4. 结点数为n的完全二叉树，其深度为 log2n + 1 证明： 符号【x】表示不大于x的最大整数。 假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到：2k-11n=2k-1 或 2k-1=n2k 取对数得到：k1log2nk 因为k是整数。所以有：k【log2n】1。,
10、6.3 二叉树,性质5. 在按层序编号的n个结点的完全二叉树中，任意一结点i(1in)有： i=1时，结点i是树的根；否则(i1)，结点i的双亲为结点i/2。 2in时，结点i无左孩子，为叶结点；否则，结点i的左孩子为结点2i。 2i+1n时，结点i无右孩子；否则，结点i的右孩子为结点2i+1。,I/2,i,I+1,2i,2i+1,2(I+1),2i+3,I+1,2(I+1),2i+3,i,2i,2i+1,图6.11 完全二叉树中结点i和i+1,(a)i和i+1结点在同一层,(b)i和i+1结点不在同一层,如图6.11所示为完全二叉树上结点及其 左右好在结点之间的关系。,在此过程中，可以从（2）和（3）推出（1），所以先证明（2）和（3）。 对于i1，由完全二叉树的定义，其左孩子是结点2，若2n，即不存在结点2，此是，结点i无孩子。结点i的由孩子也只能是结点3，若结点3不存在，即3n，此时结点i无右孩子。 对于i1，可分为两种情况： （1）设第j（1n，则无左孩子：,其右孩子必定为第j1层的第二个结点，编号为2i1。若2i+1n，则无右孩子。 （2）假设第j（11时，如果i为左孩子，即2（i/2)=i,则i/2是i的双亲；如果i为右孩子，i2p+1,i的双亲应为p，p（i1）/2=i/2. 证毕。,
