[Java] 實作二元樹 Binary Tree

二元樹維基傳送門:http://goo.gl/V9CcCK

以C語言實作傳送門:
 
我切為三個Class:Node, Btree, Test
 

 

Test.java

擺main函式,陣列arr自定,只要一個Node有值,他的left和right就要放進陣列
裡,若無值則為-1
以以下範例來說:{7,3,6,1,-1,-1,-1,10,-1,-1,5,8,-1,-1,3,-1,-1}的樹會長成這樣
 
    level1                         7
    
    level2               3                   5
   level3            6        10        8       3
   level4        1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Test {
    public static void main(String args[]){
        //Input,in terms of Preorder
        int[] arr = {7,3,6,1,-1,-1,-1,10,-1,-1,5,8,-1,-1,3,-1,-1};
        Btree btree = new Btree(arr);
        System.out.print("\nPreOrder\n");
        btree.preOrder(btree.root);
        System.out.print("\nInOrder\n");
        btree.inOrder(btree.root);
        System.out.print("\nPostOrder\n");
        btree.postOrder(btree.root);
        btree.size();
        btree.printAll(btree.root);
    }
}


Node.java:

定義節點,有data, left, right
1
2
3
4
5
6
7
8
9
10
public class Node {
    int data = 0;
    Node left;
    Node right;
    public Node(int data){
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

Btree.java:

二元樹,共五個method

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Btree {
    Node root;
    private static int i = 0;
    private static ArrayList list = new ArrayList();
    public Btree(int[] arr){
        this.root = creat(arr);
    }
    private Node creat(int[] arr){
        Node temp;
        int data = arr[i];
        i++;
        if(data==-1)
            return null;
        list.add(data);
        temp = new Node(data);
        temp.left = creat(arr);
        temp.right = creat(arr);
        return temp;
    }
    public void preOrder(Node n){//中->左->右
        if (n != null) {
            System.out.print(n.data+" ");
            preOrder(n.left);
            preOrder(n.right);
        }
    }
    public void postOrder(Node n) {//左->右->中
        if (n!=null) {
            postOrder(n.left);
            postOrder(n.right);
            System.out.print(n.data+" ");
        }
    }
    public void inOrder(Node n) {//左->中->右
        if (n != null) {
            inOrder(n.left);
            System.out.print(n.data+" ");
            inOrder(n.right);
        }
    }
    public void printAll(Node n) {//樹的節點降冪輸出
        System.out.print("\nPrintAll: ");
        Collections.sort(list, new Comparator(){//Sort ArrayList
            @Override
            public int compare(Integer a, Integer b){
                return a.compareTo(b);
            }
        });
        for (int i = list.size()-1; i >= 0; i--) {
            System.out.print(list.get(i)+" ");
        }
    }
    public void size() {//樹的大小
        System.out.print("\nSize: "+list.size());
    }
}
廣告

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s