二叉树类：
1 package com.antis.tree; 2 3 public class BinaryTree { 4 5 int data; //根节点数据 6 BinaryTree left; //左子树 7 BinaryTree right; //右子树 8 9 public BinaryTree(int data) //实例化二叉树类 10 { 11 this.data = data; 12 left = null; 13 right = null; 14 } 15 /** 16 * 向二叉树中插入子节点 17 * @param root 18 * @param data 19 */ 20 public void insert(BinaryTree root,int data){ 21 //二叉树的左节点都比根节点小 22 if(data>root.data) 23 { 24 if(root.right==null){ 25 root.right = new BinaryTree(data); 26 }else{ 27 this.insert(root.right, data); 28 } 29 }else{ 30 //二叉树的右节点都比根节点大 31 if(root.left==null){ 32 root.left = new BinaryTree(data); 33 }else{ 34 this.insert(root.left, data); 35 } 36 } 37 } 38 39 }
二叉树遍历代码：
1 package com.antis.tree; 2 3 import java.util.Stack; 4 5 public class BinaryTreeTraversal { 6 7 /** 8 * 先序遍历--先根遍历递归 9 * @param root 10 */ 11 public static void preOrder(BinaryTree root){ //先根遍历 12 if (root==null) { 13 return; 14 } 15 System.out.print(root.data+"-"); 16 preOrder(root.left); 17 preOrder(root.right); 18 } 19 /** 20 * 中序遍历--中根遍历递归 21 * @param root 22 */ 23 public static void inOrder(BinaryTree root){ //中根遍历 24 if (root==null) { 25 return; 26 } 27 inOrder(root.left); 28 System.out.print(root.data+"--"); 29 inOrder(root.right); 30 } 31 /** 32 * 后序遍历--后根遍历递归 33 * @param root 34 */ 35 public static void postOrder(BinaryTree root){ //后根遍历 36 if (root==null) { 37 return; 38 } 39 postOrder(root.left); 40 postOrder(root.right); 41 System.out.print(root.data+"---"); 42 } 43 // 先序遍历非递归 44 public static void preOrder2(BinaryTree t) { 45 Stack<BinaryTree> s = new Stack<BinaryTree>(); 46 while (t != null || !s.empty()) { 47 while (t != null) { 48 System.out.print(t.data+"-"); 49 s.push(t); 50 t = t.left; 51 } 52 if (!s.empty()) { 53 t = s.pop(); 54 t = t.right; 55 } 56 } 57 } 58 // 中序遍历非递归 59 public static void InOrder2(BinaryTree t) { 60 Stack<BinaryTree> s = new Stack<BinaryTree>(); 61 while (t != null || !s.empty()) { 62 while (t != null) { 63 s.push(t); 64 t = t.left; 65 } 66 if (!s.empty()) { 67 t = s.pop(); 68 System.out.print(t.data+"--"); 69 t = t.right; 70 } 71 } 72 } 73 74 // 后序遍历非递归 75 public static void PostOrder2(BinaryTree t) { 76 Stack<BinaryTree> s = new Stack<BinaryTree>(); 77 Stack<Integer> s2=new Stack<Integer>(); 78 Integer i=new Integer(1); 79 while (t != null || !s.empty()) { 80 while (t != null) { 81 s.push(t); 82 s2.push(new Integer(0)); 83 t = t.left; 84 } 85 while (!s.empty() && s2.peek().equals(i)) { 86 s2.pop(); 87 System.out.print(s.pop().data+"---"); 88 } 89 90 if (!s.empty()) { 91 s2.pop(); 92 s2.push(new Integer(1)); 93 t = s.peek(); 94 t = t.right; 95 } 96 } 97 } 98 public static void main(String[] str){ 99 int[] array = {12,76,35,22,16,48,90,46,9,40}; 100 BinaryTree root = new BinaryTree(array[0]); //创建二叉树 101 for(int i=1;i<array.length;i++){ 102 root.insert(root, array[i]); //向二叉树中插入数据 103 } 104 System.out.println("先根遍历："); 105 preOrder(root); 106 System.out.println(); 107 System.out.println("先根遍历："); 108 preOrder2(root); 109 System.out.println(); 110 System.out.println("中根遍历："); 111 inOrder(root); 112 System.out.println(); 113 System.out.println("中根遍历："); 114 InOrder2(root); 115 System.out.println(); 116 System.out.println("后根遍历："); 117 postOrder(root); 118 System.out.println(); 119 System.out.println("后根遍历："); 120 PostOrder2(root); 121 } 122 }
运行结果：
先根遍历：
12-9-76-35-22-16-48-46-40-90-
先根遍历：
12-9-76-35-22-16-48-46-40-90-
中根遍历：
9--12--16--22--35--40--46--48--76--90--
中根遍历：
9--12--16--22--35--40--46--48--76--90--
后根遍历：
9---16---22---40---46---48---35---90---76---12---
后根遍历：
9---16---22---40---46---48---35---90---76---12---