二叉树( Binary Tree 二叉树的完义 一棵二叉树是结点的一个有限集合,该 集合或者为空,或者是由一个根结点加上两 棵分别称为左子树和右子树的、互不相交的 二叉树组成。 (a)(b) R (e) 二叉树的五种不同形
二叉树 (Binary Tree) 二叉树的定义 二叉树的五种不同形态 一棵二叉树是结点的一个有限集合，该 集合或者为空，或者是由一个根结点加上两 棵分别称为左子树和右子树的、互不相交的 二叉树组成
二叉树的性质 性质1若二叉树的层次从0开始,则在二叉树的 第i层最多有2个结点。(i≥0) i证明用数学归纳法 性质2高度为k的二叉树最多有24+1-1个结点。 (k≥-1) 证明用求等比级数前k项和的公式 性质3对任何一棵二叉树,如果其叶结点个数为 np度为2的非叶结点个数为m2,则有 noEn+1
性质1 若二叉树的层次从0开始, 则在二叉树的 第 i 层最多有 2 i 个结点。(i 0) [证明用数学归纳法] 性质2 高度为k的二叉树最多有 2 k+1 -1个结点。 (k -1) [证明用求等比级数前k项和的公式] 性质3 对任何一棵二叉树, 如果其叶结点个数为 n0 , 度为2的非叶结点个数为n2 , 则有 n0＝n2＋1 二叉树的性质
证明:若设度为1的结点有n1个,总结点个 数为n,总边数为e,则根据二叉树的定义, n=n0+n1+n2e=2m2+n1=n- 因此,有2m2+n1=n+n1+n2-1 2 0 0-2 +1 当当当当当当当当当当当当当当当当当当当当当当当巨当当当当巨当 定义1满二叉树( Full Binary tree 定义2完全二叉树( omplete Binary Tree) 若设二叉树的高度为h,则共有h+1层。除第h 层外,其它各层(0~h-1)的结点数都达到最大个数 第h层从右向左连续缺若干结点,这就是完全二 叉树
证明：若设度为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 定义1 满二叉树(Full Binary Tree) 定义2 完全二叉树(Complete Binary Tree) 若设二叉树的高度为h，则共有h+1层。除第h 层外，其它各层(0h-1)的结点数都达到最大个数， 第h层从右向左连续缺若干结点，这就是完全二 叉树
(8)(9 0203 (a)满二叉树 (b)完全二叉树 性质4具有n个结点的完全二叉树的高度为 log(n+1)|-1 证明:设完全二叉树的高度为则有 2h-1<n≤2h+1-12h<n+1≤2h+1 取对数h<log2(n+1)≤h+1
性质4 具有n个结点的完全二叉树的高度为 log2 (n+1) -1 证明：设完全二叉树的高度为h，则有 2 h - 1 < n 2 h+1 - 1 2 h < n+1 2 h+1 取对数 h < log2 (n+1) h+1
性质5如果将一棵有n个结点的完全二叉树自顶 向下,同一层自左向右连续给结点编号0,1,2, n-1,然后按此结点编号将树中各结点顺序地存 放于一个一维数组中,并简称编号为结点为结 点i(0≤i≤n-1。则有以下关系 若i==0,则i无双亲 若i>0,则i的双亲为(-1)2」 若2*计1<n,则i的左子女为2*计1 若2*计2<n,则i的右子女为2*计2 若i为偶数,且i!=0,则其左兄弟为i1 若i为奇数,且i!=n-1,则其右兄弟为i1 i所在层次为Log2(计+1)
性质5 如果将一棵有n个结点的完全二叉树自顶 向下，同一层自左向右连续给结点编号0, 1, 2, …, n-1，然后按此结点编号将树中各结点顺序地存 放于一个一维数组中, 并简称编号为i的结点为结 点i (0 i n-1。则有以下关系： ◼ 若i == 0, 则 i 无双亲 若i > 0, 则 i 的双亲为(i -1)/2 ◼ 若2*i+1 < n, 则 i 的左子女为2*i+1 若2*i+2 < n, 则 i 的右子女为2*i+2 ◼ 若 i 为偶数, 且i != 0, 则其左兄弟为i-1 若 i 为奇数, 且i != n-1, 则其右兄弟为i+1 ◼ i 所在层次为 log2 (i+1)