1
2
3
孩子兄弟表示法(二叉链表树)
顾名思义，孩子兄弟表示法的每个节点有两个指针域，一个指向其长子，另一个指向其兄弟.
4
5
平衡二叉树（Balanced Binary Tree）是二叉查找树的一个进化体，也是第一个引入平衡概念的二叉树。1962年，G.M. Adelson-Velsky 和 E.M. Landis发明了这棵树，所以它又叫AVL树。平衡二叉树要求对于每一个节点来说，它的左右子树的高度之差不能超过1，如果插入或者删除一个节点使得高度之差大于1，就要进行节点之间的旋转，将二叉树重新维持在一个平衡状态。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。
6
7
8
9
在一棵度为3的树中,度为2的结点个数是1,度为0的结点个数是6,则度为3的结点个数是
设度为0的结点个数为n0，度为1的结点个数为n1，度为2的结点个数为n2，度为3的个数n3
树中结点总数n0+ n1 + n2 + n3，所有边的数量为0 * n0 + 1 * n1 + 2 * n2 + 3 * n3
树中结点比边多1个，合并这两个式子就可以得到：n0 = 1 + n2 + 2 * n3
代入数据可以得到n3 = 2，度为3的结点个数是2
10
11
12
13
14
15
16
二叉查找树是一种查找效率非常高的数据结构，它有三个特点。
- 每个节点最多只有两个子树。
- 左子树都为小于父节点的值，右子树都为大于父节点的值。
- 在n个节点中找到目标值，一般只需要log(n)次比较。
B树的特点也有三个。
- 一个节点可以容纳多个值。比如上图中，最多的一个节点容纳了4个值。
- 除非数据已经填满，否则不会增加新的层。也就是说，B树追求"层"越少越好。
- 子节点中的值，与父节点中的值，有严格的大小对应关系。一般来说，如果父节点有a个值，那么就有a+1个子节点。比如上图中，父节点有两个值（7和16），就对应三个子节点，第一个子节点都是小于7的值，最后一个子节点都是大于16的值，中间的子节点就是7和16之间的值。
17
18
19
