二叉数的遍历

  1 import java.util.LinkedList;
  2 import java.util.List;
  3 
  4 /**
  5  * 功能：把一个数组的值存入二叉树中，然后进行3种方式的遍历
  6  * 
  7  * 参考资料0:数据结构(C语言版)严蔚敏
  8  * 
  9  * 参考资料1：http://zhidao.baidu.com/question/81938912.html
 10  * 
 11  * 参考资料2：http://cslibrary.stanford.edu/110/BinaryTrees.html#java
 12  * 
 13  * @author ocaicai@yeah.net @date: 2011-5-17
 14  * 
 15  */
 16 public class BinTreeTraverse {
 17 
 18     private int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 19     private static List<Node> nodeList = null;
 20 
 21     /**
 22      * 内部类：节点
 23      * 
 24      * @author ocaicai@yeah.net @date: 2011-5-17
 25      * 
 26      */
 27     private static class Node {
 28         Node leftChild;
 29         Node rightChild;
 30         int data;
 31 
 32         Node(int newData) {
 33             leftChild = null;
 34             rightChild = null;
 35             data = newData;
 36         }
 37     }
 38 
 39     public void createBinTree() {
 40         nodeList = new LinkedList<Node>();
 41         // 将一个数组的值依次转换为Node节点
 42         for (int nodeIndex = 0; nodeIndex < array.length; nodeIndex++) {
 43             nodeList.add(new Node(array[nodeIndex]));
 44         }
 45         // 对前lastParentIndex-1个父节点按照父节点与孩子节点的数字关系建立二叉树
 46         for (int parentIndex = 0; parentIndex < array.length / 2 - 1; parentIndex++) {
 47             // 左孩子
 48             nodeList.get(parentIndex).leftChild = nodeList
 49                     .get(parentIndex * 2 + 1);
 50             // 右孩子
 51             nodeList.get(parentIndex).rightChild = nodeList
 52                     .get(parentIndex * 2 + 2);
 53         }
 54         // 最后一个父节点:因为最后一个父节点可能没有右孩子，所以单独拿出来处理
 55         int lastParentIndex = array.length / 2 - 1;
 56         // 左孩子
 57         nodeList.get(lastParentIndex).leftChild = nodeList
 58                 .get(lastParentIndex * 2 + 1);
 59         // 右孩子,如果数组的长度为奇数才建立右孩子
 60         if (array.length % 2 == 1) {
 61             nodeList.get(lastParentIndex).rightChild = nodeList
 62                     .get(lastParentIndex * 2 + 2);
 63         }
 64     }
 65 
 66     /**
 67      * 先序遍历
 68      * 
 69      * 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已
 70      * 
 71      * @param node
 72      *            遍历的节点
 73      */
 74     
 75     
 76     public static void preOrderTraverse(Node node) {
 77         if (node==null)
 78         {
 79             return;
 80         }
 81         
 82         System.out.print(node.data+" ");
 83         preOrderTraverse(node.leftChild);
 84         
 85         preOrderTraverse(node.rightChild);
 86     }
 87 
 88     /**
 89      * 中序遍历
 90      * 
 91      * 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已
 92      * 
 93      * @param node
 94      *            遍历的节点
 95      */
 96     public static void inOrderTraverse(Node node) {
 97         if (node==null)
 98         {
 99             return ;
100         }
101         
102         inOrderTraverse(node.leftChild);
103         System.out.print(node.data+" ");
104         inOrderTraverse(node.rightChild);
105     }
106 
107     /**
108      * 后序遍历
109      * 
110      * 这三种不同的遍历结构都是一样的，只是先后顺序不一样而已
111      * 
112      * @param node
113      *            遍历的节点
114      */
115     public static void postOrderTraverse(Node node) {
116         if (node==null)
117         {
118             return ;
119         }
120         
121         postOrderTraverse(node.leftChild);
122         postOrderTraverse(node.rightChild);
123         System.out.print(node.data+" ");
124     }
125 
126     public static void main(String[] args) {
127         BinTreeTraverse binTree = new BinTreeTraverse();
128         binTree.createBinTree();
129         // nodeList中第0个索引处的值即为根节点
130         Node root = nodeList.get(0);
131 
132         System.out.println("先序遍历：");
133         preOrderTraverse(root);
134         System.out.println();
135 
136         System.out.println("中序遍历：");
137         inOrderTraverse(root);
138         System.out.println();
139 
140         System.out.println("后序遍历：");
141         postOrderTraverse(root);
142     }
143 
144 }