chap6-1树与二叉树

1、数字媒体技术教研室 乐小燕,1,数据结构（C）,愿大家开心学习、学习开心！,第6章 树和二叉树,第6章 主要内容,2,数字媒体技术教研室 乐小燕,树和二叉树的概念及特点 二叉树的存储表示 二叉树的遍历 树与森林 树、森林与二叉树的转换 Huffman树,6.1 树的定义和基本术语,一、树的定义 树(tree)是n(n=0)个结点的有限集。 当n0时(非空树中), (1)有且仅有一个特定的称为根(root)的结点; (2)当n1时,其余结点可分为m(m0)个互不相交的有限集T1,T2,.,Tm,其中每个集合本身又是一棵树。称为根的子树(subtree)。,数字媒体技术教研室 乐小燕,3,4,r

2、是一个特定的称为根(root)的结点，它只有直接后继，但没有直接前驱； 根以外的其他结点划分为 m (m 0) 个互不相交的有限集合T1, T2, , Tm，每个集合又是一棵树，并且称之为根的子树。 每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。,树的定义是采用递归方法,5,一、树的定义,树是n个结点的有限集,T1,T2,T3,递归定义,树的性质： 递归性， 层次性。 特点：树中至少有一个结点-根f 树中各子树是互不相交的集合。,(a) 一棵树结构 (b)一个非树结构 (c)一个非树结构,一、树的定义,A（B（D，E（H，I），F），C（G）,7,树的表示方式,凹入表示,嵌

3、套集合,括号表示法,树的应用举例文件结构,结点的度：结点所拥有的子树的棵数。 树的度：树中各结点度的最大值。,二、树的基本术语,叶子结点：度为0的结点，也称为终端结点。 分支结点：度不为0的结点，也称为非终端结点。,二、树的基本术语,孩子、双亲：树中某结点子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点； 兄弟结点：具有同一个双亲的孩子结点互称为兄弟。,二、树的基本术语,祖先、子孙：在树中，如果有一条路径从结点x到结点y，那么x就称为y的祖先，而y称为x的子孙。,二、树的基本术语,路径：如果树的结点序列n1, n2, , nk有如下关系：结点ni是ni+1的双亲（1=ik）

4、，则把n1, n2, , nk称为一条由n1至nk的路径；路径上经过的边的个数称为路径长度。,二、树的基本术语,结点所在层数：也称结点的层次，即从根到该结点所经路径上的分支数。如：根结点的层数为1；其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。,二、树的基本术语,树的深度：树中距离根结点最远的结点所处的层次即为树的深度。空树的深度为0。 树的高度：从下往上定义。叶结点的高度为1，非叶结点的高度 = 它的子女结点高度的最大值 + 1,二、树的基本术语,层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从1开始的连续自然数。,二、树的基本术语,有序树、无序树：如果一

5、棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，称为无序树。,数据结构中讨论的一般都是有序树,二、树的基本术语,森林：m (m0)棵互不相交的树的集合。,二、树的基本术语,同构：对两棵树，若通过对结点适当地重命名，就可以使这两棵树完全相等（结点对应相等，结点对应关系也相等），则称这两棵树同构。,二、树的基本术语,二、树的基本术语,数字媒体技术教研室 乐小燕,20,21,例题：已知一棵树边的集合为,画出这棵树，并回答下列问题：,1、根结点、叶子结点？ 2、结点F的双亲、祖先、孩子？ 3、B的子孙、B的兄弟、F的兄弟？ 4、结点J和M的层次号？ 5、树的深度、度数，以结点D为根的子树

6、的深度？,23,性质1： 树中的结点数等于所有结点的度数加1。,三、树的性质,24,性质2：度为m的树中第i层上至多有mi-1个结点，这里应有i1。 证明(采用数学归纳法),三、树的性质,25,性质3：高度为h的m次树至多有 个结点。 证明：由树的性质2可知,第i层上最多结点数为mi-1(i=1,2,h),显然当高度为h的m次树(即度为m的树)上每一层都达到最多结点数时,整个m次树具有最多结点数,因此有： 整个树的最多结点数=每一层最多结点数之和 =m0+m1+m2+mh-1 = 。,(等比数列求和公式),三、树的性质,性质4：具有n个结点的m次树的最小高度为 logm(n(m-1)+1) 证

7、明：设具有n个结点的m次树的高度为h,若在该树中前h-1层都是满的,即每一层的结点数都等于mi-1个(1ih-1),第h层(即最后一层)的结点数可能满,也可能不满,则该树具有最小的高度。其高度h可计算如下：,根据树的性质3可得： n 乘(m-1)后得： mh-1n(m-1)+1mh 以m为底取对数后得：h-1logm(n(m-1)+1)h 即logm(n(m-1)+1)hlogm(n(m-1)+1)+1 因h只能取整数,所以 h=logm(n(m-1)+1) 结论得证。,或,或,27,根据树的性质3可得： n,乘(m-1)后得：,以m为底取对数后得：,即,因h只能取整数, 所以:,h-1 lo

8、gm(n(m-1) h,mh-1-1n(m-1)mh-1,mh-1 n(m-1) mh,logm(n(m-1) h logm(n(m-1)+1,或,结论得证。,28,例1: 含10个结点的三次树的最小高度是多少？,例2: 含14个结点的三次树的最小高度是多少？,3,4,三、树的性质,29,四、树的抽象数据类型,数据对象D:,ADT Tree ,D是具有相同特性的数据元素的结合,数据关系R:,略！,基本操作:,(1) InitTree( (4) ClearTree ( (7) Root(T); (8) Value(T, cur_e); (9) Assign(T, cur_e, value); (

9、10) Parent(T, cur_e); (11) LeftChild(T, cur_e); (12) RightSibling (T, cur_e); (13) InsertChild(,线性结构,树结构,无前驱,无双亲,无后继,无孩子,一个前驱,一个后继,一个双亲,多个孩子,一对一 一对多,五、树结构和线性结构的比较,数字媒体技术教研室 乐小燕,32,一、二叉树的定义 一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。 每个结点最多有两个子女，分别称为左子女和右子女。 二叉树中不存在度大于2的结点。 二叉树的子树有左

10、、右之分，子树的次序不能颠倒。,6.2 二叉树,一、二叉树的定义,二叉树是分支数最大不超过2的有根有序树。,数字媒体技术教研室 乐小燕,33,二叉树的五种不同形态,L,L,R,R,34,思考题： 高度为k的2叉树至多有多少个结点？ 此情况下树的形状是什么样的？试画出来。,k=1，2，3，4.,35,定义1 满二叉树 (Full Binary Tree) 定义2 完全二叉树 (Complete Binary Tree),两种特殊二叉树,在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。,满二叉树的特点：,叶子只能出现在最下一层； 只有度为0和度为2的结点。,特殊二叉

11、树满二叉树,不是满二叉树，虽然所有分支结点都有左右子树，但叶子不在同一层上。,满二叉树在同样深度的二叉树中结点个数最多 满二叉树在同样深度的二叉树中叶子结点个数最多,特殊二叉树满二叉树,对一棵具有n个结点的二叉树按层序编号，如果编号为i（1in）的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同。,特殊二叉树完全二叉树,若设二叉树的深度为 k，则共有 k 层。除第 k 层外，其它各层 (1k-1) 的结点数都达到最大个数，第k层从右向左连续缺若干结点，这就是完全二叉树。,在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树。,A,1,5,2,3,4,6,7,

12、9,10,B,C,D,E,F,G,H,I,J,不是完全二叉树，结点10与满二叉树中的结点10不是同一个结点,特殊二叉树完全二叉树,1. 叶子结点只能出现在最下两层，且最下层的叶子结点都集中在二叉树的左部； 2. 完全二叉树中如果有度为1的结点，只可能有一个，且该结点只有左孩子。 3. 深度为k的完全二叉树在k-1层上一定是满二叉树。,完全二叉树的特点,41,正则二叉树 理想平衡二叉树,满的,二、二叉树的性质,性质1：若二叉树结点的层次从 1 开始, 则在二叉树的第 i 层最多有 2i-1 个结点。( i1) 性质2 ：深度为 k 的二叉树最少有 k 个结点，最多有 2k-1个结点。( k1 )

13、 因为每一层最少要有1个结点，因此，最少结点数为 k。最多结点个数借助性质1：用求等比级数前k项和的公式： 20 +21 +22 + +2k-1 = 2k-1,数字媒体技术教研室 乐小燕,42,43,性质3：对任何一棵二叉树，如果其叶结点有 n0 个, 度为 2 的非叶结点有 n2 个, 则有 n0n21 若设度为 1 的结点有 n1 个，总结点数为n， 总边数为e，则根据二叉树的定义， n = n0+n1+n2 e = 2n2+n1 = n-1 因此，有 2n2+n1 = n0+n1+n2-1 n2 = n0-1 n0 = n2+1,二、二叉树的性质,44,性质4 具有 n (n0) 个结点

14、的完全二叉树的深度为 设完全二叉树的深度为k，则有 2k-1-1 n 2k-1 取对数 k-1 log2(n) k 有,上面k-1层结点数,包括第k层的最大结点数,23-1,24-1,二、二叉树的性质,45,性质5 如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1, 2, , n，则有以下关系： 若i = 1, 则 i 无双亲 若i 1, 则 i 的双亲为i2 若2*i = n, 则 i 的左子女为 2*i， 若2*i+1 = n, 则 i 的右子女为2*i+1 若 i 为奇数, 且i != 1, 则其左兄弟为i-1, 若 i 为偶数, 且i != n, 则其右兄弟为i+

15、1,二、二叉树的性质,具有3个结点的树和具有3个结点的二叉树的形态,二叉树和树是两种树结构。,三、树与二叉树的比较,47,四、二叉树的ADT,ADT BinaryTree ,教材121页,数据对象D:,D是具有相同特性的数据元素的结合,数据关系R:,基本操作:,(1)InitBiTree( ADT BinaryTree,6.3 二叉树的存储表示,一、二叉树的顺序存储表示数组,数字媒体技术教研室 乐小燕,48,完全二叉树 一般二叉树 的顺序表示 的顺序表示,二叉树的顺序存储结构,#define MAX_TREE_SIZE typedef TElemType SqBiTreeMAX_TREE_SI

16、ZE; SqBiTree bt;,数字媒体技术教研室 乐小燕,49,结点编号从1开始到 n 。（与数组下标区分开）,课堂练习,写出下图二叉树的顺序存储结构。,数字媒体技术教研室 乐小燕,50,0表示不存在此结点,51,极端情形: 只有右单支的二叉树,二叉树的顺序存储结构一般仅存储完全二叉树,6.3 二叉树的存储表示,二、二叉树的链表存储表示 二叉树结点定义：每个结点有3个数据成员，data域存储结点数据，leftChild和rightChild分别存放指向左子女和右子女的指针。,数字媒体技术教研室 乐小燕,52,二叉链表,53,三叉链表,二、二叉树的链表表示（三叉链表）,每个结点增加一个指向双

17、亲的指针parent，使得查找双亲也很方便。,54,二叉树链表表示的示例,二叉树 二叉链表 三叉链表,55,二、二叉树的链式存储结构,typedef struct BiNode TElemType data; struct BiNode *lchild,*rchild ; BiNode,*BiTree;,PARENT,LCHILD,RCHILD,二叉链表,三叉链表, *parent; /三叉链表,56,F,含有n个结点的二叉链表中有n+1个空链域。 -教材126页！,小结,树的基本概念及术语 结点、度、子女、双亲、兄弟、祖先、子孙、 分支结点、层次、深度、高度、路径 二叉树的概念及性质 性质1：若二叉树结点的层次从 1 开始, 则在二叉树的第 i 层最多有 2i-1 个结点。( i1) 性质2 ：深度为 k 的二叉树最少有 k 个结点，最多有 2k-1个结点。( k1 ) 性质3：对任何一棵二叉树，如果其叶结点有 n0 个, 度为 2 的非叶结点有 n2 个, 则有 n0n21 性质4 : 具有 n (n0) 个结点的完全二叉树的深度为 log2(n+1),数字媒体技术教研室 乐小燕,57,58,性质5 : 如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1, 2, , n，则有以下关系： 若i