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