1 //二叉树节点 2 public class BinaryTreeNode { 3     private int data; 4     private BinaryTreeNode left; 5     private BinaryTreeNode right; 6      7     public BinaryTreeNode() {} 8  9     public BinaryTreeNode(int data, BinaryTreeNode left, BinaryTreeNode right) {10         super();11         this.data =http://www.mamicode.com/ data;12         this.left = left;13         this.right = right;14     }15 16     public int getData() {17         return data;18     }19 20     public void setData(int data) {21         this.data =http://www.mamicode.com/ data;22     }23 24     public BinaryTreeNode getLeft() {25         return left;26     }27 28     public void setLeft(BinaryTreeNode left) {29         this.left = left;30     }31 32     public BinaryTreeNode getRight() {33         return right;34     }35 36     public void setRight(BinaryTreeNode right) {37         this.right = right;38     }39 }

  1 import com.ccut.aaron.stack.LinkedStack;  2   3 public class BinaryTree {  4     //前序遍历递归的方式  5     public void preOrder(BinaryTreeNode root){  6         if(null!=root){  7             System.out.print(root.getData()+"\t");  8             preOrder(root.getLeft());  9             preOrder(root.getRight()); 10         } 11     } 12      13     //前序遍历非递归的方式 14     public void preOrderNonRecursive(BinaryTreeNode root){ 15         Stack<BinaryTreeNode> stack=new Stack<BinaryTreeNode>(); 16         while(true){ 17             while(root!=null){ 18                 System.out.print(root.getData()+"\t"); 19                 stack.push(root); 20                 root=root.getLeft(); 21             } 22             if(stack.isEmpty()) break; 23             root=stack.pop(); 24             root=root.getRight(); 25         } 26     } 27      28     //中序遍历采用递归的方式 29     public void inOrder(BinaryTreeNode root){ 30         if(null!=root){ 31             inOrder(root.getLeft()); 32             System.out.print(root.getData()+"\t"); 33             inOrder(root.getRight()); 34         } 35     } 36      37     //中序遍历采用非递归的方式 38     public void inOrderNonRecursive(BinaryTreeNode root){ 39         Stack<BinaryTreeNode> stack=new Stack<BinaryTreeNode>(); 40         while(true){ 41             while(root!=null){ 42                 stack.push(root); 43                 root=root.getLeft(); 44             } 45             if(stack.isEmpty())break; 46             root=stack.pop(); 47             System.out.print(root.getData()+"\t"); 48             root=root.getRight(); 49         } 50     } 51      52     //后序遍历采用递归的方式 53     public void postOrder(BinaryTreeNode root){ 54         if(root!=null){ 55             postOrder(root.getLeft()); 56             postOrder(root.getRight()); 57             System.out.print(root.getData()+"\t"); 58         } 59     } 60      61     //后序遍历采用非递归的方式 62     public void postOrderNonRecursive(BinaryTreeNode root){ 63         Stack<BinaryTreeNode> stack=new Stack<BinaryTreeNode>(); 64         while(true){ 65             if(root!=null){ 66                 stack.push(root); 67                 root=root.getLeft(); 68             }else{ 69                 if(stack.isEmpty()) return; 70                  71                 if(null==stack.lastElement().getRight()){ 72                     root=stack.pop(); 73                     System.out.print(root.getData()+"\t"); 74                     while(root==stack.lastElement().getRight()){ 75                         System.out.print(stack.lastElement().getData()+"\t"); 76                         root=stack.pop(); 77                         if(stack.isEmpty()){ 78                             break; 79                         } 80                     } 81                 } 82                  83                 if(!stack.isEmpty()) 84                     root=stack.lastElement().getRight(); 85                 else 86                     root=null; 87             } 88         } 89     } 90  91     //层序遍历 92     public void levelOrder(BinaryTreeNode root){ 93         BinaryTreeNode temp; 94         Queue<BinaryTreeNode> queue=new LinkedList<BinaryTreeNode>(); 95         queue.offer(root); 96         while(!queue.isEmpty()){ 97             temp=queue.poll(); 98             System.out.print(temp.getData()+"\t"); 99             if(null!=temp.getLeft()) 100                 queue.offer(temp.getLeft());101             if(null!=temp.getRight()){102                 queue.offer(temp.getRight());103             }104         }105     }106     107     public static void main(String[] args) {108         BinaryTreeNode node10=new BinaryTreeNode(10,null,null);109         BinaryTreeNode node8=new BinaryTreeNode(8,null,null);110         BinaryTreeNode node9=new BinaryTreeNode(9,null,node10);111         BinaryTreeNode node4=new BinaryTreeNode(4,null,null);112         BinaryTreeNode node5=new BinaryTreeNode(5,node8,node9);113         BinaryTreeNode node6=new BinaryTreeNode(6,null,null);114         BinaryTreeNode node7=new BinaryTreeNode(7,null,null);115         BinaryTreeNode node2=new BinaryTreeNode(2,node4,node5);116         BinaryTreeNode node3=new BinaryTreeNode(3,node6,node7);117         BinaryTreeNode node1=new BinaryTreeNode(1,node2,node3);118         119         BinaryTree tree=new BinaryTree();120         //采用递归的方式进行遍历121         System.out.println("-----前序遍历------");122         tree.preOrder(node1);123         System.out.println();124         //采用非递归的方式遍历125         tree.preOrderNonRecursive(node1);126         System.out.println();127 128         129         //采用递归的方式进行遍历130         System.out.println("-----中序遍历------");131         tree.inOrder(node1);132         System.out.println();133         //采用非递归的方式遍历134         tree.inOrderNonRecursive(node1);135         System.out.println();136         137         //采用递归的方式进行遍历138         System.out.println("-----后序遍历------");139         tree.postOrder(node1);140         System.out.println();141         //采用非递归的方式遍历142         tree.postOrderNonRecursive(node1);143         System.out.println();144         145         //采用递归的方式进行遍历146         System.out.println("-----层序遍历------");147         tree.levelOrder(node1);148         System.out.println();149     }150 }