【資料結構】樹狀結構與二元樹（Binary Tree）

日期：

樹狀結構是一種能夠儲存具有「階層」關係的資料的結構，實際應用包含現實生活中的組織架構圖，或是電腦中的檔案總管等等。本文會先解說樹狀結構是什麼，接著使用 Java 程式語言實作出二元樹，最後走訪樹中的每一個資料。

一、樹的基本概念

在日常生活中，有一些事物是可以用「樹狀圖」來表達的，例如家族成員，上面有自己的父母，下面有子女。至於阿姨、舅舅、姑姑等親戚又與父母同一輩。而兄弟姊妹、堂親、表親則與自己同一輩。

在電腦中，檔案的儲存方式也能用樹狀圖表達。一個資料夾裡面可能又有許多資料夾和其他檔案。一直深入到資料夾中沒有資料夾，才到達終點。像這些具有「階層」關係的資料，我們可以用「樹狀結構」來儲存。

從概念上來看，樹與鏈結串列一樣，都是由一個一個節點構成的。不同之處在於鏈結串列的節點只會指向一個節點，而樹節點可以指向多個。以下是樹的示意圖。

在圖中，最上方的節點0稱為「根節點」（root），而節點1、2是它的「子節點」（child）。由於其具有2個子節點，我們說它的「分支度」為2。依此類推，節點1的分支度為3。而節點3~7由於沒有子節點，於是稱它們為「樹葉」（leaf）或終端節點（terminal node）。樹的節點除了存有資料，還會有鏈結指向子節點。

二、二元樹

在資料結構的領域中，以「二元樹」（Binary Tree）的使用最為廣泛。二元樹的每個節點最多只有2個子節點，分別是左節點與右節點。二元樹能應用於排序、搜尋與決策過程等。讀者可以聯想一下排序與搜尋的演算法，經常會有比大小的動作，這項判斷只有「大」和「小」兩種可能。而在進行決策的過程判斷自身狀況時，也只有「是」和「否」兩種回答。

接下來讓我們用 Java 進行二元樹的實作練習。以下是樹節點的類別，value 欄位是用於儲存資料，而 leftNode 與 rightNode 欄位分別作為指向左、右節點的指標。

public class TreeNode<E> {
    private E value;
    private TreeNode<E> leftNode;
    private TreeNode<E> rightNode;

    public TreeNode(E value) {
        this.value = value;
    }

    public E getValue() {
        return value;
    }

    public TreeNode<E> getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(TreeNode<E> leftNode) {
        this.leftNode = leftNode;
    }

    public TreeNode<E> getRightNode() {
        return rightNode;
    }

    public void setRightNode(TreeNode<E> rightNode) {
        this.rightNode = rightNode;
    }

    @Override
    public String toString() {
        return value.toString();
    }
}

經由將多個 TreeNode 連結起來，就能形成一棵二元樹。以下圖的樹為範本，我們慢慢地在程式中將樹建立出來。

public static void main(String[] args) {
    TreeNode<Integer> node1 = new TreeNode<>(1);
    TreeNode<Integer> node3 = new TreeNode<>(3);
    TreeNode<Integer> node2 = new TreeNode<>(2);
    node2.setLeftNode(node1);
    node2.setRightNode(node3);

    TreeNode<Integer> node5 = new TreeNode<>(5);
    TreeNode<Integer> node7 = new TreeNode<>(7);
    TreeNode<Integer> node6 = new TreeNode<>(6);
    node6.setLeftNode(node5);
    node6.setRightNode(node7);

    TreeNode<Integer> node4 = new TreeNode<>(4);
    node4.setLeftNode(node2);
    node4.setRightNode(node6);
}

三、二元樹的走訪

讀者可以聯想一下陣列與鏈結串列這兩個資料結構，只要知道第一個元素或節點的起始位址，就能一路走到最後一個，它們屬於線性的資料結構。但樹狀結構就不一樣了，由於每個樹節點可能指向不只一個子節點，因此會有「分岔」，無法一條路就通過所有節點。

二元樹的走訪（traversal）是拜訪樹中每個節點一次，就像防毒軟體會徹底經過全部的資料夾，掃描其中的檔案。

上圖是個簡單的二元樹，「中」為根節點，「左」為左節點，「右」為右節點。其走訪方式分為「前序」（preorder）、「中序」（inorder）與「後序」（postorder）三種。以下將會以第二節的二元樹為對象，也就是下圖，示範走訪的過程。

為了實作二元樹走訪，請在 TreeNode 類別，宣告以下三個走訪方法 。

public class TreeNode<E> {  
    // 其餘略過

    public void preOrder() {
        // TODO
    }

    public void inOrder() {
        // TODO
    }

    public void postOrder() {
        // TODO
    }
}

前序走訪的順序是「中左右」，根節點固定是第一個走訪到的。結果為：4、2、1、3、6、5、7。以下是範例程式。

public void preOrder() {
    System.out.print(value);

    if (leftNode != null) {
        leftNode.preOrder();
    }

    if (rightNode != null) {
        rightNode.preOrder();
    }
}

中序走訪的順序是「左中右」，結果為：1、2、3、4、5、6、7。以下是範例程式。

public void inOrder() {
    if (leftNode != null) {
        leftNode.inOrder();
    }

    System.out.print(value);

    if (rightNode != null) {
        rightNode.inOrder();
    }
}
後序走訪的順序是「左右中」，根節點是最後一個走訪到的。結果為：1、3、2、5、7、6、4。以下是範例程式。 

public void postOrder() {
    if (leftNode != null) {
        leftNode.postOrder();
    }

    if (rightNode != null) {
        rightNode.postOrder();
    }

    System.out.print(value);
}

讀者只要知道，根節點的拜訪順位分別是前、中、後，而另外兩個節點固定是先左再右，就會更好記住。以下是方法的使用方式與執行結果。

public static void main(String[] args) {
    // 其餘略過

    node4.preOrder();
    System.out.println();
    node4.inOrder();
    System.out.println();
    node4.postOrder();
}
 

留言

張貼留言