《计算机软件技术基础 教学课件 ppt 作者 牟艳 陈慧萍 第4章 树形结构》由会员分享，可在线阅读，更多相关《计算机软件技术基础 教学课件 ppt 作者 牟艳 陈慧萍 第4章 树形结构（65页珍藏版）》请在金锄头文库上搜索。
1、第四章 树形结构,本章基本内容与要求,基本内容 树的基本概念及存储结构 二叉树概念 二叉树的存储结构 二叉树的操作 二叉排序树 哈夫曼树 要求：掌握上述所有内容,第一节 树的基本概念及存储结构,一、树的基本概念,4.1.1 树的定义,1树的定义,树是由n（n0）个结点组成的有限集合。若n=0，称为空树；若n0，则： （1）有一个特定的称为根（root）的结点。它只有直接后继，但没有直接前驱；,（2）除根结点以外的其它结点可以划分为m（m0）个互不相交的有限集合T0，T1，Tm-1，每个集合Ti（i=0,1,m-1）又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多
2、个直接后继。 由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概念。,在图4-1c中，树的根结点为A，该树还可以分为三个互不相交子集T0，T1，T2，具体请参见图4-2，其中T0=B，E，F，J，K，L，T1=C，G，T2=D，H，I，M，其中的T0，T1，T2都是树，称为图4-1c中树的子树，而T0，T1，T2又可以分解成若干棵不相交子树。如T0可以分解成T00，T01两个不相交子集，T00=E，J，K，L，T01=F，而T00又可以分为三个不相交子集T000，T001，T002，其中，T000=J，T001=K，T002=L。,2树的逻辑结构描述,一棵树的逻辑结构可以用二元组描
3、述为： tree =(T,R) T=Ti1in;n0,Tielemtype R=r 其中，n为树中结点个数，若 n=0，则为一棵空树， n 0时称为一棵非空树，而关系 r 应满足下列条件：,例如，对图4-1(c )的树结构,可以二元组表示为： T=A，B，C，D，E，F，G，H，I，J，K，L，M R=r r=(A,B)，(A,C)，(A,D)，(B,E)，(B,F)，(C,G)，(D,H)，(D,I)，(E,J)，(E,K)，(E,L)，(H,M),（1）有且仅有一个结点没有前驱,称该结点为树根; （2）除根结点以外,其余每个结点有且仅有一个直接前驱; （3）树中每个结点可以有多个直接后继(
4、孩子结点)。,4.1.2 基本术语,1.结点 指树中的一个数据元素，一般用一个字母表示。,2.度 一个结点包含子树的数目，称为该结点的度。,3.树叶（叶子） 度为0的结点，称为叶子结点或树叶，也叫终端结点。,4.孩子结点 若结点X有子树，则子树的根结点为X的孩子结点，也称为孩子，儿子，子女等。,5.双亲结点 若结点X有子女Y，则X为Y的双亲结点。,6.祖先结点 从根结点到该结点所经过分枝上的所有结点为该结点的祖先，如图4-1c中M的祖先有A，D ，H 。,7.子孙结点 某一结点的子女及子女的子女都为该结点子孙。,8.兄弟结点 具有同一个双亲的结点，称为兄弟结点。,9.分枝结点 除叶子结点外的所
5、有结点，为分枝结点，也叫非终端结点。,10层数 根结点的层数为1，其它结点的层数为从根结点到该结点所经过的分支数目再加1。,11. 树的高度（深度） 树中结点所处的最大层数称为树的高度，如空树的高度为0，只有一个根结点的树高度为1。,12.树的度 树中结点度的最大值称为树的度。,13. 有序树 若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。,14. 无序树 若一棵树中所有子树的次序无关紧要，则称为无序树。,15森林（树林） 若干棵互不相交的树组成的集合为森林。一棵树可以看成是一个特殊的森林。,4.1.3 树的存储结构,4.2 二叉树,4.2.1 二叉树的定义,1二叉
6、树的定义,和树结构定义类似，二叉树的定义也可以递归形式给出： 二叉树是n（n0）个结点的有限集，它或者是空集（n=0），或者由一个根结点及两棵不相交的左子树和右子树组成。 二叉树的特点是每个结点最多有两个孩子，或者说，在二叉树中，不存在度大于2的结点，并且二叉树是有序树（树为无序树），其子树的顺序不能颠倒，因此，二叉树有五种不同的形态，参见图4-5 。,1. 满二叉树 ：二叉树的每一层上的结点数都达到最大，否则就不是满二叉树。,2. 完全二叉树 如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1 n的结点一一对应，则称这棵二叉树为完全二叉树。 从完全二叉树定
7、义可知，结点的排列顺序遵循从上到下、从左到右的规律。所谓从上到下，表示本层结点数达到最大后，才能放入下一层。从左到右，表示同一层结点必须按从左到右排列，若左边空一个位置时不能将结点放入右边。,4.2.2 两种特殊的二叉树,从满二叉树及完全二叉树定义还可以知道，满二叉树一定是一棵完全二叉树，反之完全二叉树不一定是一棵满二叉树。满二叉树的叶子结点全部在最底层，而完全二叉树的叶子结点可以分布在最下面两层。深度为4的满二叉树和完全二叉树如图4-6所示。,4.2.3 二叉树的性质,性质1 若二叉树的层数从1开始，则二叉树的第k层结点数，最多为2k-1个（k0）。 可以用数学归纳法证明之。,性质2 深度（
8、高度）为k的二叉树最大结点数为2k-1（k0）。,证明： 深度为k的二叉树，若要求结点数最多，则必须每一层的结点数都为最多，由性质1可知，最大结点数应为每一层最大结点数之和。既为 20+21+2k-1=2k-1。,性质3 对任意一棵二叉树，如果叶子结点个数为n0，度为2的结点个数为n2，则有n0=n2+1。,证明：设二叉树中度为1的结点个数为n1，根据二叉树的定义可知，该二叉树的结点数n=n0+n1+n2。又因为在二叉树中，度为0的结点没有孩子，度为1的结点有1 个孩子，度为2的结点有2个结孩子，故该二叉树的孩子结点数为 n0*0+n1*1+n2*2 ，而一棵二叉树中，除根结点外所有都为孩子
9、结点，故该二叉树的结点数应为孩子结点数加1即：n=n0*0+n1*1+n2*2+1因此,有 n=n0+n1+n2=n0*0+n2*1+n2*2+1，最后得到n0=n2+1。,为继续给出二叉树的其它性质，先定义两种特殊的二叉树。,性质4 具有n个结点的完全二叉树高度为log2(n)+1 或 log2（n+1） 。 (注意x表示取不大于x的最大整数，也叫做对x下取整，x表示取不小于x的最小整数，也叫做对x上取整。),证明：设该完全二叉树高度为k，则该二叉树的前面k-1层为满二叉树，共有2k-1-1个结点，而该二叉具有k层，第k层至少至少有1个结点，最多有2k-1个结点。因此有下面的不等式成立：（2
10、k-1 1） +1 n （2k-1-1）+2k-1，即有 2k-1n2k-1。由式子后半部分可知, n2k-1 由式子前半部分可知 2k-1n 由有 n+12k ，同时取对数得： log2(n+1)k 故 klog2(n+1),即 k=log2(n+1)。即得到第二个结论。 由有2k-1n,同时取对数得：klog2n+1即 k=log2 n+1,即第一个结论成立,证毕。,性质5 如果将一棵有n个结点的完全二叉树从上到下，从左到右对结点编号1，2，n，然后按此编号将该二叉树中各结点顺序地存放于一个一维数组中，并简称编号为j的结点为 j(1jn)，则有如下结论成立：,（1）若 j=1，则结点j为根
11、结点，无双亲，否则j的双亲为 j/2； （2）若2jn，则结点j的左子女为2j ,否则无左子女。即满足2jn的结点为叶子结点； （3）若2j+1n，则结点j的右子女为2j+1，否则无右子女； （4）若结点j序号为奇数且不等于1，则它的左兄弟为j-1； （5）若结点j序号为偶数且不等于n，它的右兄弟为j+1； （6） 结点j所在层数(层次)为log2j+1；,4.2.4 树、森林和二叉树的转换,可以分为三步： （1） 连线 指相邻兄弟之间连线。,（2） 抹线 指抹掉双亲与除左孩子外其它孩子之间的连线。,（3） 旋转 只需将树作适当的旋转。,具体实现过程见图-25。,1树转换成二叉树,2森林转换成
12、二叉树,（1） 将森林中每一棵树分别转换成二叉树 这在刚才的树转换成二叉树中已经介绍过。,（2）合并 使第n棵树接入到第n-1棵的右边并成为它的右子树，第 n-1 棵二叉树接入到第n-2 棵的右边并成为它的右子树，第2棵二叉树接入到第1棵的右边并成为它的右子树，直到最后剩下一棵二叉树为止。,C,D,B,A,F,E,I,A,A,A,H,G,E,F,I,H,G,G,F,E,D,C,B,A,I,H,A,D,B,C,图,4,-,26,森林转换成二叉树示意图,合并,.2. 二叉树的存贮结构,1顺序存贮结构,将一棵二叉树按完全二叉树顺序存放到一个一维数组中，若该二叉树为非完全二叉树，则必须将相应位置空出来
13、，使存放的结果符合完全二叉树形状。如图6-7给出了顺序存贮形式。,对于一棵二叉树,若采用顺序存贮时,当它为完全二叉树时,比较方便,若为非完全二叉树,将会浪费大量存贮存贮单元。最坏的非完全二叉树是全部只有右分支,设高度为K,则需占用2K-1个存贮单元,而实际只有k个元素,实际只需k个存储单元。因此，对于非完全二叉树，宜采用下面的链式存储结构。,2二叉链表存贮结构,（1）二叉链表表示 将一个结点分成三部分,一部分存放结点本身信息,另外两部分为指针,分别存放左、右孩子的地址。,二叉链表中一个结点可描述为:,对于图-7所示二叉树,用二叉链表形式描述见图4-8。,对于一棵二叉树,若采用二叉链表存贮时,当
14、二叉树为非完全二叉树时,比较方便,若为完全二叉树时,将会占用较多存贮单元(存放地址的指针)。若一棵二叉树有n个结点,采用二叉链表作存贮结构时,共有2n个指针域,其中只有n-1个指针指向左右孩子,其余n+1个指针为空,没有发挥作用,被白白浪费掉了。,第四节 二叉树的操作,二叉树的遍历是指按照一定的次序访问树中所有结点，并且每个结点仅被访问一次。它是最基本的运算，是二叉树中其他所有运算的基础。在二叉树中，左子树和右子树是有严格区别的，因此在遍历一棵非空二叉树时，根据访问根结点，遍历左子树和遍历右子树之间的先后关系，可以得到6种遍历方法。B1若按先左后右的原则，则通常使用下面三种遍历方法，见表4-1
15、。,4.2.1 二叉树遍历的概念,表4-1 遍历方法表,a) b),4-11b： 先序遍历：ABCDEFG 中序遍历：CBDAEGF 后序遍历：CDBGFEA,4-11a： 先序遍历：ABDC 中序遍历：BDAC 后序遍历：DBCA,4.2.2 二叉树遍历算法的实现,链式存储结构二叉树的定义： struct bitree elemtype data; / elemtype：结点数据类型 bitree *lchild; bitree *rchild; ; （1）先序遍历二叉树算法,void preorde (bitree *root) if(root!=NULL) cout data lchild); preorde (root - rchild); ,中序遍历也是一个递归过程，对于一棵二叉树，其过程为：1）中序遍历左子树，2）访问根结点，3）中序遍历右子树，直到二叉树为空时退出。 算法描述如下： void inorder(bitree *root) if(root != NULL) inorder(root - lchild); cout data rchild); ,（2）中序遍历二叉树算法,同样是一个递归过程，
