树与二叉树

树的结点个数与结点的度与树的高度

树

$$ N = n_{0} + n_{1} + n_{2} + n_{3} + ...... + n_{n} $$ $$ N = 0 \times n_{0} + 1 \times n_{1} + 2 \times n_{2} + 3 \times n_{3} ...... + n \times n_{n} + 1 $$ 高为h的树至多有 $ \frac{m^h-1}{m - 1} $ 个节点
度为m的树在第i层上至多有 $ m^{i-1} $ 个节点
具有n个节点m叉树最小高度为$ log_{m}[n(m-1)+1] $

二叉树

$$ N = n_{0} + n_{1} + n_{2} $$ $$ N = n_{1} + 2 \times n_{2} + 1 $$ $$ n_{0} = n_{2} + 1 $$ 非空 k 叉树上的第 k 层至多$ 2^{k-1} $ 个节点.
高为 h 的二叉树至多有 $ 2^h - 1 $ 个节点.

特殊树

完全二叉树

$$ h = log_{2}(n + 1) = log_{2}(n) + 1 $$ 当 i > 1 时，i 节点的双亲的 $ index = \left\{\begin{matrix} & i / 2 偶\\ & (i -1)/2 奇 \end{matrix}\right. $

线索二叉树

对于 n 个节点的线索二叉树，空指针个数有 n + 1 个。

高度为 h 只有度为 0 和 2 的结点

总结点至少为 $ 2h-1 $

二叉平衡树

$$ n_{h} = n_{h - 1} + n_{n - 2} + 1 $$ 平衡因子是 $ 左右子树的高度之差。 $