第六章树和三叉树 性质4具有n个结点的满二叉树或完全二叉树的深度为log2n+1 [证]对于满二叉树,n=2k1,或n+1=2,得K=92+ 由于k是整数.故nn+1 对于完全/符号含义 Lx」表示不大于x的最大整数 其中2k1- 「x|表示不小于x的最小整数 人。于是 例如:5.8 或有L5.8」=5 6 由于k是 ⑦ 示例如右图,对于n=8,9,10;…,14的 完全二叉树,以及n=15的满二叉树,均有 k=Log2n+1=3+1=4. 第26页
第六章 树和二叉树 第26页 [证] 对于满二叉树，n=2k -1，或n+1=2k，得k=log2 (n+1). 由于k是整数，故log2n+1 对于完全二叉树，根据性质2和完全二叉树的定义知 2 k-1 -1<n≤2k -1 其中2 k-1 -1与2 k -1分别表示深度为k-1与k的最大结点数。于是 2 k-1 ≤ n<2k 或有 k-1≤log2n<k 由于k是整数，故 k= log2n+1 示例 如右图，对于n=8,9,10,···,14的 完全二叉树，以及n=15的满二叉树，均有 k= log2n+1 =3+1=4. 1 2 3 4 5 8 9 10 11 6 7 12 性质4 具有n个结点的满二叉树或完全二叉树的深度为log2n+1. 符号含义： x 表示不大于x的最大整数。 表示不小于x的最小整数。 例如：5.8 5.8 = 5 = 6 x 5.8
二又树的性质 第六章树和三叉树 性质5如果对二棵有η个结点的完全二叉树(其 深度为logn+1)的结点按层序编号(从第1层到第 Log2nH+1层,每层从左到右),则对任一结点(1≤ 一n),有 (1)如果j1,则结点是二叉树的根,无双亲 如果i1,则其双亲 Parent()是Li2」 (2)如果2+2n。则结点无左孩子(结点为叶子 结点);如果2≤n,则其左孩子LChd(是结点2i (3)如果2计+1>n,则结点话无右孩子(但怀一定 是叶结点);如果2+15n,则其右孩子RCh①是 结点2+1 第27页
第六章 树和二叉树 第27页 性质5 如果对一棵有n个结点的完全二叉树（其 深度为 log2n+1 ）的结点按层序编号（从第1层到第 log2n+1层，每层从左到右），则对任一结点 i(1 ≤ i≤n)，有 (1) 如果 i=1，则结点i是二叉树的根，无双亲； 如果 i>1，则其双亲Parent(i)是 i/2 (2) 如果 2 *i>n。则结点i无左孩子（结点i为叶子 结点）；如果 2i ≤n，则其左孩子LChild(i)是结点2i; (3) 如果 2i+1>n，则结点i无右孩子（但i不一定 是叶结点）；如果 2i+1 ≤n，则其右孩子RChild(i)是 结点2i+1。 ⚫ 二叉树的性质
又树的性质 第六章树和三叉树 证]用归纳法证明(2),(3),由(2)3)再导出(1) 记j为层次 1:按完全二叉树定义,其左、右孩子应为结点2,3。 若21>n,则无左孩子 若21+1>n,则无右孩子。 设时结论成立,即有左孩子为结点2(2≤n),右孩子为结 点2+1(2+1≤η),现欲证j=计1时结论亦成立,即有左孩子为结 点2(+1)(2(+1)≌n) 根据完全二叉树的特点,与结点+1的左孩子相邻的前两个 一结点分别是结点的左、右孩子。由归纳法假定,j左孩子是2i ,右孩子是2+1,因此,计+1的左孩子应为21+1=2(+1),如 2(+1)>n,则说明计1无左孩子;而计+1的右孩子为 2+1+3=2(+1)+1(2(+1)+1sn)因此=1时(2),(3)成立 对任一结点(s≤n),除=1即结点外,若=偶数,则必是 左孩子,其双亲是i2=Li2」;若奇数,则必是右孩子,其双 亲是12=Li2」故(1)成立。 第28页
第六章 树和二叉树 第28页 [证] 用归纳法证明(2)，(3)，由(2),(3)再导出(1). 记j为层次。 j=1：按完全二叉树定义，其左、右孩子应为结点2，3。 若2·1>n，则无左孩子； 若2·1+1>n，则无右孩子。 设j=i时结论成立，即有左孩子为结点2i(2i≤n)，右孩子为结 点2i+1(2i+1 ≤n). 现欲证j=i+1时结论亦成立，即有左孩子为结 点2(i+1) (2(i+1) ≤n). 根据完全二叉树的特点，与结点i+1的左孩子相邻的前两个 结点分别是结点i的左、右孩子。由归纳法假定，i的左孩子是2i ，右孩子是2i+1，因此，i+1的左孩子应为2i+1+1=2(i+1)，如 2(i+1)>n，则说明i+1无左孩子；而i+1的右孩子为 2i+1+3=2(i+1)+1 (2(i+1)+1 ≤n). 因此j=i+1时(2)，(3)成立。 对任一结点i(i ≤i ≤n)，除i=1即结点外，若i=偶数，则必是 左孩子，其双亲是i/2= i/2 ；若i=奇数，则必是右孩子，其双 亲是i-i/2= i/2 . 故(1)成立。 ⚫ 二叉树的性质
下图展开了完全二叉树中结点和计+1与其左、右孩军之树和二又 间的关系 2]) (2+1 2i+3 LChild( Rchild( LChild(i+ 1) RChild(i+1) 结点和+1在同一层次(必为偶数) 2 LChild( Childe 2+2)(2+3)Rchd(+1) LChild(i+ 1) 结点+1不在同一层次(结点必在上一层最后,+1必为 此层最左;i必为奇数) 第29页
第六章 树和二叉树 第29页 下图展开了完全二叉树中结点i和i+1与其左、右孩子之 间的关系 LChild(i) RChild(i) LChild(i+1) RChild(i+1) 结点i和i+1在同一层次（i必为偶数） [i/2] i i+1 2i 2i+1 2i+2 2i+3 结点i和i+1不在同一层次（结点i必在上一层最后，i+1必为 此层最左；i必为奇数） i 2i 2i+1 LChild(i) RChild(i) i+1 2i+2 2i+3 LChild(i+1) RChild(i+1)
二又树的存信结构 第六章树和三叉树 叉树的顺序存储结构 可使用一组连续的存储单元(向量,即一维数组)来存储 叉树的数据元素。必须把二叉树中的所有结点安排成一个 适当的线性序列,使得结点在这个序列中的相互位置能够反 映出结点之间的逻辑关系。 示例 3 5 6 8(9(1011(12 bt(1:12) 1234567|89101112 2i2+1 第30页
第六章 树和二叉树 第30页 二叉树的顺序存储结构 可使用一组连续的存储单元(向量，即一维数组)来存储 二叉树的数据元素。必须把二叉树中的所有结点安排成一个 适当的线性序列，使得结点在这个序列中的相互位置能够反 映出结点之间的逻辑关系。 示例 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 2 i ↑ i ↑ 2i ↑ 2i+1 bt(1:12) ⚫ 二叉树的存储结构