《数据结构(严蔚敏)第6章（课堂PPT）》由会员分享，可在线阅读，更多相关《数据结构(严蔚敏)第6章（课堂PPT）（176页珍藏版）》请在金锄头文库上搜索。
1、05.09.2020,1,第六章 树和二叉树,05.09.2020,2,【课前思考】,上列家族谱系图可用如下关系表示： ， ，,05.09.2020,3,【学习目标】,1领会树和二叉树的类型定义，理解树和二叉树的结构差别。 2熟记二叉树的主要特性，并掌握它们的证明方法。3熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。4理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。5熟练掌握二叉树和树的各种存储结构及其建立的算法。6学会编写实现树的各种操作的算法。7了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。,05.09.2020,4,【重点和难点】,
2、二叉树和树的遍历及其应用是本章的学习重点，而编写实现二叉树和树的各种操作的递归算法也恰是本章的难点所在。,【知识点】,树的类型定义、二叉树的类型定义、二叉树的存储表示、二叉树的遍历以及其它操作的实现、线索二叉树、树和森林的存储表示、树和森林的遍历以及其它操作的实现、最优树和赫夫曼编码,05.09.2020,5,【学习指南】,本章是整个课程的第二个学习重点，也是整个课程中的一大难点。在本章的学习过程中主要应该学会如何根据二叉树和树的结构及其操作的递归定义编写递归算法。本章必须完成的算法设计题为: 6.27,6.28,6.33,6.41,6.43,6.45,6.46,6.47,6.49,6.50,
3、6.51,6.57,6.59,6.68和6.66。,05.09.2020,6,6.1 树的类型定义,6.2 二叉树的类型定义,6.3 二叉树的存储结构,6.4 二叉树的遍历,6.5 线索二叉树,6.6 树和森林的表示方法,6.7 树和森林的遍历,6.8 哈夫曼树与哈夫曼编码,05.09.2020,7,6.1 树的类型定义,树是由n（n0）个结点组成的有限集合。若n=0，称为空树；若n0，则： （1）其中必有一个称为根（root）的特定结点，它没有直接前驱，但有零个或多个直接后继； （2）除根结点以外的其它n-1结点可以划分为m（m0）个互不相交的有限集合T0，T1，Tm-1，每个集合Ti（i=
4、0,1,m-1）又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。 由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概念。,05.09.2020,8,ADT Tree 数据对象 D：,D是具有相同特性的数据元素的集合。,若D为空集，则称为空树 。 否则: (1) 在D中存在唯一的称为根的数据元素root； (2) 当n1时，其余结点可分为m (m0)个互 不相交的有限集T1, T2, , Tm，其中每一 棵子集本身又是一棵符合本定义的树， 称为根root的子树。,数据关系 R：,05.09.2020,9,基本操作：,查 找 类,插 入 类,
5、删 除 类,ADT Tree,05.09.2020,10,Root(T) / 求树的根结点,查找类：,Value(T, cur_e) / 求当前结点的元素值,Parent(T, cur_e) / 求当前结点的双亲结点,LeftChild(T, cur_e) / 求当前结点的最左孩子,RightSibling(T, cur_e) / 求当前结点的右兄弟,TreeEmpty(T) / 判定树是否为空树,TreeDepth(T) / 求树的深度,TraverseTree( T, Visit() ) / 遍历,05.09.2020,11,InitTree(n0,kielemtype R=r 其中，n为
6、树中结点个数，若 n=0，则为一棵空树， n 0时称为一棵非空树，而关系 r 应满足下列条件： （1）有且仅有一个结点没有前驱,称该结点为树根; （2）除根结点以外,其余每个结点有且仅有一个直接前驱; （3）树中每个结点可以有多个直接后继(孩子结点)。,05.09.2020,16,线性结构,树型结构,第一个数据元素 (无前驱),根结点 (无前驱),最后一个数据元素 (无后继),多个叶子结点 (无后继),其它数据元素 (一个前驱、 一个后继),其它数据元素 (一个前驱、 多个后继),05.09.2020,17,基 本 术 语,05.09.2020,18,结点:,结点的度:,树的度:,叶子结点:,
7、分支结点:,数据元素+若干指向子树的分支,分支的个数,树中所有结点的度的最大值,度为零的结点,度大于零的结点,H,I,J,M,05.09.2020,19,(从根到结点的)路径：,孩子结点、双亲结点 兄弟结点、堂兄弟 祖先结点、子孙结点,结点的层次:,树的深度：,由从根到该结点所经分支和结点构成,A,B,C,D,E,F,G,H,I,J,M,K,L,假设根结点的层次为1，第l 层的结点的子树根结点（即孩子结点）的层次为l+1,树中叶子结点所在的最大层次,05.09.2020,20,任何一棵非空树是一个二元组 Tree = （root，F） 其中：root 被称为根结点 F 被称为子树森林,森林：,
8、是m（m0）棵互 不相交的树的集合,A,root,B,C,D,E,F,G,H,I,J,M,K,L,F,05.09.2020,21,6.2 二叉树的类型定义,05.09.2020,22,二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。,A,B,C,D,E,F,G,H,K,根结点,左子树,右子树,05.09.2020,23,二叉树的特点： （1） 每个结点的度都不大于2，即每个结点的度为0、 1或2； （2） 每个结点的孩子结点次序不能任意颠倒。即每个孩子有左右之分。我们把位于左边的孩子叫做左孩子，位于右边的孩子叫做右孩子。,05.09.2020,24,二叉树
9、的五种基本形态：,N,空树,只含根结点,N,N,N,L,R,R,右子树为空树,L,左子树为空树,左右子树均不为空树,05.09.2020,25,二叉树的主要基本操作：,查 找 类,插 入 类,删 除 类,05.09.2020,26,Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit(); InOrderTraver
10、se(T, Visit(); PostOrderTraverse(T, Visit(); LevelOrderTraverse(T, Visit();,查 找 类,05.09.2020,27,InitBiTree(,插 入 类,05.09.2020,28,ClearBiTree(,删 除 类,05.09.2020,29,二叉树的重要特性,05.09.2020,30,性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结点。 (i1),用归纳法证明： 归纳基： 归纳假设： 归纳证明：,i = 1 层时，只有一个根结点： 2i-1 = 20 = 1；,假设对所有的 j，1 j i，命题成立；,二
11、叉树上每个结点至多有两棵子树， 则第 i 层的结点数 = 2i-2 2 = 2i-1 。,05.09.2020,31,性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k1）。,证明：,基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+ +2k-1 = 2k-1 。,05.09.2020,32,性质 3 ： 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。,证明：,设 二叉树上结点总数 n = n0 + n1 + n2 又 二叉树上分支总数(即边数) b = n1+2n2 而 n = b +1= b = n-
12、1 = n0 + n1 + n2 - 1 由此， n0 = n2 + 1 。,05.09.2020,33,两类特殊的二叉树：,满二叉树：指的是深度为k且含有2k-1个结点的二叉树。,完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,a,b,c,d,e,f,g,h,i,j,满二叉树必为完全二叉树， 而完全二叉树不一定是满二叉树。,05.09.2020,34,性质 4 ： 具有 n 个结点的完全二叉树的深度为 log2n +1 。,证明：,设完全二叉树的深度为 k 则根据第二条性质得 2k-1
13、-1 n 2k 1 或2k-1 n 2k 即 k-1 log2 n k, log2 n k log2 n +1 因为 k 只能是整数，因此， k =log2n + 1 。,05.09.2020,35,性质 5 ：,若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：(1) 若 i=1，则该结点是二叉树的根，无双亲， 否则，编号为 i/2 的结点为其双亲结点；(2) 若 2in，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点；(3) 若 2i+1n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。
14、,05.09.2020,36,可以用归纳法证明其中的（2）和（3）： 当i=1时，由完全二叉树的定义知，如果2i=2n，说明二叉树中存在两个或两个以上的结点，所以其左孩子存在且序号为2； 反之，如果2n，说明二叉树中不存在序号为2的结点，其左孩子不存在。同理，如果2i+1=3n， 说明其右孩子存在且序号为3；如果3n，则二叉树中不存在序号为3的结点， 其右孩子不存在。 假设对于序号为j(1ji)的结点，当2jn时，其左孩子存在且序号为2j，当2jn 时，其左孩子不存在；当2j+1n时， 其右孩子存在且序号为2j+1，当2j+1n时，其右孩子不存在。,05.09.2020,37,当i=j+1时，
15、根据完全二叉树的定义， 若其左孩子存在， 则其左孩子结点的序号一定等于序号为j的结点的右孩子的序号加1， 即其左孩子结点的序号等于 （2j+1）+1=2（j+1）=2i， 且有2in；如果2in， 则左孩子不存在。 若右孩子结点存在，则其右孩子结点的序号应等于其左孩子结点的序号加1，即右孩子结点的序号为2i+1，且有2i+1n；如果2i+1n，则右孩子不存在。 故（2）和（3）得证。,05.09.2020,38,由（2）和（3）我们可以很容易证明（1）。 当i=1时， 显然该结点为根结点，无双亲结点。当i1时，设序号为i的结点的双亲结点的序号为m，如果序号为i的结点是其双亲结点的左孩子，根据（
16、2）有i=2m，即m=i/2; 如果序号为i的结点是其双亲结点的右孩子，根据（3）有i=2m+1， 即m=（i-1）/2=i/2-1/2，综合这两种情况，可以得到，当i1时， 其双亲结点的序号等于i/2 。证毕。,对完全二叉树，还有以下性质： （1）若结点j序号为奇数且不等于1，则它的左兄弟为j-1； （2）若结点j序号为偶数且不等于n，它的右兄弟为j+1； （3） 结点j所在层数(层次)为 log2j+1；,05.09.2020,39,6.3 二叉树的存储结构,二、二叉树的链式 存储表示,一、 二叉树的顺序 存储表示,二叉树的结构是非线性的， 每一结点最多可有两个后继。 二叉树的存储结构有两种： 顺序存储结构和链式存储结构。,05.09.2020,40,#define MAX_T
