《Ch_6 树和二叉树》由会员分享，可在线阅读，更多相关《Ch_6 树和二叉树（207页珍藏版）》请在金锄头文库上搜索。
1、1,知识回顾,线性表 一般的线性表 特殊的线性表：栈、队列线性表的扩展：数组、广义表特点：有序前趋、后继,2,第六章 树和二叉树,树是以分支关系定义的层次结构。树结构在客观世界广泛存在: 在自然科学，如地理学领域，水系、地貌（等高线）、行政区划等都具有树结构关系； 在社会人文领域，人类社会构成、组织机构等也具有树结构关系。,树型结构：非线性数据结构,4,要求,1. 熟练掌握二叉树的结构特性。2. 熟悉二叉树的各种存储结构的特点及适用范围。3. 掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。4. 熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。5.
2、 熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。6. 了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。,6.1 树的定义和基本术语,6.2 二叉树,6.3 遍历二叉树和线索二叉树,6.4 树和森林,6.5 赫夫曼树与其应用,主要内容,6,6.1.1 树的定义,树（tree）是n (n0)个结点的有限集。在任意一棵非空树中：（1）有且仅有一个特定的称为根的结点；（2）当n1时，其余结点可分为m (m0)个互不相交的有限集T1,T2,Tm，其中每一个集合本身又是一棵树，并且称为根的子树。,根,子树,树的表示法,图形表示法嵌套集合表示法广义表表示法凹入表示法左孩子右兄弟表示法,图
3、形表示法,西安石油大学,叶子,根,子树,嵌套集合表示法,( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) 约定：根作为由子树森林组成的表的名字写在表的左边,广义表表示法,凹入表示法,又称目录表示法,左孩子右兄弟表示法,多叉树转为了二叉树,15,数据对象 D：,D是具有相同特性的数据元素的集合。,若D为空集，则称为空树 。 否则: (1) 在D中存在唯一的称为根的数据元素root；(2) 当n1时，其余结点可分为m (m0)个互 不相交的有限集T1, T2, , Tm，其中每一 棵子集本身又是一棵符合本定义的树， 称为根root的
4、子树。,数据关系 R：,ADT Tree,16,基本操作：,查 找 类,插 入 类,删 除 类,17,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() ) / 遍历,18,InitTree(&T) / 初始化置空树
5、,插入类：,CreateTree(&T, definition) / 按定义构造树,Assign(T, cur_e, value) / 给当前结点赋值,InsertChild(&T, &p, i, c) / 将以c为根的树插入为结点p的第i棵子树,19,ClearTree(&T) / 将树清空,删除类：,DestroyTree(&T) / 销毁树的结构,DeleteChild(&T, &p, i) / 删除结点p的第i棵子树,20,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,树根,例如:,21
6、,() 有确定的根；() 树根和子树根之间为有向关系。,有向树：,有序树：,子树之间存在确定的次序关系。,无序树：,子树之间不存在确定的次序关系。,22,对比树型结构和线性结构的结构特点,线性结构,树型结构,第一个数据元素 (无前驱),根结点 (无前驱),最后一个数据元素 (无后继),多个叶子结点 (无后继),其它数据元素(一个前驱、 一个后继),其它数据元素(一个前驱、 多个后继),对比树型结构和线性结构的结构特点,6.1.2 基本术语,25,结点:,结点的度:,树的度:,叶子结点:,分支结点:,数据元素+若干指向子树的分支,分支的个数,树中所有结点的度的最大值,度为零的结点,度大于零的结点
7、,D,H,I,J,M,26,子孙:以某结点为根的子树中的任一结点。,A,B,C,D,E,F,G,H,I,J,M,K,L,孩子:结点的子树的根。,双亲:该结点称为孩子的双亲。,兄弟:同一个双亲的孩子之间互称兄弟。,祖先:从根到该结点所经分支上的所有结点,27,有序树：子树之间存在确定的次序关系,无序树：子树之间不存在确定的次序关系,树的深度：树中结点的最大层次,堂兄弟:其双亲在同一层的结点,结点的层次:假设根结点的层次为1，第l 层的结点的子树根结点的层次为l+1,28,结点A的度：3结点B的度：2结点M的度：0,叶子：K，L，F，G，M，I，J,结点A的孩子：B，C，D结点B的孩子：E，F,结
8、点I的双亲：D结点L的双亲：E,结点B，C，D为兄弟结点K，L为兄弟,树的度：3,结点A的层次：1结点M的层次：4,树的深度：4,结点F，G为堂兄弟,29,任何一棵非空树是一个二元组 Tree = （root，F）其中：root 被称为根结点 F 被称为子树森林,森林：,是m（m0）棵互不相交的树的集合,A,root,B,C,D,E,F,G,H,I,J,M,K,L,F,6.2 二叉树,最简单的树二叉树,先研究最简单、最有规律的树，然后设法把一般的树转化为简单树。,解决思路：,树的操作实现比较复杂。,为何要重点研究每结点最多只有两个 “叉” 的树？二叉树的结构最简单，规律性最强；可以证明，所有树
9、都能转为唯一对应的二叉树，不失一般性。,二叉树:或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。,A,B,C,D,E,F,G,H,K,根结点,左子树,右子树,二叉树的特点（1）每个结点至多有二棵子树(即不存在度大于2的结点)；（2）二叉树的子树有左、右之分，且其次序不能任意颠倒。,二叉树的五种基本形态：,空树,只含根结点,L,R,R,右子树为空树,L,左子树为空树,左右子树均不为空树,34,二叉树的主要基本操作：,查 找 类,插 入 类,删 除 类,35,Root(T); Value(T, e); Parent(T, e); LeftChild(T, e);
10、RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit(); InOrderTraverse(T, Visit(); PostOrderTraverse(T, Visit(); LevelOrderTraverse(T, Visit();,36,InitBiTree(,37,ClearBiTree(,38,二叉树的重要特性,39,性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结点。 (i1),用归纳法证明： 归纳基
11、： 归纳假设： 归纳证明：,i = 1 层时，只有一个根结点： 2i-1 = 20 = 1；,假设对所有的 j，1 j i，命题成立；,二叉树上每个结点至多有两棵子树，则第 i 层的结点数 = 2i-2 2 = 2i-1 。,40,性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k1）。,证明：,基于性质1，深度为 k 的二叉树上的结点数至多为 20+21+ +2k-1 = 2k-1 。,41,性质 3 ： 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。,证明： 二叉树中全部结点数nn0+n1+n2(叶子数1度结点数2度
12、结点数)又二叉树中全部结点数nB+1 ( 总分支数根结点 ) （除根结点外，每个结点必有一个直接前趋，即一个分支）而 总分支数B= n1+2n2 (1度结点必有1个直接后继，2度结点必有2个)三式联立可得： n0+n1+n2= n1+2n2 +1, 即n0=n2+1,42,两类特殊的二叉树：,满二叉树：深度为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,43,44,完全二叉树特点：,（1）叶子结点只可能在层次最大
13、的两层上出现;（2）对任一结点，若其右分支下子孙的最大层次为i，则其左分支下子孙的最大层次必为i或i+1。,满二叉树与完全二叉树的区别,满二叉树是叶子一个也不少的树，而完全二叉树虽然前k-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。为何要研究这两种特殊形式？因为它们在顺序存储方式下可以复原。,45,性质 4 ：具有 n 个结点的完全二叉树的深度为 log2n +1 。 x 表示= x的最大整数。,证明：设完全二叉树的深度为 k 则根据第二条性质得 2k-1 (第k层第一个结点的编号） n 2k（第k1层第一个结点的编号） 即 k-1 log2 n = (2k-1-1)+1，根据第二条性质得 n 2k -1，因此：2k-1 n 2k 即 k-1 log2 n n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点；(3) 若 2i+1n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。,第k层上最后一个结点的编号是2k-1,它的右孩子是第k+1层上最后一个结点,编号是2k+1-1,右孩子编号是它的双亲结点编号的(2k-1)*2+1,左孩子的编号是(2k-1)*2所以，编号为 i 的结点的左孩子结点编号是2i，右孩子结点编号是2i+1,双亲结点编号i/2,
