數據結構之二叉樹java實現

二叉樹是一種非線性數據結構，屬於樹結構，最大的特點就是度為2，也就是每個節點只有一個左子樹和一個右子樹。二叉樹的操作主要為創建，先序遍歷，中序遍歷，後序遍歷。還有層次遍歷。遍歷有兩種方式，一是采用遞歸的方式，二是采用轉換為棧進行遍歷，對二叉樹的遍歷本質上市將非線性結構轉換為線性序列。

  1 package tree;
  2 
  3 import java.util.ArrayList;
  4 import java.util.List;
  5 import java.util.Queue;
  6 
  7 //通過先序方式將數組依次添加到二叉樹
  8 public class CreateTreeByArray<E> {
  9     public static class Node<E>{
 10         Node<E> left = null;  //左子樹
 11         Node<E> right = null; //右子樹
 12         E data = null;          //數據域
 13         
 14         //初始化節點
 15         public Node(E data){
 16             this.data = data;
 17             this.left = null;
 18             this.right = null;
 19         }
 20         
 21         public Node(){
 22             
 23         }
 24     }
 25     private Node<E> root = null; //根節點
 26     private List<Node<E>> list = null; //節點列表，用於將數組元素轉化為節點
 27     
 28     public Node<E> getRoot(){
 29         return this.root;
 30     }
 31     
 32     //將將數組轉化為一顆二叉樹，轉換規則：依次為節點列表中節點的左右孩子賦值。左孩子為i*2+1,右孩子為i*2+2
 33     @SuppressWarnings("unchecked")
 34     public void createTreeByArray(Object[] array){
 35         this.list = new ArrayList<Node<E>>();
 36         
 37         //將數組添加到節點列表
 38         for (int i = 0; i < array.length; i++) {
 39             list.add(new Node<E>((E) array[i]));
 40         }
 41         
 42         System.out.println("頭節點->" + list.get(0).data);
 43         this.root = new Node<E>(list.get(0).data); //根節點
 44         
 45         //為二叉樹指針賦值
 46         for(int j = 0; j < (list.size() / 2); j ++){
 47             try {
 48                 //為左子樹賦值  j*2+1
 49                 list.get(j).left = list.get(j * 2 + 1);
 50                 System.out.println("節點" + list.get(j).data + "左子樹 ->" + list.get(j * 2 + 1).data);
 51                 //為右子樹賦值 j*2+2
 52                 list.get(j).right = list.get(j * 2 + 2);
 53                 System.out.println("節點" + list.get(j).data + "右子樹 ->" + list.get(j * 2 + 2).data);
 54             } catch (Exception e) {
 55                 
 56             }
 57         }
 58         
 59     }
 60     
 61     //先序遍歷二叉樹
 62     public void Indorder(Node<E> root){
 63         if(root == null){
 64             return;
 65         }
 66         System.out.println(root.data);
 67         Indorder(root.left);  //遞歸輸出左子樹
 68         Indorder(root.right); //遞歸遍歷右子樹
 69     }
 70     
 71     //中序遍歷二叉樹
 72     public void inOrderTraverse(Node<E> root){
 73         if(root == null){
 74             return;
 75         }
 76         inOrderTraverse(root.left);  //遍歷左子樹
 77         System.out.println(root.data);
 78         inOrderTraverse(root.right); //遍歷右子樹
 79     }
 80     
 81     //後序遍歷
 82     public void postOrderTraverse(Node<E> root){
 83         if(root == null){
 84             return;
 85         }
 86         postOrderTraverse(root.left);  //遍歷左子數節點
 87         postOrderTraverse(root.right); //遍歷右子樹節點
 88         System.out.println(root.data); //從下往上遍歷
 89     }
 90         
 91     
 92     public static void main(String[] args) {
 93         CreateTreeByArray<Integer> createTreeByArray = new CreateTreeByArray<Integer>();
 94         Object[] arrays = {new Integer(1),new Integer(2),new Integer(3),new Integer(4),5,6,7,8,9,10};
 95         createTreeByArray.createTreeByArray(arrays);
 96         System.out.println("===============================");
 97         createTreeByArray.postOrderTraverse(createTreeByArray.list.get(0));
 98     
 99     }
100 
101 }