数据结构之——树

一、树

1、深度为n的满m叉数的第k层有 m^(k-1) 个结点（1≤k≤h）

　　解析：树的根节点为1，满M叉树，第n层节点树肯定是前一层节点的m倍

　　　　第1层： 1 　　　　    　　m^0 　

　　　　第2层： 1*m 　　　　　　m^1

　　　　第3层： 1*m*m　　    　　m^2

　　　　 . . . 　　　　　　　　　　. . .

　　　　第k层： 1*m^(k-1) 　　　  m^(k-1)

2、 二叉树有一个性质：n0=n2+1   (n0是指度为0的节点，n2是指度为2的节点）

　　若二叉树有67个结点，那么，要么度为0（m），要么度为2（n），则有 m+n = 67，  m=n+1，2n+1 = 67， 则有 n=33 ，m=34。所以度为2的节点有33个，度为0的节点有34个。

3、使用一个长度最大为150的队列，对满二叉树进行广度优先遍历时，能容纳的二叉树最大深度为  2^(n-1)  。

4、一棵左右子树不空的二叉树，前序和后序先说好空指针域都是1，中序是2。

5、求图的最小生成树算法：

　　①Prim算法：适合稠密图，贪心算法的运用，时间复杂度O（n+e），邻接表存储；O(n^2)

　　②Kruskal算法：适合稠密图，贪心算法的运用，时间复杂度O（eloge），e为边数。

6、平衡因子=左子树高度-右子树高度，有四种情况可能导致二叉查找树不平衡，分别为：

　　①LL：插入一个新节点到根节点的左子树（Left）的左子树（Left），导致根节点的平衡因子由1变为2。

　　②RR：插入一个新节点到根节点的右子树（Right）的右子树（Right），导致根节点的平衡因子由-1变为-2。

　　③LR：插入一个新节点到根节点的左子树（Left）的右子树（Right），导致根节点的平衡因子由1变为2。

　　④RL：插入一个新节点到根节点的右子树（Right）的左子树（Left），导致根节点的平衡因子由-1变为-2。

　　针对四种情况可能导致的不平衡，可以通过旋转使之变平衡，有两种基本的旋转：

　　①左旋转：将根节点旋转到（根节点的）右子树的右子树的位置

　　②右旋转：将根节点旋转到（根节点的）左子树的左子树的位置