二叉树的先序、中序、后序和中序遍历—

二叉树的先序、中序、后序和中序遍历——Java实现

 1 package treeTraverse;
 2 /**
 3  * 定义一个树的结点类
 4  */
 5 public class Node {
 6     private int data;
 7     private Node leftChild;
 8     private Node rightChild;
 9     
10     public Node(){
11         
12     }
13 
14     public Node(int data) {
15         super();
16         this.data = data;
17     }
18 
19     public int getData() {
20         return data;
21     }
22 
23     public void setData(int data) {
24         this.data = data;
25     }
26 
27     public Node getLeftChild() {
28         return leftChild;
29     }
30 
31     public void setLeftChild(Node leftChild) {
32         this.leftChild = leftChild;
33     }
34 
35     public Node getRightChild() {
36         return rightChild;
37     }
38 
39     public void setRightChild(Node rightChild) {
40         this.rightChild = rightChild;
41     }
42     
43 }

 1 package treeTraverse;
 2 
 3 import java.util.ArrayList;
 4 import java.util.List;
 5 
 6 /**
 7  * 实现树的先、中、后及层次遍历
 8  */
 9 public class FindTree {
10 
11     private void visit(int data){
12         System.out.print(data + "-->");
13     }
14     //先序遍历
15     public void preOrder(Node root){
16         if(root == null) return ;
17         
18         visit(root.getData());
19         preOrder(root.getLeftChild());
20         preOrder(root.getRightChild());
21     }
22     //中序遍历
23     public void inOrder(Node root){
24         if(root == null) return ;
25         
26         inOrder(root.getLeftChild());
27         visit(root.getData());
28         inOrder(root.getRightChild());
29     }
30     //后序遍历
31     public void afterOrder(Node root){
32         if(root == null) return ;
33         
34         afterOrder(root.getLeftChild());
35         afterOrder(root.getRightChild());
36         visit(root.getData());
37     }
38     
39     /**
40      * 层次遍历(非递归)
41      * 思路：
42      * 现将二叉树头结点入队列，然后出队列，访问该结点，
43      * 如果它有左子树，则将左子树根节点入队; 
44      * 如果它有右子树，则将右子树根节点入队; 
45      * 然后出队列，对出队列的结点访问，如此反复，知道队列为空。
46      */
47     public void levelOrder(Node root){
48         
49         List<Node> queue = new ArrayList<Node>();
50         if(root != null){
51             queue.add(root);//将根结点入队
52             while(queue.size() != 0){//当队列不空的时候进行循环
53                 Node q = queue.remove(0);//出队列       返回从列表中移除的元素
54                 visit(q.getData());//访问该结点
55                 
56                 if(q.getLeftChild() != null){//如果它有左子树，则将左子树根节点入队; 
57                     queue.add(q.getLeftChild());
58                 }
59                 if(q.getRightChild() != null){//如果它有右子树，则将右子树根节点入队;
60                     queue.add(q.getRightChild());
61                 }
62             }
63         }    
64     }
65 }

 1 package treeTraverse;
 2 
 3 /**
 4  * 构建一个二叉树排序树并测试
 5  */
 6 public class TestTree {
 7     public static void main(String[] args) {
 8         FindTree ft = new FindTree();
 9         int[] array = {12,76,35,22,16,48,90,46,9,40,90};
10         
11         Node root = new Node(array[0]);
12         for(int i = 1; i < array.length; i++){
13             insert(root, array[i]);
14         }
15         System.out.println("preorder:");  
16         ft.preOrder(root);  
17         System.out.println("
"+"inorder:");  
18         ft.inOrder(root);  
19         System.out.println("
"+"afterorder:");  
20         ft.afterOrder(root);  
21         System.out.println("
"+"levelOrder:");  
22         ft.levelOrder(root); 
23     }
24 
25     /**
26      * 构造二叉排序树, 性质如下:
27      * 若它的左子树不空,则左子树上所有关键字的值均小于根关键字的值
28      * 若它的右子树不空,则右子树上所有关键字的值均小于根关键字的值
29      * 如果输出二叉树排序树的中序遍历，则这个序列是递增有序的
30      * @param root
31      * @param data
32      */
33     private static void insert(Node root, int data) {
34         if(root.getData() < data){
35             if(root.getRightChild() == null){
36                 root.setRightChild(new Node(data));
37             }else{
38                 insert(root.getRightChild(), data);
39             }
40         }else {
41             if(root.getData() > data){
42                 if(root.getLeftChild() == null){
43                     root.setLeftChild(new Node(data));
44                 }else{
45                     insert(root.getLeftChild(), data);
46                 }
47             }
48         }
49     }
50     
51 }

遍历结果：

preorder:
12-->9-->76-->35-->22-->16-->48-->46-->40-->90-->
inorder:
9-->12-->16-->22-->35-->40-->46-->48-->76-->90-->
afterorder:
9-->16-->22-->40-->46-->48-->35-->90-->76-->12-->
levelOrder:
12-->9-->76-->35-->90-->22-->48-->16-->46-->40-->