二叉树的遍历

    1.以某种次序访问所有节点，且每个节点恰好只访问一次

    2.遍历方式：先序遍历、中序遍历、后序遍历。它们是针对根节点的访问顺序决定的

    3.遍历二叉树均指二叉树不为空的情况。

    

1.先序遍历：根节点 --> 左子树 --> 右子树

2.中序遍历：左子树 --> 根节点 --> 右子树

3.后序遍历：左子树 --> 右子树 --> 根节点

范例：

1.节点类 - Node

1 /** 2  * 节点类 3  * @author Ivy 4  */ 5 public class Node { 6     // 节点值 7     int data; 8     // 左子树 9     Node left;10     // 右子树11     Node right;12 13     public Node(int data, Node left, Node right) {14         this.data = data;15         this.left = left;16         this.right = right;17     }18 19 }

2.遍历类 - BinaryTree

import java.util.Vector;/** * 实现二叉树类 * @author Ivy */public class BinaryTree {//  省略其它代码......//    先序遍历    public static Vector rootFirst(Node root) {        Vector result = new Vector();        if (null == result) {            return result;        }        result.add(root);        Vector leftChild = rootFirst(root.left);        result.add(leftChild);        Vector rightChild = rootFirst(root.right);        result.add(rightChild);        return result;    }//    中序遍历    public static Vector rootMid(Node root) {        Vector result = new Vector();        if (null == result) {            return result;        }        Vector leftChild = rootFirst(root.left);        result.add(leftChild);        result.add(root);        Vector rightChild = rootFirst(root.right);        result.add(rightChild);        return result;    }//    后序遍历    public static Vector rootLast(Node root) {        Vector result = new Vector();        if (null == result) {            return result;        }        Vector leftChild = rootFirst(root.left);        result.add(leftChild);        Vector rightChild = rootFirst(root.right);        result.add(rightChild);        result.add(root);        return result;    }    }