以下例子的树是存在数组中
1.中序遍历
1 package chapter12Tree; 2 3 public class ArrayBinaryTreeWithInorder 4 { 5 // data members 6 static Object [] a; // array that contains the tree 7 static int last; // position of last element in array a 8 9 /** visit method that prints the element in a[i] */ 10 public static void visit(int i) 11 {System.out.print(a[i] + " ");} 12 13 14 /** inorder traversal */ 15 public static void inOrder(Object [] theArray, int theLast) 16 { 17 // set static data members 18 a = theArray; 19 last = theLast; 20 21 // start the recursive traversal method at the root 22 theInOrder(1); 23 } 24 25 /** actual method to do the inorder traversal */ 26 static void theInOrder(int i) 27 {// traverse subtree rooted at a[i] 28 if (i <= last && a[i] != null) 29 {// root exists 30 theInOrder(2 * i); // do left subtree 31 visit(i); // visit tree root 32 theInOrder(2 * i + 1); // do right subtree 33 } 34 } 35 36 public static void main(String[] args) { 37 Object [] a = {0,1,2,3,4,5}; //第一个位置没用 38 inOrder(a, a.length-1); //输出4 2 5 1 3 39 } 40 }
2.平层遍历
1 package chapter12Tree; 2 3 //Since the elements are stored in the array by levels, 4 //a level order traversal may be done by examining the array 5 //from left to right. The code is given below. 6 public class ArrayBinaryTreeWithLevelOrder 7 { 8 static Object [] a; // array that contains the tree 9 10 /** visit method that prints the element in a[i] */ 11 public static void visit(int i) 12 {System.out.print(a[i] + " ");} 13 14 /** level order traversal */ 15 public static void levelOrder(Object [] theArray, int last) 16 { 17 a = theArray; 18 for (int i = 1; i <= last; i++) 19 if (a[i] != null) 20 visit(i); 21 } 22 23 public static void main(String[] args) { 24 Object [] a = {0,1,2,3,4,5}; //第一个位置没用 25 levelOrder(a, a.length-1); //输出1 2 3 4 5 26 } 27 }