1.前言
2.树的遍历
3.B-树
4.总结
1前言对于二叉树，有深度遍历和广度遍历，深度遍历有前序、中序以及后序三种遍历方法，广度遍历即我们寻常所说的层次遍历。
与2-路树或二叉树不同，B-树是平衡M-路树，它能很好的匹配磁盘；其特殊情形是2-3树，它是实现平衡查找树的另一种常用方法。
2树的遍历由于二叉查找树中对信息进行了排序，因而按照排序的顺序列出所有关键字会很简单。
//按顺序打印二叉查找树的例程voidPrintTree(SearchTreeT){if(T!=NULL){PrintTree(T-Left);PrintElement(T-Element);PrintTree(T-Right);}}
上面的递归过程称为中序遍历。首先遍历左子树，然后当前的节点，最后遍历右子树。类似的还有先序遍历和后序遍历。
后序遍历需要先处理两个子树才能处理当前节点。
先序遍历需要当前节点在其儿子节点之前处理。
所有的实现都有一个共有的想法，那就是先处理NULL的情形，然后才是其余的工作。
第四种遍历用的很少，叫做层序遍历，在层序遍历中，所有深度为D的节点要在深度D+1的节点之前进行处理。层序遍历与其他类型的遍历不同的地方在于它不是递归地实施的；它用到队列，而不使用递归所默认的栈。
3B-树虽然迄今为止我们所看到的查找树都是二叉树，但是还有一种常用的查找树不是二叉树。这种树叫做B-树（B-tree）。
阶为M的B-树是一棵具有下列结构特性的树：
树的根或者是一片树叶，或者其儿子树在2和M之间。
除根外，所有非树叶节点的儿子树在[M/2]和M之间。
所有的树叶都在相同的深度上。
所有的数据都存储在树叶上。(另一种流行的结构允许实际数据存储在树叶上，也可以存储在内部节点上，正如我们在二叉查找树中所做的那样。)
下图中的树是4阶B-树的一个例子。
4阶B-树更流行的称呼是2-3-4树。而3阶B-树叫做2-3树。
为了执行一次Find，我们从根开始并根据要查找的关键字与存储在节点上的两个（很可能是一个）值之间的关系确定（最多）三个方向中的一个方向。
当插入一个关键字的时候，只有在访问路径上的那些内部节点才有可能发生变化，
我们可以通过查找要被删除的关键字并将其除去而完成删除操作。
对于一般的M阶B-树，当插入一个关键字时，惟一的困难发生在接收该关键字的节点已经具有M个关键字的时候。这个关键字使得该节点具有M+1个关键字，我们可以把它分裂成两个节点，它们分别具有[(M+1)/2]个和[(M+1)/2]个关键字。由于这使得父节点多出一个儿子，因此我们必须检查这个节点是否可被父节点接受，如果父节点已经具备M个儿子，那么这个父节点就要被分裂成两个节点。我们重复这个过程直到找到一个父节点具有少于M个儿子，如果我们分裂根节点，那么我们就要创建一个新的根，这个根有两个儿子。
B-树的深度最多[logM/2N]。在路径上的每个节点，我们执行O(logM)时间的工作量以确定选择哪个分支（使用折半查找），但是Insert和Delete可能需要O（M）的工作量来调整该节点上的所有信息。从运行时间考虑，M的最好（合法的）选择是M=3或M=4；当M再增大时插入和删除的时间就会增加。
B-树实际用于数据库系统，在那里树被存储在物理磁盘上而不是主存中。M的值选择为使得一个内部节点仍然能够装入一个磁盘区块的最大值，那么它一般说来是在32≤M≤内。选择存储在一片树叶上的元素的最大个数时，要使得如果树叶是满的那么它就装满一个区块。这意味着，一个记录总可以在很少的磁盘访问中被找到，因为典型的B-树的深度只有2或3，而根（很可能还有第一层）可以放在主存中。
分析指出，一棵B-树将被占满ln2=69%。得到它的第（M+1）项时，例程不是总去分裂节点，而是搜索能够接纳新儿子的兄弟，此时我们就能更好的利用空间。
4总结在实践中，所有平衡树方案的运行时间都不如简单的二叉查找树省时（差一个常数因子），但一般来说是可以接受的，它防止轻易得到最坏情形的输入。
给出一种O（NlogN）排序算法，通过将一些元素插入到查找树中然后执行一次中序遍历，我们得到的是排过序的元素。
全文完。
如果觉得不错，就随手点个「在看」吧。
预览时标签不可点收录于话题#个上一篇下一篇