树
- m阶B-树的所有叶子都在==同一==层次上。
- 最优二叉树：哈夫曼树。
-
Kruskal算法是==按权值选边==，若选边后不形成回路,则保留作为一条边,若形成回路则除去。 Prim算法是每次==从当前的二叉树节点向外延伸==的，选择权值最小的边。
- 分支节点是度不为0的节点。设树高h,因为是满二叉树，所以叶子节点有2^(h-1)个。
有n(n>0)个分支结点的满二叉树的深度：==h=log2(n+1)+1==。 - 二叉链表作为树的存储结构时，链表中结点的两个链域分别指向==该结点的第一个孩子结点==和==第一个孩子下一个兄弟结点==。
- 不同的求最小生成树的方法最后得到的生成树不唯一，但最小生成树上权值之和相等。
- 设度为0的结点数为n0，度为1的结点数为n1，度为2的结点数为n2，二叉树的总结点为n，
则 ==n0 + n1 + n2 = n==（1）
对任意数，分支数b=n-1，对二叉树来说，所有的分支是由度为1和2的结点出发的，故b=n1+2*n2
则 ==2 × n2 + 1 × n1+1 = n==（2）
==n0 = n2 + 1== - K层总共最多是：2^k -1 满二叉树. 第K层最多是：2^(k-1) 第k层是满的。
- 完全二叉树叶子节点：==n0＝（n＋1）/2==。
完全二叉树的深度公式：==↓log(2 N)↓+1==，注意是以2为底向下取整的整数再加1。 - 采用二叉链表作为存储结构,==树的前序遍历和其相应的二叉树的前序遍历==的结果是一样，==树的后序遍历和其相应的二叉树的中序遍历==一致。
- B树 是一种==多路搜索树==（并不是二叉的）：
- 定义任意非叶子结点最多只有 M 个儿子；且 M>2 ；
- 根结点的儿子数为 [2, M] ；
- 除根结点以外的非叶子结点的儿子数为 [M/2, M] ；
- 每个结点存放至少 M/2-1 （取上整）和至多 M-1 个关键字；（至少 2 个关键字）
- 非叶子结点的关键字个数 = 指向儿子的指针个数 -1 ；
- 非叶子结点的关键字： K[1], K[2], …, K[M-1] ；且 K[i] < K[i+1] ；
- 非叶子结点的指针： P[1], P[2], …, P[M] ；其中 P[1] 指向关键字小于 K[1] 的子树， P[M] 指向关键字大于 K[M-1] 的子树，其它 P[i] 指向关键字属于 (K[i-1], K[i]) 的子树；
- 所有叶子结点位于同一层；
