樹狀結構是一種能夠儲存具有「階層」關係的資料的結構，實際應用包含現實生活中的組織架構圖，或是電腦中的檔案總管等等。本文會先解說樹狀結構是什麼，接著使用 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() {後序走訪的順序是「左右中」，根節點是最後一個走訪到的。結果為：1、3、2、5、7、6、4。以下是範例程式。
if (leftNode != null) {
leftNode.inOrder();
}
System.out.print(value);
if (rightNode != null) {
rightNode.inOrder();
}
}
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();
}
留言
張貼留言