二叉查找树（三）
我们知道二叉查找树是一种数据结构，它支持多种动态集合的操作，包括：查询，最大值，最小值，前驱，后继，插入和删除等操作。那么我们在前一篇已经创建了二叉查找树，那么我们来实现二叉查找树的各种操作吧。(*^__^*) （以下纯属个人理解，个人原创，理解不当的地方，请指正，谢谢）
我们来看二叉树的遍历操作，所谓遍历，顾名思义，就是能够依次的访问二叉查找树中的各个结点。在数据结构课堂上，我们知道，遍历方式有深度优先和广度优先遍历，深度优先又包括前序、中序和后序遍历；广度优先遍历，在二叉树的范畴中，就是层序遍历，就是先遍历某一层的结点，然后再遍历下一层的结点。好了，一个个的来介绍吧。
前序遍历前序遍历，就是先遍历父结点，然后遍历左子树，最后遍历右子树的遍历方法，所谓前序，指的是遍历父结点发生在遍历左右子树之前。
前序遍历的递归算法很简单，代码如下：
1 /**
2 * 递归前序遍历以x为根的二叉树
3 * @author Alfred
4 * @param x 根结点
5 */
6 public void preOrderTreeWalk(TreeNode x){
7 if (x != null ){
8 System.out.print(x); // 访问形式为打印输出一下
9 preOrderTreeWalk(x.getLeft());
10 preOrderTreeWalk(x.getRight());
11 }
12 }
这个算法，没什么难点可说，就是先访问当前结点，然后递归访问当前结点的左子树，最后递归访问当前结点的右子树。因为要遍历所有节点，所以该算法的时间复杂度为O(n)；
递归往往意味着低效，那么，如果不用递归的算法，如果实现前序遍历呢？这里有两个方法，都是借助“栈”来实现的。
方法1是模拟递归算法的实现效果，具体代码如下：
1 /**
2 * 非递归前序遍历以x为根结点的二叉树
3 * @author Alfred
4 * @param x 根结点
5 */
6 public void preOrderTreeWalkNonrecursive1(TreeNode x){
7 // 借助栈来实现。
8 Stack<TreeNode> stack = new Stack<TreeNode> ();
9 while (x != null || ! stack.empty()){
10 if (x != null ){
11 System.out.print(x); // 遍历输出
12 stack.push(x); // 压栈
13 x = x.getLeft();
14 } else {
15 x = stack.pop(); // 出栈
16 x = x.getRight();
17 }
18 }
19 }
方法1每次都将遇到的节点压入栈，当左子树遍历完毕后才从栈中弹出最后一个访问的节点，访问其右子树。在同一层中，不可能同时有两个节点压入栈，因此栈的大小空间为O(h)，h为二叉树高度。时间方面，每个节点都被压入栈一次，弹出栈一次，访问一次，复杂度为O(n)。
方法2是直接模拟递归来实现的，代码如下：
/**
* 非递归前序遍历以x为根结点的二叉树
* @author Alfred
* @param x 根结点
*/
public void preOrderTreeWalkNonrecursive2(TreeNode x){
Stack <TreeNode> stack = new Stack<TreeNode> ();
if (x != null ){
stack.push(x);
while (! stack.empty()){
TreeNode tmpNode = stack.pop();
System.out.print(tmpNode); // 遍历输出
if (tmpNode.getRight() != null ){
stack.push(tmpNode.getRight());
}
if (tmpNode.getLeft() != null ){
stack.push(tmpNode.getLeft());
}
}
}
}
方法2每次将节点压入栈，然后弹出，压右子树，再压入左子树，在遍历过程中，遍历序列的右节点依次被存入栈，左节点逐次被访问。同一时刻，栈中元素为m-1个右节点和1个最左节点，最高为h，所以空间也为O(h)；每个节点同样被压栈一次，弹栈一次，访问一次，时间复杂度O(n)。
中序遍历中序遍历，就是先遍历左子树，然后遍历父结点，最后遍历右子树，所谓中序，是指遍历父结点在遍历左子树和遍历右子树之间。同时，根据二叉查找树的性质，中序遍历的输出结果，恰好就是排序之后的序列。
中序遍历的递归算法也很简单，具体代码如下：
1 /**
2 * 递归中序遍历以x为根的二叉树
3 * @author Alfred
4 * @param x 根结点
5 */
6 public void inOrderTreeWalk(TreeNode x){
7 if (x != null ){
8 inOrderTreeWalk(x.getLeft());
9 System.out.print(x);
10 inOrderTreeWalk(x.getRight());
11 }
12 }
先递归遍历左子树，然后访问父结点，最后递归遍历右子树，上面的算法很简单，不多说。
同理，非递归该如何实现二叉查找树的中序遍历呢？同样，也需要借助“栈”来实现。代码如下：
1 /**
2 * 非递归中序遍历以x为根结点的二叉树
3 * @author Alfred
4 * @param x 根结点
5 */
6 public void inOrderTreeWalkNonrecursive(TreeNode x){
7 Stack<TreeNode> stack = new Stack<TreeNode> ();
8 while (x != null || ! stack.empty()){
9 if (x != null ){
10 stack.push(x);
11 x = x.getLeft();
12 } else {
13 x = stack.pop();
14 System.out.print(x); // 遍历输出
15 x = x.getRight();
16 }
17 }
18 }
该算法与前序遍历的非递归算法1非常的相近，时间和空间复杂度也相同。至于对应的第二种非递归中序遍历方法，没有想到，牛逼的童鞋们自己来补充吧~
后续遍历后序遍历，就是先遍历左子树，然后遍历右子树，最后遍历父结点，所谓后序，是指遍历父结点在遍历左右子树之后。
同样，后序遍历的递归算法也很简单，代码如下：
1 /**
2 * 递归后序遍历以x为根的二叉树
3 * @author Alfred
4 * @param x 根结点
5 */
6 public void postOrderTreeWalk(TreeNode x){
7 if (x != null ){
8 postOrderTreeWalk(x.getLeft());
9 postOrderTreeWalk(x.getRight());
10 System.out.print(x);
11 }
12 }
先递归遍历左子树，然后递归遍历右子树，最后父结点。
那么，后序遍历的递归算法该如何写呢？这里同样有两个方法，方法1用单栈实现，方法2用双栈实现。
方法1代码如下：
1 /**
2 * 非递归后序遍历以x为根结点的二叉树
3 * @author Alfred
4 * @param x 根结点
5 */
6 public void postOrderTreeWalkNonrecursive1(TreeNode x){
7 Stack<TreeNode> stack = new Stack<TreeNode> ();
8 TreeNode prev = null ;
9 TreeNode curr = null ;
10 if (x != null ){
11 stack.push(x);
12 }
13 while (! stack.empty()){
14 curr = stack.peek();
15 if (prev == null || prev.getLeft() == curr || prev.getRight() == curr){
16 if (curr.getLeft() != null ){
17 stack.push(curr.getLeft()); // 压左孩子
18 } else if (curr.getRight() != null ){
19 stack.push(curr.getRight()); // 压右孩子
20 }
21 } else if (curr.getLeft() == prev){
22 if (curr.getRight() != null ){
23 stack.push(curr.getRight()); // 压右孩子
24 }
25 } else {
26 System.out.print(curr); // 遍历输出
27 stack.pop();
28 }
29 prev = curr;
30 }
31 }
方法1是根据访问前后元素的关系来进行的算法，根据关系的不同，发生的行为也就不同。
方法2的具体代码为：
1 /**
2 * 非递归后序遍历以x为根结点的二叉树
3 * @author Alfred
4 * @param x 根结点
5 */
6 public void postOrderTreeWalkNonrecursive2(TreeNode x){
7 Stack<TreeNode> stack = new Stack<TreeNode> ();
8 Stack<TreeNode> output = new Stack<TreeNode> ();
9 TreeNode curr = null ;
10 if (x != null ){
11 stack.push(x);
12 }
13 while (! stack.empty()){
14 curr = stack.pop();
15 output.push(curr); // 存放到输出地栈里面
16 if (curr.getLeft() != null ){
17 stack.push(curr.getLeft()); // 压左孩子
18 }
19 if (curr.getRight() != null ){
20 stack.push(curr.getRight()); // 压右孩子
21 }
22 }
23 while (! output.empty()){
24 TreeNode tmpNode = output.pop();
25 System.out.print(tmpNode); // 打印输出
26 }
27 }
方法2利用一个栈出栈并压入到另一个栈的手法，对二叉查找树进行了后序遍历。
层序遍历层序遍历，就是按照二叉树的层次结构，逐层进行遍历的方法。层序遍历需要借助“队列”来实现，具体的代码如下：
1 /**
2 * 层序遍历二叉树
3 * @author Alfred
4 * @param x 根结点
5 */
6 public void levelOrderTreeWalk(TreeNode x){
7 Queue<TreeNode> queue = new LinkedList<TreeNode> ();
8 TreeNode tmpNode = null ;
9 if (x != null ){
10 queue.offer(x);
11 }
12 while (! queue.isEmpty()){
13 tmpNode = queue.poll();
14 System.out.print(tmpNode); // 打印输出
15 if (tmpNode.getLeft() != null ){
16 queue.offer(tmpNode.getLeft()); // 左孩子入队
17 }
18 if (tmpNode.getRight() != null ){
19 queue.offer(tmpNode.getRight()); // 右孩子入队
20 }
21 }
22 }
上面的算法，先将根结点入队，然后出队，遍历输出，然后将左孩子和右孩子分别入队，依次循环下去，知道队列为空为止。
好了，遍历就先写到这儿吧。
ps：有写的不好的，请各位童鞋指正。
标签: 算法
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息