数据结构速查

树的性质

1. 树中的结点数等于所有结点的度数之和加1。
2. 度为 $m$ 的树中第 $i$ 层上至多有 $m^{i-1}$ 个结点（$i≥1$）。
3. 高度为 $h$ 的 $m$ 叉树至多有 $(m^h-1)/(m-1)$ 个结点。
4. 具有 $n$ 个结点的 $m$ 叉树的最小高度为 $\lceil\log_m(n(m-1)+1)\rceil$。
5. 常用于求解树结点与度之间关系的有：
   • 总结点数=$n_0+n_1+n_2+\cdots+n_m$
   • 总分支数=$1n_1+2n_2+\cdots+mn_m$(度为 $m$ 的结点引出 $m$ 条分支)
   • $总结点数=总分支数+1$

二叉树的性质

1. 非空二叉树上的叶子结点数等于度为 $2$ 的结点数加 $1$，即$n_0=n_2+1$。
2. 非空二叉树上第 $k$ 层上至多有 $2^{k-1}$ 个结点（$k≥1$）。
3. 高度为 $h$ 的二叉树至多有 $2^h-1$ 个结点（$h≥1$）。
4. 对完全二叉树按从上到下、从左到右的顺序依次编号 $1，2，\cdots，n$，则有以下关系：
   1. 当 $i＞1$ 时，结点 $i$ 的双亲的编号为 $\lfloor i/2\rfloor$，即当 $i$ 为偶数时，其双亲的编号为 $i/2$，它是双亲的左孩子；当 $i$ 为奇数时，其双亲的编号为 $(i-1)/2$，它是双亲的右孩子。
   2. 当 $2i≤n$ 时，结点 $i$ 的左孩子编号为 $2i$，否则无左孩子。
   3. 当 $2i+1≤n$ 时，结点 $i$ 的右孩子编号为 $2i+1$，否则无右孩子。
   4. 结点 $i$ 所在层次（深度）为 $\lfloor\log_2i\rfloor+1$。
5. 具有 $n$ 个（$n＞0$）结点的完全二叉树的高度为 $\lceil\log_2(n+1)\rceil$ 或 $\lfloor\log_2n\rfloor+1$。