二叉树的前序、中序、后序、层序遍历方法

  1 package BinaryTreeDemo01;
  2 
  3 /*
  4  * 二叉树的前、中、后、层序遍历方法；
  5  * 其中前中后三种遍历方法类似，只是代码的顺序不同；
  6  * 层序遍历则使用队列实现；
  7  * */
  8 
  9 import java.util.LinkedList;
 10 import java.util.Queue;
 11 
 12 class BinaryTree01{
 13     class Node{
 14         private int data;
 15         private Node left;
 16         private Node right;
 17         public Node(int data){
 18             this.data = data;
 19         }
 20         public void addNode(Node newNode){
 21             if(this.data > newNode.data){
 22                 if(this.left == null){
 23                     this.left = newNode;
 24                 }else{
 25                     this.left.addNode(newNode);
 26                 }
 27             }
 28             if(this.data <= newNode.data){
 29                 if(this.right == null){
 30                     this.right = newNode;
 31                 }else{
 32                     this.right.addNode(newNode);
 33                 }
 34             }
 35         }
 36         
 37         public void preTravel(){            //前序遍历
 38             System.out.println(this.data);    //输出根节点数据，此处的根节点包括指子树的根节点
 39             if(this.left != null){
 40                 this.left.preTravel();        //左子树递归
 41             }
 42             if(this.right != null){            //右子树递归
 43                 this.right.preTravel();
 44             }
 45         }
 46         public void midTravel(){            //中序遍历
 47             if(this.left != null){            
 48                 this.left.midTravel();        //左子树递归
 49             }
 50             System.out.println(this.data);    //输出根节点数据，此处的根节点包括指子树的根节点
 51             if(this.right != null){
 52                 this.right.midTravel();        //右子树递归
 53             }
 54         }
 55         public void lastTravel(){            //后序遍历，其过程和前两种遍历方法类似，只是访问根节点的时间不同
 56             if(this.left != null){
 57                 this.left.lastTravel();
 58             }
 59             if(this.right != null){
 60                 this.right.lastTravel();
 61             }
 62             System.out.println(this.data);
 63         }    
 64     }
 65     Node root;
 66     public void add(int data){
 67         Node newNode = new Node(data);
 68         if(this.root == null){
 69             this.root = newNode;
 70         }else{
 71             this.root.addNode(newNode);
 72         }
 73     }
 74     public void prePrint(){
 75         this.root.preTravel();
 76     }
 77     public void midPrint(){
 78         this.root.midTravel();
 79     }
 80     public void lastPrint(){
 81         this.root.lastTravel();
 82     }
 83     
 84     
 85     /*
 86      * 层序遍历的思想不同于上边三种遍历；
 87      * 运用队列实现；先将根节点入队列，只要队列不为空，就出队列，并访问（打印或者加入数组、集合），
 88      * 接着将访问节点的左右子树依次入队列
 89      * */
 90     public void levelPrint(){
 91         levelTravel(this.root);
 92     }
 93     public void levelTravel(Node root){
 94         if(root == null) return;
 95         Queue<Node> q=new LinkedList<Node>();    //运用队列实现层序遍历
 96         q.add(root);
 97         while(!q.isEmpty()){
 98             Node temp =  q.poll();
 99             System.out.println(temp.data);
100             if(temp.left!=null)q.add(temp.left); 
101             if(temp.right!=null)q.add(temp.right);
102         }
103     }
104 } 
105 public class BinaryTravel01 {
106 
107     public static void main(String[] args) {
108         BinaryTree01 b = new BinaryTree01();
109         b.add(8);
110         b.add(3);
111         b.add(10);
112         b.add(9);
113         b.add(1);
114         b.add(5);
115         System.out.println("前序遍历：");
116         b.prePrint();
117         System.out.println("中序遍历：");
118         b.midPrint();
119         System.out.println("后序遍历：");
120         b.lastPrint();
121         System.out.println("层序遍历：");
122         b.levelPrint();
123     }
124 }