首页  

二叉树的几个重要性质     所属分类 DS 浏览量 795
h  高度
n  结点数
n0 度为零的结点数 (叶子结点数)
n1 度为1的结点数
n2 度为2的结点数
e  边数

1. 第 i 层最多有 2^(i-1)个结点 (i>=1)
2. 高度为h(h>=0)的二叉树最少有h个结点,最多有2^h - 1 个结点 
   2^0 + 2^1 + ... + 2^(h-1) = 2^h - 1

3. 具有n个结点的二叉树的深度至少为 log(n+1)
   根据性质2
   h <= n <= 2^h -1
   2^h >= n+1
   h >= log(n+1)

4. 对于非空二叉树,若其叶结点数为n0,度为2的非叶结点数为n2,则n0 = n2 +1
   度为2的结点 有两条边 度为1的结点 有一条边 
   
   n = n0 + n1 + n2   (公式1)
   e = n - 1          (公式2)
   e = 2*n2 + n1      (公式3)
   n = 2*n2 + n1 + 1  (公式4)
   公式4 - 公式1
   n2 + 1 - n0 = 0
   n0 = n2 + 1
   
   0度结点没有孩子,1度结点有一个孩子,2度结点有两个孩子,根不是任何结点的孩子 ,因此
   n=n1+2n2+1
   
       

5. n个结点的完全二叉树的结点按层序编号(从上到下,从左到右),对任一结点i(1<=i<=n)
   根节点编号 1 
   结点i 左孩子为 2i   (如果有的话 n >= 2i)
   结点i 右孩子为 2i+1 (如果有的话 n >= 2i + i )
   
1
2 3
4 5 6 7

上一篇     下一篇
程序数据结构与算法

Java switch tableswitch lookupswitch

算法精粹 经典计算机科学问题的Python实现 关键术语

关于数学的名言

冒泡选择和插入排序比较

金庸小说人物英文名