数据结构思维 第六章 树的遍历
第六章 樹的遍歷
原文：Chapter 6 Tree traversal
譯者：飛龍
協議：CC BY-NC-SA 4.0
自豪地采用谷歌翻譯
本章將介紹一個 Web 搜索引擎，我們將在本書其余部分開發它。我描述了搜索引擎的元素，并介紹了第一個應用程序，一個從維基百科下載和解析頁面的 Web 爬行器。本章還介紹了深度優先搜索的遞歸實現，以及迭代實現，它使用 JavaDeque實現“后入先出”的棧。
6.1 搜索引擎
網絡搜索引擎，像谷歌搜索或 Bing，接受一組“檢索項”，并返回一個網頁列表，它們和這些項相關（之后我將討論“相關”是什么意思）。你可以在 http://thinkdast.com/searcheng 上內容，但是我會解釋你需要什么。
搜索引擎的基本組成部分是：
抓取：我們需要一個程序，可以下載網頁，解析它，并提取文本和任何其他頁面的鏈接。
索引：我們需要一個數據結構，可以查找一個檢索項，并找到包含它的頁面。
檢索：我們需要一種方法，從索引中收集結果，并識別與檢索項最相關的頁面。
我們以爬蟲開始。爬蟲的目標是查找和下載一組網頁。對于像 Google 和 Bing 這樣的搜索引擎，目標是查找所有網頁，但爬蟲通常僅限于較小的域。在我們的例子中，我們只會讀取維基百科的頁面。
作為第一步，我們將構建一個讀取維基百科頁面的爬蟲，找到第一個鏈接，并跟著鏈接來到另一個頁面，然后重復。我們將使用這個爬蟲來測試“到達哲學”的猜想，它是：
點擊維基百科文章正文中的第一個小寫的鏈接，然后對后續文章重復這個過程，通常最終會到達“哲學”的文章。
這個猜想在 http://thinkdast.com/getphil 中闡述，你可以閱讀其歷史。
測試這個猜想需要我們構建爬蟲的基本部分，而不必爬取整個網絡，甚至是所有維基百科。而且我覺得這個練習很有趣！
在幾個章節之內，我們將處理索引器，然后我們將到達檢索器。
6.2 解析 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 樹。這里是一個例子：
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提供。編輯：
6.4 遍歷 DOM
為了使你變得更輕松，我提供了一個WikiNodeIterable類，可以讓你遍歷 DOM 樹中的節點。以下是一個示例，展示如何使用它：
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，遞歸和迭代。遞歸實現簡單優雅：
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指代“棧”。然后我們將討論兩個 Javainterfaces，它們定義了棧的方法：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對象的棧。
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 的迭代版本的一個優點是，更容易實現為 JavaIterator；你會在下一章看到如何實現。
但是首先，有一個Deque接口的最后的注意事項：除了ArrayDeque，Java 提供另一個Deque的實現，我們的老朋友LinkedList。LinkedList實現兩個接口，List和Deque（還有Queue）。你得到哪個接口，取決于你如何使用它。例如，如果將LinkedList對象賦給Deque變量，如下所示：
Deqeue<Node> deque = new LinkedList<Node>();你可以使用Deque接口中的方法，但不是所有List中的方法。如果你將其賦給List變量，像這樣：
List<Node> deque = new LinkedList<Node>();你可以使用List接口中的方法，但不是所有Deque中的方法。并且如果像這樣賦值：
LinkedList<Node> deque = new LinkedList<Node>();你可以使用所有方法，但是混合了來自不同接口的方法。你的代碼會更不可讀，并且更易于出錯。
總結
以上是生活随笔為你收集整理的数据结构思维 第六章 树的遍历的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 你以为A10 Networks只做应用交
- 下一篇： 比世界纪录快3倍 阿里云377秒完成10