树

以二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和第一个孩子下一个兄弟结点。所以根节点的右指针指向根节点的右兄弟，跟节点没有兄弟节点，因此为空。

---

线索二叉链表/线索化二叉树：

左孩子域/ltag = 0：lchild指向结点的左孩子

左孩子域/ltag = 1：lchild指向结点的前驱结点

右孩子域/rtag = 0：rchild指向结点的右孩子

右孩子域/rtag = 1：rchild指向结点的后驱结点

---

完全二叉树的深度公式：[log(2 N)]+1，注意是以2为底向下取整的整数再加1

---

B-是多路搜索树，是多叉树

B+是B-变体，与B-基本相同，区别是B+只有到达叶子节点才命中

AVL本质上还是二叉树

B+、B-都和搜索有关

B+树可以为空

B树 即二叉搜索树：

 1.所有非叶子结点至多拥有两个儿子（Left和Right）；

 2.所有结点存储一个关键字；

3.非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；

---

具有 60 个结点的二叉树，其叶子结点有 12 个，则度为1 的结点数为（ ）

叶子结点 n0 = 12;

由二叉树的性质可得 度为2的结点 n2 = n0 - 1;

二叉树结点 n = 60, 则度为1的结点 n1 = n - n0 - n2 = 37.

---

设一棵完全二叉树中有65个结点，则该完全二叉树的深度为(  7   )。

---

完全二叉树结点个数，根据公式 节点为n时，左孩子节点为2n，右孩子节点为2n+1。