第五章树及二叉树 1树的定义和术语 2.二叉树:定义、性质、存储 3.二又树的遍历 4.二叉树遍历的迭代器类 *5.中序穿线树 6.最优二叉树及其应用 7.树和森林
1.树的定义和术语 2.二叉树:定义、性质、存储 3.二叉树的遍历 4. 二叉树遍历的迭代器类 *5. 中序穿线树 6. 最优二叉树及其应用 7. 树和森林 第五章 树及二叉树
树和森林 树:n>0个结点的集合,根+其余结点分为m>=0个 高度为4、度为3的树 集合,每一个集合本身又是一棵树(子树) 结点的度:该结点的子树数目 树的度:树中各结点度数的最大值 叶子、父结点、儿子结点、兄弟结点 ·祖先结点:从根结点到该结点的路径上所有结点 层次、高度:根为1,依次往下数 有序树:规定所有结点的儿子结点次序,否则为无序树 森林:m>=0棵互不相交树的集合 其它表示方法: 1.(A(B(L,E),c(F),D(G(),H) 2类似于书籍的目录表示法。 高度定义为层数或层数-1,都可以;本书定义为层数
树和森林 •树：n > 0 个结点的集合，根+其余结点分为 m >= 0 个 集合，每一个集合本身又是一棵树（子树） •结点的度：该结点的子树数目 •树的度：树中各结点度数的最大值 •叶子、父结点、儿子结点、兄弟结点 •祖先结点：从根结点到该结点的路径上所有结点 •层次、高度：根为1, 依次往下数 •有序树：规定所有结点的儿子结点次序，否则为无序树 •森林： m >= 0 棵互不相交树的集合 其它表示方法： 1. ( A(B(L,E),C(F),D(G(I),H)) 2. 类似于书籍的目录表示法。 高度定义为层数或层数－1，都可以；本书定义为层数。 A B C D E F G H I L 高度为 4 、度为 3 的树
树和森林 ADT5.1:树的AD 数据及关系: 具有相同数据类型的数据元素或结点的有限集合。树T的二元组形式为 T=(D, R) 其中D为树T中结点的集合,R为树中结点之间关系的集合。 D=RootED 其中,Root为树T的根结点,D为树T的根Root的子树集合 R={,i=1,2, 其中,r;是树T的根结点Root的子树T的根结点。 操作 Constructor 前提:已知根结点的数据元素之值。 结果:创建一棵树。 troo 前提:已知一棵树。 结果:得到树的根结点 FirstChild 前提:已知树中的某一指定结点p 结果:得到结点p的第一个儿子结点 Nextchild 前提:已知树中的某一指定结点p和它的一个儿子结点u。 结果:得到结点p的儿子结点u的下一个兄弟结点 ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
树和森林 ADT 5.1: 树的ADT 数据及关系: 具有相同数据类型的数据元素或结点的有限集合。树T的二元组形式为： T＝（D，R） 其中D为树T中结点的集合，R为树中结点之间关系的集合。 D＝{Root}∪DF 其中，Root为树T的根结点，DF为树T的根Root的子树集合。 R＝{，i＝1，2，…，m} 其中，ri是树T的根结点Root的子树Ti的根结点。 操作: Constructor： 前提：已知根结点的数据元素之值。 结果：创建一棵树。 Getroot: 前提：已知一棵树。. 结果：得到树的根结点。 FirstChild： 前提：已知树中的某一指定结点 p。 结果：得到结点 p 的第一个儿子结点。 NextChild： 前提：已知树中的某一指定结点 p 和它的一个儿子结点 u。 结果：得到结点 p 的儿子结点 u 的下一个兄弟结点 v
二叉树的定义 空或有一个根,根有左子树、右子树;而左右子树本身又是二叉树。 和树的区别:可为空 左右子树有序,不可颠倒 例:二叉树 例:结点总数为3 时的所有二叉树的树 的形状
例：结点总数为 3 时的所有二叉树的树 的形状 二叉树的定义 空或有一个根，根有左子树、右子树；而左右子树本身又是二叉树。 和树的区别：可为空 左右子树有序，不可颠倒 B C D E F L 例： 二叉树
二叉树的性质 性质1:在二叉树的第i层上至多有2个结点 1层:结点个数211=20个 2层:结点个数221=21个 3层:结点个数231=22个 证:k=1时成立,设k=|-1时成立则当k=i时在二叉树的第i层上至多有 2111*2=2H个结点 性质2:高度为k的二叉树至多有2k1个结点 证:利用性质1,将第1层至第k层的最多的结点数进行相加: 1+2+22+……+2k-2+2k1=2k-1 性质3:二叉树的叶子结点数n0等于度为2的结点数n2+1 证:设度为1的结点数为n1,树枝的总数为B则:B=n-1=n0+n1+n21 又B=n1+2×n2;原命题得证
二叉树的性质 •性质1：在二叉树的第 i 层上至多有 2 i-1个结点 B C D E F L A 1层：结点个数 2 1-1=20 个 2层：结点个数 2 2-1=21 个 3层：结点个数 2 3-1=22 个 证：k = 1 时成立，设 k = i-1 时成立 则当 k = i 时在二叉树的第 i 层上至多有 2 i-1-1 * 2 = 2 i-1 个结点 •性质2：高度为 k 的二叉树至多有2 k - 1 个结点 证：利用性质 1 ，将第 1 层至第 k 层的最多的结点数进行相加： 1 + 2 + 22 + ………… + 2k-2 + 2k-1 = 2k - 1 •性质3：二叉树的叶子结点数 n0 等于度为 2 的结点数 n2 + 1 证：设度为 1 的结点数为 n1，树枝的总数为 B 则：B = n-1=n0+n1+n2-1 又 B = n1+2×n2； 原命题得证。 C E F L A
完全二叉树 满二叉树: 完全二叉树: 1、满二叉树 每层结点 2、从满二叉树 数最多 最底层从右向左 依次去掉若干结 点形成的 P)(a)(R)(s)(u)(v)(w 性质4:具有n个结点的完全二叉树高度为ogn」+1 证:根据性质2和完全二叉树的定义:设其高度为k 2k-1-1<n<=2k-1 k-1<n+1<=2k 2k1<=n<2 故:k-1<=log2n<k;原命题得证
完全二叉树 B C E F D L A P Q R S U B C E F D L A P Q R S U V W X •满二叉树: 每层结点 数最多 •完全二叉树: 1、满二叉树 2、从满二叉树 最底层从右向左 依次去掉若干结 点形成的 性质4：具有 n 个结点的完全二叉树高度为 log2n + 1 证：根据性质 2 和完全二叉树的定义：设其高度为 k 2 k-1 -1< n <= 2k -1 2 k-1 < n + 1 <= 2k 2 k-1 <= n < 2k 故：k-1 <= log2n < k ; 原命题得证
完全二叉树 性质5:对一棵有n个结点的完全二叉树按照从第一层(根所在的层次〕到最后一层,并且 每一层都按照从左到右的次序进行编号。根结点的编号为1,最后一个结点的编号 为n。 1:对任何一个编号为i的结点而言,它的左儿子的编号为2(若2i<=n),而右儿子的 编号为2H1(若2i+1<=n)。 2:对任何一个编号为的结点而言,它的父亲结点的的编号为j2}根结点无父结 证:对编号归纳 3 7 89101112
完全二叉树 B C E F D L A P Q R S U 性质5：对一棵有 n 个结点的完全二叉树按照从第一层（根所在的层次〕到最后一层，并且 每一层都按照从左到右的次序进行编号。根结点的编号为 1，最后一个结点的编号 为 n。 1：对任何一个编号为 i 的结点而言，它的左儿子的编号为 2i( 若 2i <= n) ,而右儿子的 编号为 2i+1(若 2i +1 <= n)。 2：对任何一个编号为 j 的结点而言，它的父亲结点的的编号为 j/2 。根结点无父结 点。 证：对编号归纳 8 9 10 11 12 4 5 6 7 3 2 1
二叉树的顺序存储 一般情况: data left right 01234567 195 G|87 14 应用范围:适用于二叉树上的结点个数已知,或不支持动态存储分配的高级语言
二叉树的顺序存储 一般情况： A B C D E F G I H L A 1 -1 B 9 2 C 5 3 D 6 -1 E -1 -1 F -1 -1 G 8 7 H -1 -1 I -1 -1 L -1 4 0 1 2 3 4 5 6 7 8 9 data left right 应用范围：适用于二叉树上的结点个数已知，或不支持动态存储分配的高级语言
二叉树的顺序存储 特殊情况:完全二叉树 data left right 234567 2468 357900 3456 000000 0000 10 应用范围:适用于完全二叉树,且结点个数已知
二叉树的顺序存储 特殊情况：完全二叉树 A 2 3 B 4 5 C 6 7 D 8 9 E 10 0 F 0 0 G 0 0 H 0 0 I 0 0 L 0 0 0 1 2 3 4 5 6 7 8 9 10 data left right 应用范围：适用于完全二叉树，且结点个数已知。 D C E F G B A H I L A B C D E F G H I 0 1 2 3 4 5 6 7 8 9 L
二叉树的顺序存储 特殊情况:若不是完全二叉树,许多数据场为空,不合算。如下例所示: 考虑浪费空间最多的情况,是一种什么情况?浪费2^k-1-k个单元 3456
二叉树的顺序存储 特殊情况：若不是完全二叉树，许多数据场为空，不合算。如下例所示： 考虑浪费空间最多的情况，是一种什么情况？ 浪费 2^k - 1 – k 个单元 A B ∧ D ∧ ∧ ∧ H I 0 1 2 3 4 5 6 7 8 9 D B A H I