6.5、树与森林的遍历 6.5.1、树的遍历
由树结构的定义可引出两种次序遍历树的方法：一种是先根（次序）遍历树，即：先访问树的根结点，然后依次先根遍历根的每棵子树；另一种是后根（次序）遍历，即先依次后根遍历每棵子树，然后访问根结点。
例如，对图 38 所示的树进行先根遍历，可得树的先根序列为：
R A D E B C F G H K
对该树进行后根遍历，则得树的后根序列为：
D E A B G H K F C R
按照森林和树相互递归的定义，可以推出森林的两种遍历方法：先序遍历和中序遍历。
6.5.2、森林的遍历
森林的遍历有两种方式： 前序遍历和中序遍历。
前序遍历
前序遍历的过程：
(1) 访问森林中第一棵树的根结点；
(2) 前序遍历第一棵树的根结点的子树森林；
(3) 前序遍历剩余的其他子森林。
对于图 46 所示的森林进行前序遍历， 得到的结果序列为 A B C D E F G H I J K。
中序遍历
中序遍历的过程：
(1) 中序遍历第一棵树的根结点的子树森林；
(2) 访问森林中第一棵树的根结点；
(3) 中序遍历剩余的其他子森林。
对于图 46 所示的森林进行中序遍历， 得到的结果序列为 B A D E F C J H K I G 。
根据森林与二叉树的转换关系以及森林和二叉树的遍历定义可以推论： 森林前序遍历和中序遍历分别与所转换的二叉树的前序遍历和中序遍历的结果序列相同。
7、B树
在前面学习了平衡二叉树，B树也是一种平衡查找树，不过不是二叉树。
B树也称B-树，它是一种多路平衡查找树。
一棵m阶的B树定义如下：
每个节点最多有m-1个关键字（可以存有的键值对）。
根节点最少可以只有1个关键字。
* 非根节点至少有m/2个关键字。
每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都相同。
每个节点都存有索引和数据，也就是对应的key和value。
看一个B树的实例（字母大小 C>B>A）
看看B树的一些基本操作。
7.1、查找
查找和平衡二叉树类似，不过B树是多路的而已。以图47中查找15为例：
（1）获取根节点的关键字进行比较，当前根节点关键字为39，15<39，所以往找到指向左边的子节点（二分法规则，左小右大，左边放小于当前节点值的子节点、右边放大于当前节点值的子节点）；
（2） 获取到关键字12、22, 12<15<22，所以查找12和22中间的节点
（3）获取到关键字13和15，因为15=15，所以返回关键字和指针信息；如果没有找到所包含的节点，返回null。
7.2、插入
插入的时候，需要记住一个规则：判断当前结点key的个数是否小于等于m-1，如果满足，直接插入即可，如果不满足，将节点的中间的key将这个节点分为左右两部分，中间的节点放到父节点中即可。
例子：在5阶B树中，结点最多有4个key,最少有2个key（注意：下面的节点统一用一个节点表示key和value）。
插入18，70，50,40
插入22
插入22时，发现这个节点的关键字已经大于4了，所以需要进行分裂，分裂的规则在上面已经讲了，分裂之后，如下。
接着插入23，25，39
分裂，得到下面的。
7.3、删除
B树的删除操作相对于插入操作是相对复杂一些。
树初始状态如下
删除15，这种情况是删除叶子节点的元素，如果删除之后，节点数还是大于m/2，这种情况只要直接删除即可。