2014/07/09

[Java] 實作二元樹 Binary Tree




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

以Ｃ語言實作傳送門：




我切為三個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<integer> list = new ArrayList<integer>();
    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<integer>(){//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());
    }
}
於
標籤： ,