树

树结构中的每个节点有其父节点和子节点:

对于树的遍历，一般有三种，先序遍历，中序遍历和后序遍历：

• 先序遍历：这里以二叉树为例，每个树有其根节点，以此可以划分为左子树和右子树，先序遍历的顺序就是根左右，上面的二叉树的先序遍历顺序就是：ABDECFG。
• 中序遍历：顺序是左根右，DBEAFCG。
• 后序遍历：顺序是左右根，DEBFGCA。

二叉树就是每个节点的子节点不能多于两个，上面的树结构图就是一个二叉树。而二叉查找树是一种特殊的二叉树，即一个节点和两个子树上所有关键值的关系是左子树节点<该节点<右子树节点，比如：

AVL树是带有平衡条件的二叉查找树，它的每个节点的左子树和右子树的高度最多差1。向AVL树插入节点会破坏原有平衡，可以通过旋转操作修正。可以分为两种情况：

• 插入节点在“外边”，即左-左或右-右，这样进行单旋转即可。
• 插入节点在“内部”，即左-右或右-左，这样要通过双旋转完成。

单旋转的一个例子：

上面的树插入节点6会破坏节点8的平衡，则在节点7和8之间旋转一次，得到：

双旋转有两种，右左和左右双旋转。比如：

插入节点5，节点6不平衡，且节点5关键值位于2和6之间，不符合查找树条件，首先绕4左旋转，得：

然后绕4右旋转，让4作为根节点，得：

B树也是一种常用的查找树，比如M阶：

• 树的根或者是一片树叶，或者其子节点数在2和M之间
• 除根外，所有非树叶节点的子节点数在M/2和M之间
• 所有的树叶都在相同的深度上

所有的数据都存储在树叶上，在每一个内部节点上皆含有指向该节点各子节点的指针P1、P2、...、PM和分别代表在字数中法线的最小关键字的值k1、k2、...、kM，对于每一个节点，其子树P1中所有关键字小于子树P2上的关键字，以此类推。比如一个3阶B树，也可称为2-3树：

用椭圆表示非树叶节点，每个节点有两个数据，短横线表示该节点只有两个子节点。树叶用方框画出，框内有关键字，树叶中的关键字是有序的