樹數(shù)據(jù)結(jié)構(gòu)在我們編碼和面試中都是很重要的知識(shí)。使用數(shù)據(jù)結(jié)構(gòu)來(lái)組織數(shù)據(jù)，數(shù)據(jù)結(jié)構(gòu)越高效，程序就會(huì)越好。

今天，我們將深入探討數(shù)據(jù)結(jié)構(gòu)之一：樹。

今天，我們將介紹：

• 什么是樹？
• 樹的種類
• 樹的遍歷和搜索

什么是樹？

數(shù)據(jù)結(jié)構(gòu)用于存儲(chǔ)和組織數(shù)據(jù)。我們可以使用算法來(lái)操縱和使用我們的數(shù)據(jù)結(jié)構(gòu)。通過使用不同的數(shù)據(jù)結(jié)構(gòu)可以更有效地組織不同類型的數(shù)據(jù)。

樹是非線性數(shù)據(jù)結(jié)構(gòu)。它們通常用于表示分層數(shù)據(jù)。舉一個(gè)現(xiàn)實(shí)的例子，分層的公司結(jié)構(gòu)使用樹來(lái)組織。

樹的組成部分

樹是節(jié)點(diǎn)（頂點(diǎn)）的集合，它們通過邊（指針）鏈接起來(lái)，代表節(jié)點(diǎn)之間的層次連接。節(jié)點(diǎn)包含任意類型的數(shù)據(jù)，但所有節(jié)點(diǎn)必須具有相同的數(shù)據(jù)類型。樹與圖類似，但樹中不能存在環(huán)。樹有哪些不同的組成部分？

根：樹的根是沒有傳入鏈接的節(jié)點(diǎn)（即沒有父節(jié)點(diǎn)）。將此視為樹的起點(diǎn)。

子節(jié)點(diǎn)：樹的子節(jié)點(diǎn)是一個(gè)節(jié)點(diǎn)，具有來(lái)自其上方節(jié)點(diǎn)（即父節(jié)點(diǎn)）的一個(gè)傳入鏈接。如果兩個(gè)子節(jié)點(diǎn)共享同一個(gè)父節(jié)點(diǎn)，則它們稱為兄弟節(jié)點(diǎn)。

父節(jié)點(diǎn)：父節(jié)點(diǎn)具有將其連接到一個(gè)或多個(gè)子節(jié)點(diǎn)的傳出鏈接。

葉子：葉子有一個(gè)父節(jié)點(diǎn)，但沒有到子節(jié)點(diǎn)的傳出鏈接。將此視為樹的端點(diǎn)。

子樹：子樹是包含在較大樹中的較小樹。該樹的根可以是較大樹中的任何節(jié)點(diǎn)。

深度：節(jié)點(diǎn)的深度是該節(jié)點(diǎn)與根之間的邊數(shù)。將此視為節(jié)點(diǎn)和樹的起點(diǎn)之間有多少步。

高度：節(jié)點(diǎn)的高度是從該節(jié)點(diǎn)到葉節(jié)點(diǎn)的最長(zhǎng)路徑中的邊數(shù)。將此視為節(jié)點(diǎn)和樹端點(diǎn)之間有多少步。樹的高度是其根節(jié)點(diǎn)的高度。

度：節(jié)點(diǎn)的度是指子樹的數(shù)量。

我們?yōu)槭裁匆褂脴洌?/h3>

樹可以應(yīng)用于很多事情。層次結(jié)構(gòu)賦予樹用于存儲(chǔ)、操作和訪問數(shù)據(jù)的獨(dú)特屬性。樹構(gòu)成了計(jì)算機(jī)最基本的組織結(jié)構(gòu)。我們可以將樹用于以下用途：

• 存儲(chǔ)為層次結(jié)構(gòu)。存儲(chǔ)層次結(jié)構(gòu)中自然出現(xiàn)的信息。計(jì)算機(jī)上的文件系統(tǒng)和 PDF 使用樹結(jié)構(gòu)。
• 搜索。存儲(chǔ)我們想要快速搜索的信息。樹比鏈表更容易搜索。某些類型的樹（如 AVL 樹和紅黑樹）是為快速搜索而設(shè)計(jì)的。
• 繼承。樹可用于繼承、XML 解析器、機(jī)器學(xué)習(xí)和 DNS 等。
• 索引。高級(jí)類型的樹（例如 B 樹和 B+ 樹）可用于為數(shù)據(jù)庫(kù)建立索引。
• 網(wǎng)絡(luò)。樹非常適合社交網(wǎng)絡(luò)和電腦國(guó)際象棋游戲等。
• 最短路徑。生成樹可用于查找路由器中的最短路徑以進(jìn)行網(wǎng)絡(luò)連接。
• 等等

如何編碼一棵樹

例如，要在Java中構(gòu)建樹，我們從根節(jié)點(diǎn)開始。

Node<String> root = new Node<>("root");

一旦我們有了根，我們就可以使用添加第一個(gè)子節(jié)點(diǎn)addChild，這會(huì)添加一個(gè)子節(jié)點(diǎn)并將其分配給父節(jié)點(diǎn)。我們將此過程稱為插入（添加節(jié)點(diǎn)）和刪除（刪除節(jié)點(diǎn)）。

Node<String> node1 = root.addChild(new Node<String>("node 1"));

我們繼續(xù)使用相同的過程添加節(jié)點(diǎn)，直到我們擁有復(fù)雜的層次結(jié)構(gòu)。

樹的種類

我們可以使用多種類型的樹在層次結(jié)構(gòu)中以不同的方式組織數(shù)據(jù)。我們使用的樹取決于我們要解決的問題。讓我們看一下可以在 Java 中使用的樹。我們將涵蓋：

• N叉樹
• 平衡樹
• 二叉樹
• 二叉搜索樹
• AVL樹
• 紅黑樹
• 2-3 棵樹
• 2-3-4 樹

N叉樹

在N叉樹中，一個(gè)節(jié)點(diǎn)可以有0-N個(gè)子節(jié)點(diǎn)。例如，如果我們有一個(gè)二叉樹（也稱為二叉樹），它最多有 0-2 個(gè)子節(jié)點(diǎn)。

注： 節(jié)點(diǎn)的平衡因子是左右子樹的高度差。

平衡樹

平衡樹是幾乎所有葉子節(jié)點(diǎn)都在同一級(jí)別的樹，最常應(yīng)用于子樹，即所有子樹都必須是平衡的。換句話說，我們必須使樹高平衡，左右子樹的高度差不超過1。這是平衡樹的直觀表示。

根據(jù)其結(jié)構(gòu)，二叉樹主要分為三種類型。

1、完全二叉樹

當(dāng)每一層（不包括最后一層）都被填滿并且最后一層的所有節(jié)點(diǎn)都盡可能靠左時(shí)，就存在完全二叉樹。這是完整二叉樹的直觀表示。

2、滿二叉樹

當(dāng)每個(gè)節(jié)點(diǎn)（不包括葉子）都有兩個(gè)子節(jié)點(diǎn)時(shí)，就存在滿二叉樹（有時(shí)稱為真二叉樹）。每一層都必須填滿，并且節(jié)點(diǎn)盡可能遠(yuǎn)離。查看此圖以了解完整二叉樹的外觀。

3、完美二叉樹

完美的二叉樹應(yīng)該是滿的和完整的。所有內(nèi)部節(jié)點(diǎn)都應(yīng)該有兩個(gè)子節(jié)點(diǎn)，并且所有葉子節(jié)點(diǎn)必須具有相同的深度。查看此圖以了解完美二叉樹的外觀。

注意：還可以擁有傾斜二叉樹，其中所有節(jié)點(diǎn)都向左或向右移動(dòng)，但最佳實(shí)踐是在 Java 中避免這種類型的樹，因?yàn)樗阉鞴?jié)點(diǎn)要復(fù)雜得多。

二叉搜索樹

二叉搜索樹是一棵二叉樹，其中每個(gè)節(jié)點(diǎn)都有一個(gè)鍵和一個(gè)關(guān)聯(lián)值。這允許快速查找和編輯（添加或刪除），因此得名“搜索”。二叉搜索樹根據(jù)其node值有嚴(yán)格的條件。需要注意的是，每個(gè)二叉搜索樹都是二叉樹，但并非每個(gè)二叉樹都是二叉搜索樹。

是什么讓他們與眾不同？在二叉搜索樹中，子樹的左子樹必須包含鍵少于該節(jié)點(diǎn)鍵的節(jié)點(diǎn)，而右子樹將包含鍵大于該節(jié)點(diǎn)鍵的節(jié)點(diǎn)。查看此視覺效果以了解這種情況。

在此示例中，節(jié)點(diǎn) Y 是具有兩個(gè)子節(jié)點(diǎn)的父節(jié)點(diǎn)。子樹 1 中的所有節(jié)點(diǎn)的值必須小于節(jié)點(diǎn) Y，子樹 2 中的所有節(jié)點(diǎn)的值必須大于節(jié)點(diǎn) Y。

AVL樹

AVL樹是一種特殊類型的二叉搜索樹，它通過檢查每個(gè)節(jié)點(diǎn)的平衡因子來(lái)實(shí)現(xiàn)自平衡。平衡因子應(yīng)該是+1、0或-1。左右子樹的最大高度差只能為1。

如果這種差異變得大于一個(gè)，我們必須使用旋轉(zhuǎn)技術(shù)重新平衡我們的樹以使其有效。這些對(duì)于搜索是最重要操作的應(yīng)用程序來(lái)說是最常見的。查看此視覺效果可以看到有效的 AVL 樹。

紅黑樹

紅黑樹是另一種自平衡二叉搜索樹，但它具有 AVL 樹的一些附加屬性。節(jié)點(diǎn)的顏色為紅色或黑色，以幫助在插入或刪除后重新平衡樹。它們可以節(jié)省平衡時(shí)間。那么，我們?nèi)绾螢楣?jié)點(diǎn)著色呢？

• 根部始終是黑色的。
• 兩個(gè)紅色節(jié)點(diǎn)不能相鄰（即紅色父節(jié)點(diǎn)不能有紅色子節(jié)點(diǎn)）。
• 從根到葉的路徑應(yīng)包含相同數(shù)量的黑色節(jié)點(diǎn)。
• 空節(jié)點(diǎn)是黑色的。

2-3 棵樹

2-3 樹與我們目前學(xué)到的有很大不同。與二叉搜索樹不同，2-3 樹是一種自平衡、有序、多路搜索樹。它始終是完美平衡的，因此每個(gè)葉節(jié)點(diǎn)與根的距離相等。除葉節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)都可以是 2 節(jié)點(diǎn)（具有單個(gè)數(shù)據(jù)元素和兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)）或 3 節(jié)點(diǎn)（具有兩個(gè)數(shù)據(jù)元素和三個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)）。無(wú)論發(fā)生多少次插入或刪除，2-3 樹都會(huì)保持平衡。

2-3-4 樹

2-3-4 樹是一種比 2-3 樹可以容納更多鍵的搜索樹。它涵蓋了與 2-3 樹相同的基礎(chǔ)知識(shí)，但添加了以下屬性：

• 2-節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)和一個(gè)數(shù)據(jù)元素
• 3-Node 有三個(gè)子節(jié)點(diǎn)和兩個(gè)數(shù)據(jù)元素
• 4-節(jié)點(diǎn)有四個(gè)子節(jié)點(diǎn)和三個(gè)數(shù)據(jù)元素
• 每個(gè)內(nèi)部節(jié)點(diǎn)最多有 4 個(gè)子節(jié)點(diǎn)
• 對(duì)于內(nèi)部節(jié)點(diǎn)的三個(gè)鍵，LeftChild節(jié)點(diǎn)的所有鍵都小于左鍵
• LeftMidChild 上的所有鍵都小于中間鍵
• RightMidChild 處的所有鍵都小于右側(cè)鍵
• RightChild 處的所有鍵都大于右側(cè)鍵

樹遍歷和搜索簡(jiǎn)介

要使用樹，我們可以通過訪問/檢查樹的每個(gè)節(jié)點(diǎn)來(lái)遍歷它們。如果一棵樹被“遍歷”，這意味著每個(gè)節(jié)點(diǎn)都被訪問過。遍歷一棵樹有四種方法。這四個(gè)過程屬于兩類之一：廣度優(yōu)先遍歷或深度優(yōu)先遍歷。

• 中序：將其視為在樹上向上移動(dòng)，然后向下移動(dòng)。遍歷左子樹及其子樹，直到到達(dá)根。然后，向下遍歷右孩子及其子樹。這是深度優(yōu)先遍歷。
• 前序：從根開始，遍歷左子樹，然后移動(dòng)到右子樹。這是深度優(yōu)先遍歷。
• 后序：從左子樹開始，移至右子樹。然后，向上移動(dòng)訪問根節(jié)點(diǎn)。這是深度優(yōu)先遍歷。
• 層序：將其視為一種之字形圖案。這將按節(jié)點(diǎn)的級(jí)別而不是子樹遍歷節(jié)點(diǎn)。首先，我們?cè)L問根并從左到右訪問該根的所有子節(jié)點(diǎn)。然后我們向下移動(dòng)到下一個(gè)級(jí)別，直到到達(dá)沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。這是左節(jié)點(diǎn)。這是廣度優(yōu)先的遍歷。

那么，廣度優(yōu)先遍歷和深度優(yōu)先遍歷有什么區(qū)別呢？讓我們看一下深度優(yōu)先搜索 (DFS) 和廣度優(yōu)先搜索 (BFS) 算法，以便更好地理解這一點(diǎn)。

注意：算法是用于執(zhí)行某些任務(wù)的指令序列。我們使用具有數(shù)據(jù)結(jié)構(gòu)的算法來(lái)操作我們的數(shù)據(jù)，在本例中是遍歷我們的數(shù)據(jù)。

深度優(yōu)先搜索

概述：我們沿著從起始節(jié)點(diǎn)到結(jié)束節(jié)點(diǎn)的路徑，然后開始另一條路徑，直到訪問完所有節(jié)點(diǎn)。這通常使用堆棧來(lái)實(shí)現(xiàn)，并且它比 BFS 需要更少的內(nèi)存。它最適合拓?fù)渑判?，例如圖回溯或循環(huán)檢測(cè)。

算法步驟DFS如下：

• 選擇一個(gè)節(jié)點(diǎn)。將所有相鄰節(jié)點(diǎn)壓入堆棧。
• 從該堆棧中彈出一個(gè)節(jié)點(diǎn)并將相鄰節(jié)點(diǎn)推入另一個(gè)堆棧。
• 重復(fù)此步驟，直到堆棧為空或達(dá)到目標(biāo)為止。當(dāng)訪問節(jié)點(diǎn)時(shí)，必須在繼續(xù)之前將其標(biāo)記為已訪問，否則將陷入無(wú)限循環(huán)。

廣度優(yōu)先搜索

概述：我們逐級(jí)訪問一級(jí)的所有節(jié)點(diǎn)，然后再進(jìn)入下一級(jí)。BFS算法通常使用隊(duì)列來(lái)實(shí)現(xiàn)，并且它比DFS算法需要更多的內(nèi)存。最適合尋找兩個(gè)節(jié)點(diǎn)之間的最短路徑。

算法步驟BFS如下：

• 選擇一個(gè)節(jié)點(diǎn)。將所有相鄰節(jié)點(diǎn)放入隊(duì)列中。將節(jié)點(diǎn)出隊(duì)，并將其標(biāo)記為已訪問。將所有相鄰節(jié)點(diǎn)放入另一個(gè)隊(duì)列中。
• 重復(fù)此操作，直到隊(duì)列中沒有已實(shí)現(xiàn)的目標(biāo)。
• 當(dāng)訪問節(jié)點(diǎn)時(shí)，必須在繼續(xù)之前將其標(biāo)記為已訪問，否則將陷入無(wú)限循環(huán)。

在二叉搜索樹中搜索

了解如何在樹中執(zhí)行搜索非常重要。搜索意味著我們?cè)跀?shù)據(jù)結(jié)構(gòu)中定位特定元素或節(jié)點(diǎn)。由于二叉搜索樹中的數(shù)據(jù)是有序的，因此搜索非常容易。讓我們看看它是如何完成的。

• 從根開始。
• 如果該值小于當(dāng)前節(jié)點(diǎn)的值，則遍歷左子樹。如果大于，則遍歷右子樹。
• 繼續(xù)此過程，直到到達(dá)具有該值的節(jié)點(diǎn)或到達(dá)葉節(jié)點(diǎn)，這意味著該值不存在。

在3.中步驟，如下：

現(xiàn)在讓我們看看 Java 代碼中的內(nèi)容！

public class BinarySearchTree {
      …
      
      public boolean search(int value) {
            if (root == null)
                  return false;
            else
                  return root.search(value);
      }
}
public class BSTNode {
      …

      public boolean search(int value) {
            if (value == this.value)
                  return true;
            else if (value < this.value) {
                  if (left == null)
                        return false;
                  else
                        return left.search(value);
            } else if (value > this.value) {
                  if (right == null)
                        return false;
                  else
                        return right.search(value);
            }
            return false;
      }
}

總結(jié)

本篇讓我們更深入了解樹的數(shù)據(jù)結(jié)構(gòu)以及用的運(yùn)用。