数据结构公式总结.md

数据结构公式总结

树

1. 树中的结点数 = 所有结点的度数之和 + 1 = 总分支数 + 1

   二叉树中 $n_0 + n_1 + n_2 = n_1+2*n_2+1$ —> $n_0 = n_2+1$

   ​ $ n = 2*n_0 + n_1 -1$

2. 度为m的树中第i层至多有 $m^{i-1}$

3. 具有n个结点的m叉树的最小高度： $\lceil$$log_m (n*(m-1)+1)$$\rceil$

4. n个结点的二叉链中，含有n+1个空链域（线索二叉树的时候很有用的结论）