二叉树的性质 性质1若二叉树的层次从0开始,则在二叉 树的第i层最多有2个结点。(≥0) i证明用数学归纳法] 性质2高度为h的二叉树最多有2+1-1个 结点。(≥-1) i证明用求等比级数前项和的公式] 20+21+22+….+2h=2h+1-1
性质1 若二叉树的层次从0开始, 则在二叉 树的第 i 层最多有 2 i 个结点。(i 0) [证明用数学归纳法] 性质2 高度为 h 的二叉树最多有 2 h+1-1个 结点。(h -1) [证明用求等比级数前k项和的公式] 2 0 + 21 + 22 + … + 2h = 2h+1-1 二叉树的性质
性质3对任何一棵二叉树,如果其叶结点 有n0个,度为2的非叶结点有m2个,则有 =n2+1 证明:若设度为1的结点有n1个,总结点 个数为n,总边数为e,则根据二叉树的 定义, n=n0+n1+n2e=2n2+n1=n-1 因此,有2n2+n1=+m1+n2-1 0 n=n+1 0
性质3 对任何一棵二叉树, 如果其叶结点 有 n0 个, 度为2的非叶结点有 n2 个, 则有 n0＝n2＋1 证明：若设度为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完全二叉树( omplete Binary tree 若设二叉树的高度为h,则共有h+1层。除 第h层外,其它各层(0~h-1)的结点数都 达到最大个数,第h层从右向左连续缺若干 结点,这就是完全二叉树
定义1 满二叉树 (Full Binary Tree) 定义2 完全二叉树 (Complete Binary Tree) 若设二叉树的高度为h，则共有h+1层。除 第 h 层外，其它各层 (0 h-1) 的结点数都 达到最大个数，第 h 层从右向左连续缺若干 结点，这就是完全二叉树
性质4具有n(≥0)个结点的完全二叉树 的高度为「og2(n+1)1-1 证明:设完全二叉树的高度为h,则有 2h-1<n≤2h+1-1 上面h层结点数包括第h层的最大结点数 变形2h<n+1≤2h+1 取对数h<log2n+1)sh+1 因此有「og2(n+1)1=h+1 h=「log2n+1)1-1
性质4 具有 n (n 0) 个结点的完全二叉树 的高度为 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 因此有 log2 (n+1) = h+1 h = log2 (n+1) -1 上面h层结点数 包括第h层的最大结点数
性质5如将一棵有n个结点的完全二叉树自 顶向下,同一层自左向右连续给结点编号0, 1,2,…,n-1,则有以下关系: 若i=0,则i无双亲 若i>0,则i的双亲为(-1)2」 若2*计1<n,则i的左子女为2计1,若 2*计+2<n,则i的右子女为2*计2 若i为偶数,且=0, 则其左兄弟为i-1,若 i为奇数,且i!=n-1, 则其右兄弟为计1680
性质5 如将一棵有n个结点的完全二叉树自 顶向下，同一层自左向右连续给结点编号0, 1, 2, …, 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 0 1 2 3 7 4 5 6 8 9