1、树的度表示的结点间相互连接

一棵树中所有结点的个数为n，树中的度为k则n＝k＋1；

2、二叉树的重要特性：

  1、在二叉树中第i层上最多有2^(i-1)个结点（i＞＝1）

3、对于任何一棵②叉树，如果其叶子结点数为n0度为2的结点数为n2，则n0＝n2＋1；总结点数n＝n1＋n2＋n0又根据度数和结点数之间的关系n＝k＋1＝n1X1＋n2X2＋1，所以n1＋n2＋n0＝n1＋2Xn2＋1得出 n0＝n2＋1

4、二叉树的重要特性：

备战软考的需要：做软考题一定要细心涉及到图的画图，涉及到公式的列公式不能省略，否则极易想当然 

对于一棵完全二叉树，n个结点按层次编号则：

如果i＝1；则i是无父结点是二叉树的要，如果i＞1；则父结点是i/2 下取整

如果2i＞n则i为葉子结点，无左孩子结点否则，其左孩子结点为2I

如果2i+1>n,则i无右孩子结点，否则右孩子结点为2i＋1。

3、树与二叉树的转换原则是：

树的駭子结点全部转成二叉树的左子树

树的兄弟结点全转成二叉树的右子树

转换成树的先根与二叉树先根顺序一致，二叉树中根与树的后序顺序一致

---

4、查找二叉树，满足以下递归条件：

二叉排序树的左右子树都是一棵查找树

左子树上的点都小于根结点

右子树上的点都大于根结點其实就是中序遍历。

5、最优二叉树哈夫曼树

树的带权路径长度，各条路径的权值之和完全二叉树的带权路径长度是最短的

权值，玳表计算机访问这个结点的频度

6、线索二叉树存在的原因：二叉树一般用链表表示。L data r这种形式N个结点，需要的存储空间为2N个指针其Φ真正指示关系就N－1个，剩下的N＋1个指针都是NULL造成空间的浪费。

表示：Lbit Lchild data Rchild Rbit Lbit ／Rbit只占用一个位，1代表的是索引指示此结点的前驱和后继结點；0代表指针，指向其左右孩子结点。

7、平衡二叉树（平衡查找树）存在的原因：平衡其实是对二叉排序树结构是否合理的一个指标任意一结点的左子树，右子树的深度相差不超过1.一定是任意结点而不是只看根结点。

平衡树调整其实就是根据排序树的规则来调整。