【译】数据结构中关于树的一切（java版）
你每天都那么努力，忍受了那么多的寂寞和痛苦。可我也沒見你有多優秀。
https://user-gold-cdn.xitu.io/2018/4/17/162d1b4c1dd95fa3?w=1080&h=1080&f=jpeg&s=191088當我還是一個年輕男孩的時候畫的一張關于樹的畫。
當你第一次學習編碼時，大部分人都是將數組作為主要數據結構來學習。
之后，你將會學習到哈希表。如果你是計算機專業的，你肯定需要選修一門數據結構的課程。上課時，你又會學習到鏈表，隊列和棧等數據結構。這些都被統稱為線性的數據結構，因為它們在邏輯上都有起點和終點。
當你開始學習樹和圖的數據結構時，你會覺得它是如此的混亂。因為它的存儲方式不是線性的，它們都有自己特定的方式存儲數據。
這篇文章幫助你更好的理解樹形數據結構并盡可能的幫你解決你的疑問。本章我們將學到
- 是什么是樹？
- 一個簡單樹的例子
- 樹的術語和工作原理
- 如何在代碼中實現樹結構
定義
當學習編程時，我們更容易理解線性的數據結構而不是樹和圖的數據結構。
樹是眾所周知的非線性數據結構。它們不以線性方式存儲數據。他們按層次組織數據。
我們來舉例一個現實生活中的例子
我們所說的層次組織到底是是什么呢？
想象一下我們的家譜：祖父母，父母，子女，兄弟姐妹等等，我們通常按層次結構組織家譜。
https://user-gold-cdn.xitu.io/2018/4/17/162d1b4c1d8bd514?w=1600&h=792&f=jpeg&s=219120我的家庭族譜
上圖是我的家譜。tossico，akikazu，hitomi和takemi是我的祖父母。
Toshiaki 和 Juliana 是我的父母。
TK 、Yuji 、Bruno 和 Kaio 是我父母的孩子（我和我的兄弟們）。
另一個層次結構的例子是企業的組織結構。
https://user-gold-cdn.xitu.io/2018/4/17/162d1b4c1d51bf83?w=1600&h=900&f=jpeg&s=242151公司的結構也是是一個層次結構的例子
在 HTML 中，文檔對象模型（DOM）是樹形結構的。
https://user-gold-cdn.xitu.io/2018/4/17/162d1b4c1d86c62f?w=1600&h=900&f=jpeg&s=216336文檔對象模型（dom）
HTML 標簽包含其他的標簽。我們有一個 head 標簽和 body 標簽。這些標簽包含特點的元素。head 標簽中有 meta 和 title 標簽。body 標簽中有在用戶界面展示的標簽，如 h1 、a 、li 等等。
樹的術語定義
樹(tree)是被稱為結點(node)的實體的集合。結點通過邊(edge)連接。每個結點都包含值或數據(value/date)，并且每結節點可能有也可能沒有子結點。
https://user-gold-cdn.xitu.io/2018/4/17/162d1b4c1d6f688b?w=1600&h=900&f=jpeg&s=152343樹的首結點叫根結點（即root結點）。如果這個根結點和其他結點所連接，那么根結點是父結點(parent node，與根結點連接的是子結點（child node）。
https://user-gold-cdn.xitu.io/2018/4/17/162d1b4c1dcd4d97?w=1600&h=900&f=jpeg&s=197776所有的結點都通過邊(edge)連接。它是樹中很重要得一個概念，因為它負責管理節點之間的關系。
https://user-gold-cdn.xitu.io/2018/4/17/162d1b4c6b710864?w=1600&h=900&f=jpeg&s=178329葉子結點（leaves）是樹末端，它們沒有子結點。像真正的大樹一樣，我們可以看到樹上有根、枝干和樹葉。
https://user-gold-cdn.xitu.io/2018/4/17/162d1b4c73645dae?w=1600&h=900&f=jpeg&s=186456樹的高度(height)和深度(depth)
- 樹的高度是到葉子結點（樹末端）的長度
- 結點的深度是它到根結點的長度
術語匯總
- 根結點是樹最頂層結點
- 邊是兩個結點之間的連接
- 子結點是具有父結點的結點
- 父結點是與子結點有連接的結點
- 葉子結點是樹中沒有子結點的結點（樹得末端）
- 高度是樹到葉子結點（樹得末端）的長度
- 深度是結點到根結點的長度
二叉樹
https://user-gold-cdn.xitu.io/2018/4/17/162d1b4c751c98d5?w=1600&h=900&f=png&s=1159977現在我們來討論一個特殊的樹類型。我們把它叫作二叉樹。
“在計算機科學領域，二叉樹是一種樹形數據結構，它的每個節點最多有兩個孩子，被叫作左孩子和右孩” —? Wikipedia
我們來寫一個二叉樹
當我們要實現二叉樹時，我們需要牢記的第一件事是它是一個結點集合。每個結點都有三個屬性：value，left_child``和right_child。
那么我們怎么才能實現一個有這三個屬性的簡單二叉樹呢？
我們來實現一個二叉樹的例子
/*** Created on 2018/4/16.** @author zlf* @since 1.0*/ public class BinaryTree {public BinaryTree left; //左節點public BinaryTree right; //右節點public String data; //樹的內容public BinaryTree() {}/*** 構造方法** @param data* @param left* @param right*/public BinaryTree(String data, BinaryTree left, BinaryTree right) {this.left = left;this.right = right;this.data = data;}/*** 構造方法** @param data*/public BinaryTree(String data) {this(data, null, null);} 復制代碼好，這就是我們的二叉樹類
當我們實例化一個對象時，我們把值（點的相關數據）作為參數傳遞給類。看上面類的左孩子結點和右孩子結點。兩個都被賦值為null。
為什么？
因為當我們創建節點時，它還沒有孩子，只有結點數據。
代碼測試
/*** 構建樹*/public static void testCreate() {BinaryTree node = new BinaryTree("a");System.out.println("【node data】:" + node.getData());System.out.println("【node left data】:" + (node.left==null?"null":node.left.getData()));System.out.println("【node right data】:" + (node.right==null?"null":node.right.getData()));} 復制代碼輸出：
【node data】:a 【node left data】:null 【node right data】:null 復制代碼我們可以將字符串'a'作為參數傳給二叉樹結點。如果將值、左孩子結點、右孩子結節點輸出的話，我們就可以看到這個值了。
下面開始插入部分的操作。那么我們需要做些什么工作呢？
有兩個要求：
-
如果當前的結點沒有左孩子結點，我們就創建一個新結點，然后將其設置為當前結點的左結點。
-
如果已經有了左結點，我們就創建一個新結點，并將其放在當前左結點的位置。然后再將原左結點值為新左結點的左結點。
圖形如下：
https://user-gold-cdn.xitu.io/2018/4/17/162d1b4d10dfd5d0?w=1600&h=900&f=jpeg&s=133452下面是插入的代碼：
/*** 插入節點 ，如果當前的節點沒有左節點，我們就創建一個新節點，然后將其設置為當前節點的左節點。** @param node* @param value*/public static void insertLeft(BinaryTree node, String value) {if (node != null) {if (node.left == null) {node.setLeft(new BinaryTree(value));} else {BinaryTree newNode = new BinaryTree(value);newNode.left = node.left;node.left = newNode;}} } 復制代碼再次強調，如果當前結點沒有左結點，我們就創建一個新結點，并將其置為當前結點的左結點。否則，就將新結點放在左結點的位置，再將原左結點置為新左結點的左結點。
同樣，我們編寫插入右結點的代碼
/*** 同插入左結點* @param node* @param value*/public static void insertRight(BinaryTree node, String value) {if (node != null) {if (node.right == null) {node.setRight(new BinaryTree(value));} else {BinaryTree newNode = new BinaryTree(value);newNode.right = node.right;node.right = newNode;}} } 復制代碼但是這還不算完成。我們得測試一下。
我們來構造一個像下面這樣的樹：
https://user-gold-cdn.xitu.io/2018/4/17/162d1b4d49ff6f75?w=1600&h=900&f=jpeg&s=142698- 有一個根結點
- b是左結點
- c是右結點
- b的結節點是d(b沒有左結點)
- c的左結點是e
- c的右結點是f
- e，f都沒有子結點
下面是這棵樹的實現代碼：
/*** 測試插入結點*/public static void testInsert() {BinaryTree node_a = new BinaryTree("a");node_a.insertLeft(node_a, "b");node_a.insertRight(node_a, "c");BinaryTree node_b = node_a.left;node_b.insertRight(node_b, "d");BinaryTree node_c = node_a.right;node_c.insertLeft(node_c, "e");node_c.insertRight(node_c, "f");BinaryTree node_d = node_b.right;BinaryTree node_e = node_c.left;BinaryTree node_f = node_c.right;System.out.println("【node_a data】:" + node_a.getData());System.out.println("【node_b data】:" + node_b.getData());System.out.println("【node_c data】:" + node_c.getData());System.out.println("【node_d data】:" + node_d.getData());System.out.println("【node_e data】:" + node_e.getData());System.out.println("【node_f data】:" + node_f.getData());} 復制代碼輸出：
【node_a data】:a 【node_b data】:b 【node_c data】:c 【node_d data】:d 【node_e data】:e 【node_f data】:f 復制代碼插入已經結束
現在，我們來考慮一下樹的遍歷。
樹的遍歷有兩種選擇，深度優先搜索（DFS）和廣度優先搜索（BFS）。
DFS是用來遍歷或搜索樹數據結構的算法。從根節點開始，在回溯之前沿著每一個分支盡可能遠的探索。 —? Wikipedia
BFS是用來遍歷或搜索樹數據結構的算法。從根節點開始，在探索下一層鄰居節點前，首先探索同一層的鄰居節點。 —? Wikipedia
下面，我們來深入了解每一種遍歷算法。
深度優先搜索（Depth-First Search，DFS）
DFS 在回溯和搜索其他路徑之前找到一條到葉節點的路徑。讓我們看看這種類型的遍歷的示例。
https://user-gold-cdn.xitu.io/2018/4/17/162d1b4ca8eabc95?w=1800&h=1012&f=jpeg&s=191947輸出結果為： 1–2–3–4–5–6–7
為什么？
讓我們分解一下：
當我們深入到葉結點時回溯，這就被稱為 DFS 算法。
既然我們對這種遍歷算法已經熟悉了，我們將討論下 DFS 的類型：前序、中序和后序。
前序遍歷
這和我們在上述示例中的作法基本類似。
中序遍歷
https://user-gold-cdn.xitu.io/2018/4/17/162d1b4d9d967906?w=1800&h=1012&f=jpeg&s=191947示例中此樹的中序算法的結果是3–2–4–1–6–5–7。
左結點優先，之后是中間，最后是右結點。
代碼實現：
/*** 中序遍歷** @param node*/public static void inOrder(BinaryTree node) {if (node != null) {if (node.left != null) {node.left.inOrder(node.left);}System.out.println(node.data);if (node.right != null) {node.right.inOrder(node.right);}}} 復制代碼后序遍歷
https://user-gold-cdn.xitu.io/2018/4/17/162d1b4d71908b54?w=1800&h=1012&f=jpeg&s=191947以此樹為例的后序算法的結果為 3–4–2–6–7–5–1 。
左結點優先，之后是右結點，根結點的最后。
代碼實現：
/*** 后序遍歷** @param node*/public static void postOrder(BinaryTree node) {if (node != null) {if (node.left != null) {node.left.postOrder(node.left);}if (node.right != null) {node.right.postOrder(node.right);}System.out.println(node.data);}}復制代碼廣度優先搜索（BFS）
BFS是一層層逐漸深入的遍歷算法
https://user-gold-cdn.xitu.io/2018/4/17/162d1b4d86da5624?w=1800&h=1012&f=jpeg&s=228533下面這個例子是用來幫我們更好的解釋該算法。
https://user-gold-cdn.xitu.io/2018/4/17/162d1b4da7d3108c?w=1800&h=1012&f=jpeg&s=191947我們來一層一層的遍歷這棵樹。本例中，就是1-2-5-3-4-6-7.
- 0層/深度0：只有值為1的結點
- 1層/深度1：有值為2和5的結點
- 2層/深度2：有值為3、4、6、7的結點
代碼實現：
/*** 廣度排序** @param node*/public static void bfsOrder(BinaryTree node) {if (node != null) {Queue<BinaryTree> queue = new ArrayDeque<BinaryTree>();queue.add(node);while (!queue.isEmpty()) {BinaryTree current_node = queue.poll();System.out.println(current_node.data);if (current_node.left != null) {queue.add(current_node.left);}if (current_node.right != null) {queue.add(current_node.right);}}}}復制代碼為了實現BFS算法，我們需要用到一個數據結構，那就是隊列。
隊列具體是用來干什么的呢？
請看下面解釋。
https://user-gold-cdn.xitu.io/2018/4/17/162d1b4dc5edd2de?w=1600&h=1783&f=jpeg&s=318699二叉搜索樹
二叉搜索樹有時候被稱為二叉有序樹或二叉排序樹，二叉搜索樹的值存儲在有序的順序中，因此，查找表和其他的操作可以使用折半查找原理。——Wikipedia
二叉搜索樹中的一個重要性質是，二叉搜索樹中一個節點的值大于其左結點，但是小于其右結點
https://user-gold-cdn.xitu.io/2018/4/17/162d1b4dba65fe53?w=727&h=250&f=jpeg&s=25958- 是反的二叉搜索樹。子樹 7-5-8-6應該在右邊，而子樹2-1-3 應該在左邊。
- 是唯一正確的選項。它滿足二叉搜索樹的性質
- 有一個問題：值為4的那個結點應該在根結點的左邊，因為這個節點的值比根結點的值5小。
代碼實現二叉樹搜索
插入：向我們的樹添加新的結點
現在想像一下我們有一棵空樹，我們想將幾個節點添加到這棵空樹中，這幾個結點的值為：50、76、21、4、32、100、64、52。
首先我們需要知道的是，50是不是這棵樹的根結點。
https://user-gold-cdn.xitu.io/2018/4/17/162d1b4de9c2fa9b?w=1600&h=900&f=jpeg&s=140104現在我們開始一個一個的插入結點
- 76比50大，所以76插入在右邊。
- 21比50小，所以21插入在左邊。
- 4比50小。但是50已經有了值為21的左結點。然后，4又比21小，所以將其插入在21的左邊。
- 32比50小。但是50已經有了值為21的左結點。然后，32又比21大，所以將其插入在21的右邊。
- 100比50大。但是50已經有了一個值為76的右結點。然后，100又比76大，所以將其插入在76的右邊。
- 64比50大。但是50已經有了一個值為76的右結點。然后，64又比76小，所以將其插入在76的左邊。
- 52比50大。但是50已經有了一個值為76的右結點。52又比76小，但是76也有一個值為64左結點。52又比64小，所以將52插入在64的左邊。
你注意到這里的模式了嗎？
讓我們把它分解。
代碼實現：
/*** 插入樹** @param node* @param value*/public void insertNode(BinaryTree node, Integer value) {if (node != null) {if (value <= Integer.valueOf(node.data) && node.left != null) {node.left.insertNode(node.left, value);} else if (value <= Integer.valueOf(node.data)) {node.left = new BinaryTree(String.valueOf(value));} else if (value > Integer.valueOf(node.data) && node.right != null) {node.right.insertNode(node.right, value);} else {node.right = new BinaryTree(String.valueOf(value));}}}復制代碼看起來很簡單。
該算法的強大之處是其遞歸部分，即第9行和第13行。這兩行代碼均調用 insertNode 方法，并分別為其左結點和右結點使用它。第11行和第15行則在子結點處插入新結點。
搜索結點
我們現在要構建的算法是關于搜索的。對于給定的值（整數），我們會搜索出我們的二叉查找樹有或者沒有這個值。
需要注意的一個重要事項是我們如何定義樹的插入算法。 首先我們有根結點。所有左子的節點值都比根結點小。所有右子樹的節點值都比根結點大。
讓我們看一個例子。
假設我們有這棵樹。
https://user-gold-cdn.xitu.io/2018/4/17/162d1b4e3601f689?w=1400&h=938&f=jpeg&s=148724現在我們想知道是否有一個結點的值為52。
https://user-gold-cdn.xitu.io/2018/4/17/162d1b4e45584fe1?w=1600&h=1096&f=jpeg&s=211314讓我們把它分解。
代碼實現：
/*** 查找節點是否存在** @param node* @param value* @return*/public boolean findNode(BinaryTree node, Integer value) {if (node != null) {if (value < Integer.valueOf(node.data) && node.left != null) {return node.left.findNode(node.left, value);}if (value > Integer.valueOf(node.data) && node.right != null) {return node.right.findNode(node.right, value);}return value == Integer.valueOf(node.data);}return false;}復制代碼代碼分析：
- 第8行和第9行歸于規則#1。
- 第10行和第11行歸于規則#2。
- 第13行歸于規則#3。
刪除：移除和重新組織樹
刪除是一個更復雜的算法，因為我們需要處理不同的情況。對于給定值，我們需要刪除具有此值的結點。想象一下這個節點的以下場景：它沒有孩子，有一個孩子，或者有兩個孩子。
一個沒有孩子的節點（葉節點） 。
# |50| |50| # / \ / \ # |30| |70| (DELETE 20) ---> |30| |70| # / \ \ # |20| |40| |40| 復制代碼如果要刪除的結點沒有子結點，我們簡單地刪除它。該算法不需要重組樹。
僅有一個孩子（左或右孩子）的結點。
# |50| |50| # / \ / \ # |30| |70| (DELETE 30) ---> |20| |70| # / # |20| 復制代碼在這種情況下，我們的算法需要使節點的父節點指向子結點。如果節點是左孩子，則使其父結點指向其子結點。如果結點是右孩子，則使其父結點指向其子結點。
有兩個孩子的節點。
# |50| |50| # / \ / \ # |30| |70| (DELETE 30) ---> |40| |70| # / \ / # |20| |40| 復制代碼當節點有兩個孩子，則需要從該節點的右孩子開始，找到具有最小值的結點。我們將把具有最小值的這個節點置于被刪除的節點的位置。
代碼實現：
/*** 刪除節點* @param node* @param value* @param parent* @return*/public boolean removeNode(BinaryTree node, Integer value, BinaryTree parent) {if (node != null) {if (value < Integer.valueOf(node.data) && node.left != null) {return node.left.removeNode(node.left, value, node);} else if (value < Integer.valueOf(node.data)) {return false;} else if (value > Integer.valueOf(node.data) && node.right != null) {return node.right.removeNode(node.right, value, node);} else if (value > Integer.valueOf(node.data)) {return false;} else {if (node.left == null && node.right == null && node == parent.left) {parent.left = null;node.clearNode(node);} else if (node.left == null && node.right == null && node == parent.right) {parent.right = null;node.clearNode(node);} else if (node.left != null && node.right == null && node == parent.left) {parent.left = node.left;node.clearNode(node);} else if (node.left != null && node.right == null && node == parent.right) {parent.right = node.left;node.clearNode(node);} else if (node.right != null && node.left == null && node == parent.left) {parent.left = node.right;node.clearNode(node);} else if (node.right != null && node.left == null && node == parent.right) {parent.right = node.right;node.clearNode(node);} else {node.data=String.valueOf(node.right.findMinValue(node.right));node.right.removeNode(node.right,Integer.valueOf(node.right.data),node);}return true;}}return false;} 復制代碼- clear_node 方法：設置節點的三個屬性為空——(value, left_child, and right_child)
- find_minimum_value方法：一路向下找最左側的。如果我們無法找到任何節點，我們找其中最小的
原文鏈接：Everything you need to know about tree data structures
代碼下載：
從我的 github 中下載，【譯】數據結構中關于樹的一切（java版)
推薦文章
https://user-gold-cdn.xitu.io/2018/4/17/162d1b4f7821b3ec?w=301&h=330&f=png&s=78572
???關注微信小程序java架構師歷程 上下班的路上無聊嗎？還在看小說、新聞嗎？不知道怎樣提高自己的技術嗎？來吧這里有你需要的java架構文章，1.5w+的java工程師都在看，你還在等什么？
總結
以上是生活随笔為你收集整理的【译】数据结构中关于树的一切（java版）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 简单谈谈setTimeout与setIn
- 下一篇： 【最佳实践】授权子账号进行OSS图片样式