树与搜索

1. 树与树的遍历

数据结构中，在实际编程中频繁应用的‘树’具有简单明确的基本架构：根结点无父结点而其他每个结点仅有一个直接前驱。根结点无父结点；除叶子外其余各结点都拥有一个或多个直接后继。叶子则无后继。各层间通过指针建立连接。二叉树作为一种特殊的树类型，在其中每个分支至多包含两个子分支。其关键功能在于实现访问所有存储单元的遍历过程。通常采用三种不同的遍历策略来完成这一过程。

• 前序搜索法先访问当前结点之后再依次执行左右子树的操作序列.通过图形化的展示可以看出其具体的搜索路径.
• 中序搜索法则按照先左后右再当前结点的方式来展开.同样地 在图形界面中可以看到其具体的运行轨迹.
• 后续操作则遵循先执行左右子树操作完毕之后才进行当前结点相关操作的原则.同样地 在图形界面中可以看到其具体的运行轨迹.
• 广度优先搜索采用层次分明的方式展开.即从顶层起一层一层地向下探索各个层级的所有元素.

在二叉树结构中，二叉搜索树是一种特殊的形态。其中左子节点的数值总是小于或等于根节点的值，而右子节点的数值则总是大于或等于根节点的值。如图所示的内容确实是一棵典型的二叉搜索树实例。通过平均O(lo