二叉树的性质
性质1:对于任何一棵二叉树T,其度为2的节点数加一等于度为0的叶子节点数
n 0 = n 2 + 1 n_0=n_2+1 n0?=n2?+1
其中: n 0 n_0 n0?表示度为0的节点数,也即叶子节点 n 2 n_2 n2?表示度为2的节点数
性质2:深度为k的二叉树最多有 2 k ? 1 2^k-1 2k?1个节点,最少有 k k k个节点
k ≤ n ≤ 2 k ? 1 k\le n \le 2^k -1 k≤n≤2k?1
性质3:二叉树的第 k k k层最多有 2 k ? 1 2^{k-1} 2k?1个节点,最少有1个节点
1 ≤ n k 层 ≤ 2 k ? 1 1\le n_{k层} \le 2^{k -1} 1≤nk层?≤2k?1
性质4:具有n个节点的完全二叉树的深度 k = ? l o g 2 n ? + 1 k = \lfloor log_2n \rfloor + 1 k=?log2?n?+1
性质5:如果一个有 n n n个节点的完全二叉树,对其进行编号:从左至右,从上到下,记节点编号为i,则:
- 该树共有 ? l o g 2 n ? + 1 \lfloor log_2n \rfloor + 1 ?log2?n?+1层
- 如果 i = 1 i= 1 i=1,则节点 i i i是二叉树的根,无双亲; 如果 i > 1 i > 1 i>1,则其双亲节点编号为 ? i / 2 ? \lfloor i/2 \rfloor ?i/2?
- 如果 2 i > n 2i > n 2i>n,则节点 i i i为叶节点,无左孩子,否则其左孩子编号为 2 i 2i 2i
- 如果 2 i + 1 > n 2i + 1 > n 2i+1>n,则节点 i i i无右孩子,否则右孩子编号为 2 i + 1 2i+1 2i+1
- 对于一个拥有左右孩子的节点 i i i,其左孩子编号为 2 i 2i 2i,右孩子编号为 2 i + 1 2i+1 2i+1