# 第六章 樹的遍歷
> 原文：[Chapter 6 Tree traversal](http://greenteapress.com/thinkdast/html/thinkdast007.html)
> 譯者：[飛龍](https://github.com/wizardforcel)
> 協議：[CC BY-NC-SA 4.0](http://creativecommons.org/licenses/by-nc-sa/4.0/)
> 自豪地采用[谷歌翻譯](https://translate.google.cn/)
本章將介紹一個 Web 搜索引擎，我們將在本書其余部分開發它。我描述了搜索引擎的元素，并介紹了第一個應用程序，一個從維基百科下載和解析頁面的 Web 爬行器。本章還介紹了深度優先搜索的遞歸實現，以及迭代實現，它使用 Java`Deque`實現“后入先出”的棧。
## 6.1 搜索引擎
網絡搜索引擎，像谷歌搜索或 Bing，接受一組“檢索項”，并返回一個網頁列表，它們和這些項相關（之后我將討論“相關”是什么意思）。你可以在 <http://thinkdast.com/searcheng> 上閱讀更多內容，但是我會解釋你需要什么。
搜索引擎的基本組成部分是：
抓取：我們需要一個程序，可以下載網頁，解析它，并提取文本和任何其他頁面的鏈接。
索引：我們需要一個數據結構，可以查找一個檢索項，并找到包含它的頁面。
檢索：我們需要一種方法，從索引中收集結果，并識別與檢索項最相關的頁面。
我們以爬蟲開始。爬蟲的目標是查找和下載一組網頁。對于像 Google 和 Bing 這樣的搜索引擎，目標是查找所有網頁，但爬蟲通常僅限于較小的域。在我們的例子中，我們只會讀取維基百科的頁面。
作為第一步，我們將構建一個讀取維基百科頁面的爬蟲，找到第一個鏈接，并跟著鏈接來到另一個頁面，然后重復。我們將使用這個爬蟲來測試“到達哲學”的猜想，它是：
> 點擊維基百科文章正文中的第一個小寫的鏈接，然后對后續文章重復這個過程，通常最終會到達“哲學”的文章。
這個猜想在 <http://thinkdast.com/getphil> 中闡述，你可以閱讀其歷史。
測試這個猜想需要我們構建爬蟲的基本部分，而不必爬取整個網絡，甚至是所有維基百科。而且我覺得這個練習很有趣！
在幾個章節之內，我們將處理索引器，然后我們將到達檢索器。
## 6.2 解析 HTML
當你下載網頁時，內容使用超文本標記語言（即 HTML）編寫。例如，這里是一個最小的 HTML 文檔：
```html
<!DOCTYPE html>
<html>
<head>
<title>This is a title</title>
</head>
<body>
<p>Hello world!</p>
</body>
</html>
```
短語`This is a title`和`Hello world!`是實際出現在頁面上的文字；其他元素是指示文本應如何顯示的標簽。
當我們的爬蟲下載頁面時，它需要解析 HTML，以便提取文本并找到鏈接。為此，我們將使用`jsoup`，它是一個下載和解析 HTML 的開源 Java 庫。
解析 HTML 的結果是文檔對象模型（DOM）樹，其中包含文檔的元素，包括文本和標簽。樹是由節點組成的鏈接數據結構；節點表示文本，標簽和其他文檔元素。
節點之間的關系由文檔的結構決定。在上面的例子中，第一個節點稱為根，是`<html>`標簽，它包含指向所包含兩個節點的鏈接， `<head>`和`<body>`；這些節點是根節點的子節點。
`<head>`節點有一個子節點，`<title>`，`<body>`節點有一個子節點， `<p>`（代表“段落”）。圖 6.1 以圖形方式表示該樹。
圖 6.1 簡單 HTML 頁面的 DOM 樹
每個節點包含其子節點的鏈接; 此外，每個節點都包含其父節點的鏈接，所以任何節點都可以向上或向下瀏覽樹。實際頁面的 DOM 樹通常比這個例子更復雜。
大多數網絡瀏覽器提供了工具，用于檢查你正在查看的頁面的 DOM。在 Chrome 中，你可以右鍵單擊網頁的任何部分，然后從彈出的菜單中選擇`Inspect`（檢查）。在 Firefox 中，你可以右鍵單擊并從菜單中選擇`Inspect Element`（檢查元素）。Safari 提供了一個名為 Web Inspector 的工具，你可以閱讀 <http://thinkdast.com/safari>。對于 Internet Explorer，你可以閱讀 <http://thinkdast.com/explorer> 上的說明 。
圖 6.2：Chrome DOM 查看器的截圖
圖 6.2 展示了維基百科 Java 頁面（<http://thinkdast.com/java>）的 DOM 截圖。高亮的元素是文章正文的第一段，它包含在一個`<div>`元素中 ，帶有`id="mw-content-text"`。我們將使用這個元素 ID 來標識我們下載的每篇文章的正文。
## 6.3 使用`jsoup`
`jsoup`非常易于下載，和解析 Web 頁面，以及訪問 DOM 樹。這里是一個例子：
```java
String url = "http://en.wikipedia.org/wiki/Java_(programming_language)";
// download and parse the document
Connection conn = Jsoup.connect(url);
Document doc = conn.get();
// select the content text and pull out the paragraphs.
Element content = doc.getElementById("mw-content-text");
Elements paragraphs = content.select("p");
```
`Jsoup.connect`接受`String`形式的`url`，并連接 Web 服務器。`get`方法下載 HTML，解析，并返回`Document`對象，他表示 DOM。
`Document`提供了導航樹和選擇節點的方法。其實它提供了很多方法，可能會把人搞暈。此示例演示了兩種選擇節點的方式：
+ `getElementById`接受`String`并在樹中搜索匹配`id`字段的元素。在這里，它選擇節點`<div id="mw-content-text" lang="en" dir="ltr" class="mw-content-ltr">`，它出現在每個維基頁面上，來確定包含文章正文的`<div>`元素，而不是導航邊欄和其他元素。`getElementById`的返回值是一個`Element`對象，代表這個`<div>`，并包含`<div>`中的元素作為后繼節點。
+ `select`接受`String`，遍歷樹，并返回與所有元素，它的標簽與`String`匹配。在這個例子中，它返回所有`content`中的段落標簽。返回值是一個`Elements`對象。
> 譯者注：`select`方法接受 CSS 選擇器，不僅僅能按照標簽選擇。請見 <https://jsoup.org/apidocs/org/jsoup/select/Selector.html>。
在你繼續之前，你應該仔細閱讀這些類的文檔，以便知道他們能做什么。最重要的類是`Element`，`Elements`和`Node`，你可以閱讀 <http://thinkdast.com/jsoupelt>，<http://thinkdast.com/jsoupelts> 和 <http://thinkdast.com/jsoupnode>。
`Node`表示 DOM 樹中的一個節點；有幾個擴展`Node`的子類，其中包括 `Element`，`TextNode`，`DataNode`，和`Comment`。`Elements`是`Element`對象的`Collection`。
圖 6.3：被選類的 UML 圖，由`jsoup`提供。編輯：<ttp://yuml.me/edit/4bc1c919>
圖 6.3 是一個 UML 圖，展示了這些類之間的關系。在 UML 類圖中，帶有空心箭頭的線表示一個類繼承另一個類。例如，該圖表示`Elements`繼承`ArrayList`。我們將在第 11.6 節中再次接觸 UML 圖。
## 6.4 遍歷 DOM
為了使你變得更輕松，我提供了一個`WikiNodeIterable`類，可以讓你遍歷 DOM 樹中的節點。以下是一個示例，展示如何使用它：
```java
Elements paragraphs = content.select("p");
Element firstPara = paragraphs.get(0);
Iterable<Node> iter = new WikiNodeIterable(firstPara);
for (Node node: iter) {
if (node instanceof TextNode) {
System.out.print(node);
}
}
```
這個例子緊接著上一個例子。它選擇`paragraphs`中的第一個段落，然后創建一個`WikiNodeIterable`，它實現`Iterable<Node>`。`WikiNodeIterable`執行“深度優先搜索”，它按照它們將出現在頁面上的順序產生節點。
在這個例子中，僅當`Node`是`TextNode`時，我們打印它，并忽略其他類型的`Node`，特別是代表標簽的`Element`對象。結果是沒有任何標記的 HTML 段落的純文本。輸出為：
```
Java is a general-purpose computer programming language that is concurrent, class-based, object-oriented,[13] and specifically designed …
```
> Java 是一種通用的計算機編程語言，它是并發的，基于類的，面向對象的，[13] 和特地設計的...
## 6.5 深度優先搜索
有幾種方式可以合理地遍歷一個樹，每個都有不同的應用。我們從“深度優先搜索”（DFS）開始。DFS 從樹的根節點開始，并選擇第一個子節點。如果子節點有子節點，則再次選擇第一個子節點。當它到達沒有子節點的節點時，它回溯，沿樹向上移動到父節點，在那里它選擇下一個子節點，如果有的話；否則它會再次回溯。當它探索了根節點的最后一個子節點，就完成了。
有兩種常用的方式來實現 DFS，遞歸和迭代。遞歸實現簡單優雅：
```java
private static void recursiveDFS(Node node) {
if (node instanceof TextNode) {
System.out.print(node);
}
for (Node child: node.childNodes()) {
recursiveDFS(child);
}
}
```
這個方法對樹中的每一個`Node`調用，從根節點開始。如果`Node`是一個`TextNode`，它打印其內容。如果`Node`有任何子節點，它會按順序在每一個子節點上調用`recursiveDFS`。
在這個例子中，我們在遍歷子節點之前打印每個`TextNode`的內容，所以這是一個“前序”遍歷的例子。你可以在 <http://thinkdast.com/treetrav> 上了解“前序”，“后序”和“中序”遍歷。對于此應用程序，遍歷順序并不重要。
通過進行遞歸調用，`recursiveDFS`使用調用棧（<http://thinkdast.com/callstack>）來跟蹤子節點并以正確的順序處理它們。作為替代，我們可以使用棧數據結構自己跟蹤節點；如果我們這樣做，我們可以避免遞歸并迭代遍歷樹。
## 6.6 Java 中的棧
在我解釋 DFS 的迭代版本之前，我將解釋棧數據結構。我們將從棧的一般概念開始，我將使用小寫`s`指代“棧”。然后我們將討論兩個 Java`interfaces`，它們定義了棧的方法：`Stack`和`Deque`。
棧是與列表類似的數據結構：它是維護元素順序的集合。棧和列表之間的主要區別是棧提供的方法較少。在通常的慣例中，它提供：
`push`：它將一個元素添加到棧頂。
`pop`：它從棧中刪除并返回最頂部的元素。
`peek`：它返回最頂部的元素而不修改棧。
`isEmpty`：表示棧是否為空。
因為`pop`總是返回最頂部的元素，棧也稱為 LIFO，代表“后入先出”。棧的替代品是“隊列”，它返回的元素順序和添加順序相同；即“先入先出（FIFO）。
為什么棧和隊列是有用的，可能不是很明顯：它們不提供任何列表沒有的功能；實際上它們提供的功能更少。那么為什么不使用列表的一切？有兩個原因：
+ 如果你將自己限制于一小部分方法 - 也就是小型 API - 你的代碼將更加易讀，更不容易出錯。例如，如果使用列表來表示棧，則可能會以錯誤的順序刪除元素。使用棧 API，這種錯誤在字面上是不可能的。避免錯誤的最佳方法是使它們不可能。
+ 如果一個數據結構提供了小型 API，那么它更容易實現。例如，實現棧的簡單方法是單鏈表。當我們壓入一個元素時，我們將它添加到列表的開頭；當我們彈出一個元素時，我們在開頭刪除它。對于鏈表，在開頭添加和刪除是常數時間的操作，因此這個實現是高效的。相反，大型 API 更難實現高效。
為了在 Java 中實現棧，你有三個選項：
+ 繼續使用`ArrayList`或`LinkedList`。如果使用`ArrayList`，請務必從最后添加和刪??除，這是一個常數時間的操作。并且小心不要在錯誤的地方添加元素，或以錯誤的順序刪除它們。
+ Java 提供了一個`Stack`類，它提供了一組標準的棧方法。但是這個類是 Java 的一個舊部分：它與 Java 集合框架不兼容，后者之后才出現。
+ 最好的選擇可能是使用`Deque`接口的一個實現，如`ArrayDeque`。
`Deque`代表“雙向隊列”；它應該被發音為“deck”，但有些人叫它“deek”。在 Java 中， `Deque`接口提供`push`，`pop`，`peek`和`isEmpty`，因此你可以將`Deque`用作棧。它提供了其他方法，你可以閱讀 <http://thinkdast.com/deque>，但現在我們不會使用它們。
## 6.7 迭代式 DFS
這里是 DFS 的迭代版本，它使用`ArrayDeque`來表示`Node`對象的棧。
```java
private static void iterativeDFS(Node root) {
Deque<Node> stack = new ArrayDeque<Node>();
stack.push(root);
while (!stack.isEmpty()) {
Node node = stack.pop();
if (node instanceof TextNode) {
System.out.print(node);
}
List<Node> nodes = new ArrayList<Node>(node.childNodes());
Collections.reverse(nodes);
for (Node child: nodes) {
stack.push(child);
}
}
}
```
參數`root`是我們想要遍歷的樹的根節點，所以我們首先創建棧并將根節點壓入它。
循環持續到棧為空。每次迭代，它會從棧中彈出`Node`。如果它得到`TextNode`，它打印內容。然后它把子節點們壓棧。為了以正確的順序處理子節點，我們必須以相反的順序將它們壓棧; 我們通過將子節點復制成一個`ArrayList`，原地反轉元素，然后遍歷反轉的`ArrayList`。
DFS 的迭代版本的一個優點是，更容易實現為 Java`Iterator`；你會在下一章看到如何實現。
但是首先，有一個`Deque`接口的最后的注意事項：除了`ArrayDeque`，Java 提供另一個`Deque`的實現，我們的老朋友`LinkedList`。`LinkedList`實現兩個接口，`List`和`Deque`（還有`Queue`）。你得到哪個接口，取決于你如何使用它。例如，如果將`LinkedList`對象賦給`Deque`變量，如下所示：
```java
Deqeue<Node> deque = new LinkedList<Node>();
```
你可以使用`Deque`接口中的方法，但不是所有`List`中的方法。如果你將其賦給`List`變量，像這樣：
```java
List<Node> deque = new LinkedList<Node>();
```
你可以使用`List`接口中的方法，但不是所有`Deque`中的方法。并且如果像這樣賦值：
```java
LinkedList<Node> deque = new LinkedList<Node>();
```
你可以使用所有方法，但是混合了來自不同接口的方法。你的代碼會更不可讀，并且更易于出錯。
