二叉树的几个重要性质
所属分类 DS
浏览量 785
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实现 关键术语
关于数学的名言
冒泡选择和插入排序比较
金庸小说人物英文名