Java 之道/樹
tree ADT data structure
本章介紹了一種新的資料結構，稱為樹，它的一些用途和兩種實現方法。
一個可能的混淆來源是 ADT、資料結構和 ADT 或資料結構實現之間的區別。沒有通用的答案，因為在某一級是 ADT 的東西可能反過來是另一個 ADT 的實現。
diagram!implementation
為了幫助理清其中的一些內容，有時在 ADT 及其可能實現之間繪製一個圖表以顯示其關係是有用的。此圖顯示了樹的兩種實現方法
figure=figs/tree_adt.eps
圖中的水平線代表 ADT 及其實現之間的抽象屏障。
node tree node cargo embedded reference implementation!Tree binary tree
與列表一樣，樹由節點組成。一種常見的樹是二叉樹，其中每個節點都包含對另外兩個節點（可能為空）的引用。類定義如下所示
verbatim public class Tree
Object cargo; Tree left, right;
verbatim
與列表節點一樣，樹節點包含貨物：在本例中是一個泛型物件。其他例項變數分別命名為 left 和 right，符合表示樹的標準圖形方式
figure=figs/tree1.eps
樹的頂部（由樹引用的節點）稱為根。為了符合樹的隱喻，其他節點被稱為分支，具有空引用的尖端節點被稱為葉子。我們可能覺得將根部繪製在頂部，葉子繪製在底部很奇怪，但這不是最奇怪的事情。
root node leaf node parent node child node level
更糟糕的是，計算機科學家將另一個隱喻混雜在一起：家譜。頂端節點有時被稱為父節點，它引用的節點被稱為其子節點。具有相同父節點的節點稱為兄弟節點，等等。
最後，還有一種幾何詞彙用於描述樹。我已經提到了 left 和 right，但也有“向上”（朝向父節點/根節點）和“向下”（朝向子節點/葉子）。另外，所有與根節點距離相同的節點構成了樹的一層。
我不知道為什麼我們需要三種隱喻來描述樹，但事實就是這樣。
tree!linked implementation
組裝樹節點的過程類似於組裝列表的過程。我們有一個用於樹節點的建構函式，用於初始化例項變數。
verbatim
public Tree (Object cargo, Tree left, Tree right)
this.cargo = cargo;
this.left = left;
this.right = right;
verbatim
我們首先分配子節點
verbatim
Tree left = new Tree (new Integer(2), null, null); Tree right = new Tree (new Integer(3), null, null);
verbatim
我們可以同時建立父節點並將其連結到子節點
verbatim
Tree tree = new Tree (new Integer(1), left, right);
verbatim
此程式碼產生了上一圖所示的狀態。
tree!traversal traverse
遍歷樹的最自然方法是遞迴。例如，要將樹中的所有整數加起來，我們可以編寫此類方法
verbatim
public static int total (Tree tree)
if (tree == null) return 0;
Integer cargo = (Integer) tree.cargo;
return cargo.intValue() + total (tree.left) + total (tree.right);
verbatim
這是一個類方法，因為我們希望使用 null 來表示空樹，並將空樹作為遞迴的基準情況。如果樹為空，則該方法返回 0。否則，它進行兩次遞迴呼叫以找到其兩個子節點的總值。最後，它添加了自己的貨物並返回總值。
tree!empty
雖然此方法有效，但在將其適應面向物件設計方面存在一些困難。它不應出現在 Tree 類中，因為它要求貨物是 Integer 物件。如果我們在 Tree.java 中做出這種假設，那麼我們將失去泛型資料結構的優勢。
另一方面，此程式碼訪問了 Tree 節點的例項變數，因此它“知道”它應該知道的比樹的實現更多。如果我們稍後更改該實現（我們將這樣做），此程式碼將失效。
在本章的後面，我們將開發解決此問題的方法，允許客戶端程式碼遍歷包含任何型別物件的樹，而不會破壞客戶端程式碼和實現之間的抽象屏障。在我們到達那裡之前，讓我們先看看樹的應用。
tree!expression expression tree postfix infix
樹是表示表示式結構的自然方式。與其他表示法不同，它可以明確地表示計算。例如，中綴表示式 1 + 2 * 3 是模糊的，除非我們知道乘法在加法之前發生。
下圖表示相同的計算
figure=figs/tree2.eps
節點可以是運算元，如 1 和 2，也可以是運算子，如 + 和 *。運算元是葉子節點；運算子節點包含對其運算元的引用（所有這些運算子都是二元的，意味著它們正好有兩個運算元）。
檢視此圖，毫無疑問操作順序是什麼：乘法首先發生以計算加法的第一個運算元。
像這樣的表示式樹有許多用途。我們將要檢視的示例是從一種格式（字尾）到另一種格式（中綴）的轉換。編譯器內部使用類似的樹來解析、最佳化和轉換程式。
tree!traversal traverse recursion preorder postorder inorder
我已經指出遞迴提供了一種遍歷樹的自然方法。我們可以像這樣打印表達式樹的內容
verbatim
public static void print (Tree tree)
if (tree == null) return;
System.out.print (tree + " ");
print (tree.left);
print (tree.right);
verbatim
換句話說，要列印一棵樹，首先列印根節點的內容，然後列印整個左子樹，最後列印整個右子樹。這種遍歷樹的方法稱為前序遍歷，因為根節點的內容出現在子節點內容之前。
對於示例表示式，輸出為 + 1 * 2 3。這與字尾和中綴都不同；這是一種稱為字首的新表示法，其中運算子出現在其運算元之前。
你可能懷疑，如果我們以不同的順序遍歷樹，我們將獲得不同表示法的表示式。例如，如果我們先列印子樹，然後列印根節點
verbatim
public static void printPostorder (Tree tree)
if (tree == null) return;
printPostorder (tree.left);
printPostorder (tree.right);
System.out.print (tree + " ");
verbatim
我們得到字尾表示式 (1 2 3 * +)! 正如之前方法的名稱所暗示的那樣，這種遍歷順序稱為後序遍歷。最後，要按中序遍歷樹，我們先列印左樹，然後列印根節點，最後列印右樹
verbatim
public static void printInorder (Tree tree)
if (tree == null) return;
printInorder (tree.left);
System.out.print (tree + " ");
printInorder (tree.right);
verbatim
結果為 1 + 2 * 3，這是中綴表示式。
公平地說，我必須指出我省略了一個重要的複雜情況。有時當我們在中綴表示式中編寫表示式時，我們必須使用括號來保留操作順序。因此，中序遍歷不足以生成中綴表示式。
然而，經過一些改進，表示式樹和三種遞迴遍歷提供了一種通用的方法，用於將表示式從一種格式轉換為另一種格式。
encapsulation client provider abstract class class!abstract
正如我之前提到的，我們一直用來遍歷樹的方式存在問題：它打破了客戶端程式碼（使用樹的應用程式）和提供者程式碼（樹實現）之間的界限。理想情況下，樹程式碼應該是通用的；它不應該瞭解表示式樹的任何資訊。生成和遍歷表示式樹的程式碼不應該瞭解樹的實現。這種設計準則被稱為物件封裝，以區別於我們在封裝一節中看到的封裝，我們可能將其稱為方法封裝。
在當前版本中，樹程式碼瞭解太多關於客戶端的資訊。相反，樹類應該提供以各種方式遍歷樹的通用功能。在遍歷時，它應該對每個節點執行由客戶端指定的運算。
Visitable abstract class!Visitable
為了促進這種利益分離，我們將建立一個新的抽象類，名為 Visitable。儲存在樹中的項將被要求是可訪問的，這意味著它們定義了一個名為 visit 的方法，該方法執行客戶端希望對每個節點執行的操作。這樣，樹就可以執行遍歷，而客戶端就可以執行節點運算。
以下是我們在客戶端和提供者之間插入抽象類需要執行的步驟
列舉
定義一個抽象類，指定提供者程式碼需要在其元件上呼叫的方法。
根據新的抽象類編寫提供者程式碼，而不是泛型物件。
定義一個屬於抽象類的具體類，並根據客戶端的要求實現所需的方法。
編寫客戶端程式碼以使用新的具體類。
列舉
接下來的幾節將演示這些步驟。
定義抽象類
[edit | edit source]abstract class!defining interface
抽象類定義看起來很像具體類定義，只是它只指定每個方法的介面，而不是實現。Visitable 的定義是
逐字 public interface Visitable
public void visit ();
verbatim
就是這樣！關鍵字 interface 是 Java 中抽象類的關鍵字。visit 的定義看起來像任何其他方法定義，只是它沒有主體。此定義指定任何實現 Visitable 的類都必須具有一個名為 visit 的方法，該方法不接受任何引數並返回 void。
body!method
與其他類定義一樣，抽象類定義位於與類同名的檔案中（在本例中為 Visitable.java）。
實現抽象類
[edit | edit source]abstract class!implementing Token class class!Token
如果我們使用表示式樹來生成中綴，那麼訪問節點意味著列印其內容。由於表示式樹的內容是標記，我們將建立一個名為 Token 的新具體類，該類實現 Visitable
逐字 public class Token implements Visitable
String str;
public Token (String str)
this.str = str;
public void visit ()
System.out.print (str + " ");
verbatim
當我們編譯此類定義（位於名為 Token.java 的檔案中）時，編譯器會檢查提供的方法是否滿足抽象類指定的條件。如果沒有，它將生成錯誤訊息。例如，如果我們拼寫錯誤應該為 visit 的方法的名稱，我們可能會得到類似“類 Token 必須宣告為抽象類。它沒有定義來自介面 Visitable 的 void visit()。”的東西。
下一步是修改解析器，以便將 Token 物件放入樹中，而不是字串。這裡有一個小例子
verbatim
String expr = "1 2 3 * +"; StringTokenizer st = new StringTokenizer (expr, " +-*/", true); String token = st.nextToken(); Tree tree = new Tree (new Token (token), null, null));
verbatim
此程式碼獲取字串中的第一個標記，將其包裝在 Token 物件中，然後將 Token 放入樹節點中。如果樹要求貨物是可訪問的，它將轉換 Token 以成為可訪問的物件。當我們從樹中移除 Visitable 時，我們將不得不將其強制轉換為 Token。
作為練習，編寫一個名為 visitPreorder 的 printPreorder 版本，該版本遍歷樹並按前序在每個節點上呼叫 visit。
樹的陣列實現
[edit | edit source]tree!array implementation implementation!Tree ADT!Tree
實現樹意味著什麼？到目前為止，我們只看到了樹的一種實現，一種類似於連結串列的連結資料結構。但是，我們想要識別的還有其他結構。任何能夠執行基本樹操作集的東西都應該被識別為樹。
那麼樹操作是什麼呢？換句話說，我們如何定義樹 ADT？
描述
[建構函式：] 構建一棵空樹。
[isEmpty：] 這棵樹是空樹嗎？
[getLeft：] 返回此節點的左孩子。
[getRight：] 返回此節點的左孩子。
[getParent：] 返回此節點的父節點。
[getCargo：] 從此節點返回貨物物件。
[setCargo：] 為此節點分配一個貨物物件（如果需要，建立該節點）。
描述
在我們看到的實現中，空樹由特殊值 null 表示。getLeft 和 getRight 透過訪問節點的例項變數來執行，getCargo 和 setCargo 也是如此。我們還沒有實現 getParent（你可以考慮如何實現它）。
樹的另一種實現使用陣列和索引，而不是物件和引用。為了瞭解它的工作原理，我們將從檢視同時使用陣列和物件的混合實現開始。
此圖顯示了一棵類似於我們一直在檢視的樹，儘管它是橫向排列的，根在左邊，葉在右邊。在底部，有一個引用陣列，引用樹中的物件。貨物物件表示為 null 引用。
圖=figs/tree3.eps，寬度=5in
你可能會注意到，陣列索引 1 指向根節點，而陣列索引 0 是空的。原因很快就會變得清晰。
所以現在我們有一棵樹，其中每個節點都有一個唯一的索引。此外，索引已根據特定模式分配給節點，以實現以下結果
列舉
索引為 的節點的左孩子索引為 。
索引為 的節點的右孩子索引為 。
索引為 的節點的父節點索引為 （向下取整）。
列舉
使用這些公式，我們可以僅透過進行算術運算來實現 getLeft、getRight 和 getParent；我們不必使用引用！
由於我們不使用引用，我們可以刪除它們，這意味著以前是樹節點的東西現在只是貨物，沒有其他東西。這意味著我們可以將樹實現為貨物物件的陣列；我們根本不需要樹節點。
以下是一些實現的示例
verbatim public class Tree
Object[] array; int i;
public Tree ()
array = new Object [128];
i = 1;
public Tree (Object[] array, int i)
this.array = array;
this.i = i;
verbatim
到目前為止沒有驚喜。例項變數是物件陣列和一個整數，表示在陣列中找到新節點的位置。
第一個建構函式使用任意初始大小初始化陣列（我們以後可以隨時調整它的大小）。第二個建構函式假設物件陣列已經存在。構成樹的所有節點都將共享同一個陣列，並具有不同的 i 值。
我們使用 i 來訪問給定節點的貨物
verbatim
public Object getCargo ()
if (i >= array.length) return null;
return array[i];
public void setCargo (Object obj)
if (i >= array.length)
array = resize (array);
array[i] = obj;
verbatim
兩種方法都必須檢查陣列的長度。如果 getCargo 嘗試訪問陣列中不存在的元素，它將返回 null 以指示空樹。如果 getCargo 超過陣列的長度，它將調整陣列的大小以騰出空間（有關 resize 的可能實現，請參見 resize 一節）。
要檢查節點是否是空樹，我們將檢查貨物是否為 null。
verbatim
public boolean empty ()
return (getCargo() == null);
verbatim
getLeft、getRight 和 getParent 的實現只是算術運算
verbatim
public Tree getLeft ()
return new Tree (array, 2*i);
public Tree getRight ()
return new Tree (array, 2*i + 1);
public Tree parent ()
return new Tree (array, i/2);
verbatim
最後，我們準備構建一棵樹。在另一個類（客戶端）中，我們將編寫
verbatim
Tree tree = new Tree ();
tree.setCargo ("cargo for root");
verbatim
建構函式構建一棵空樹。呼叫 setCargo 會將字串“根的貨物”放入根節點中。
要向根節點新增子節點
verbatim
tree.getLeft().setCargo ("cargo for left");
tree.getRight().setCargo ("cargo for right");
verbatim
在樹類中，我們可以提供一個按前序列印樹內容的方法。
verbatim
public void print ()
if (isEmpty ()) return;
System.out.println (array[i]);
getLeft().print();
getRight().print();
verbatim
透過將根作為引數傳遞，我們從客戶端呼叫此方法。
verbatim
tree.print (root);
verbatim
輸出為
逐字 貨物為根 貨物為左 貨物為右 逐字
此實現提供了定義樹的基本操作。正如我指出的那樣，樹的連結實現提供了相同的操作，但語法不同。作為練習，修改連結樹，使其實現 Tree ADT。
陣列實現的一個問題是陣列的初始大小是任意的，可能需要調整它的大小。最後一個問題可以透過用 Vector 替換陣列來解決。
Vector 類
[edit | edit source]向量
Vector class class!Vector
Vector 是 java.util 包中的內建 Java 類。它是物件陣列的實現，具有自動調整自身大小的附加功能，因此我們不必這樣做。
Vector 類提供名為 get 和 set 的方法，類似於我們為 Tree 類編寫的 getCargo 和 setCargo 方法。你應該透過查閱線上文件來回顧其他 Vector 操作。
在使用 Vector 類之前，你應該瞭解一些概念。每個 Vector 都有一個容量，它表示分配用於儲存值的儲存空間量，還有一個大小，它表示實際上在向量中的值數量。
下圖是一個簡單的向量圖，它包含三個元素，但容量為七。
figure=figs/vector.eps
一般來說，在呼叫 set 或 get 之前，由客戶端程式碼確保向量具有足夠的大小。如果嘗試訪問不存在的元素（在本例中是索引為 3 到 6 的元素），將收到一個 ArrayIndexOutOfBounds 異常。
exception!ArrayIndexOutOfBounds ArrayIndexOutOfBounds
向量方法 add 和 insert 會自動增加向量的尺寸，但 set 不會。resize 方法在向量的末尾新增空元素，以達到給定尺寸。
大多數情況下，客戶端不需要擔心容量。只要向量的尺寸發生改變，容量就會自動更新。出於效能原因，某些應用程式可能希望控制此功能，這就是為什麼存在用於增加和減少容量的額外方法的原因。
由於客戶端程式碼無法訪問向量的實現，因此不清楚我們應該如何遍歷它。當然，一種可能性是使用迴圈變數作為向量中的索引。
verbatim
for (int i=0; i<v.size(); i++)
System.out.println (v.get(i));
verbatim
這沒什麼問題，但還有另一種方法可以用來演示 Iterator 類。向量提供了一個名為 iterator 的方法，該方法返回一個 Iterator 物件，使遍歷向量成為可能。
Iterator 類
[edit | edit source]iterator
Iterator class class!Iterator abstract class
Iterator 是 java.util 包中的一個抽象類。它指定了三個方法。
描述
[hasNext:] 此迭代還有更多元素嗎？
[next:] 返回下一個元素，如果不存在，則丟擲異常。
[remove:] 從集合中刪除最後返回的元素。
描述
以下示例使用迭代器遍歷並列印向量的元素。
verbatim
Iterator iterator = vector.iterator ();
while (iterator.hasNext ())
System.out.println (iterator.next ());
verbatim
一旦建立了 Iterator，它就成為與原始 Vector 分開的物件。Vector 中的後續更改不會反映在 Iterator 中。事實上，如果在建立 Iterator 後修改 Vector，則 Iterator 將失效。如果再次訪問 Iterator，它將導致 ConcurrentModification 異常。
exception!ConcurrentModification ConcurrentModification
在前面的部分中，我們使用 Visitable 抽象類允許客戶端遍歷資料結構，而無需瞭解其實現的詳細資訊。迭代器提供了另一種執行相同操作的方法。在第一種情況下，提供者執行迭代並呼叫客戶端程式碼來``訪問每個元素。在第二種情況下，提供者向客戶端提供一個物件，客戶端可以使用它來一次選擇一個元素（儘管順序由提供者控制）。
作為練習，編寫一個名為 PreIterator 的具體類，它實現 Iterator 介面，併為 Tree 類編寫一個名為 preorderIterator 的方法，該方法返回一個 PreIterator，它以先序選擇 Tree 的元素。
詞彙表
[edit | edit source]binary tree root node leaf node parent node child node level prefix preorder postorder inorder class variable encapsulation
描述
[二叉樹:] 一棵樹，其中每個節點引用 0、1 或 2 個依賴節點。
[根:] 樹中最頂端的節點，其他節點不引用它。
[葉子:] 樹中最底部的節點，它不引用其他節點。
[父節點:] 引用給定節點的節點。
[子節點:] 節點引用的節點之一。
[層級:] 與根節點距離相等的節點集。
[字首表示法:] 一種編寫數學表示式的方法，其中每個運算子都出現在其運算元之前。
[先序:] 遍歷樹的一種方式，在訪問子節點之前訪問每個節點。
[後序:] 遍歷樹的一種方式，在訪問節點本身之前訪問每個節點的子節點。
[中序:] 遍歷樹的一種方式，先訪問左子樹，然後訪問根節點，最後訪問右子樹。
[類變數:] 在任何方法之外宣告的靜態變數。它可以從任何方法訪問。
[二元運算子:] 接受兩個運算元的運算子。
[物件封裝:] 將兩個物件的實現儘可能分離的設計目標。兩個類都不應該知道另一個類的實現細節。
[方法封裝:] 將方法的介面與其實現細節分離的設計目標。
描述