掃二維碼與項目經(jīng)理溝通
我們在微信上24小時期待你的聲音
解答本文疑問/技術(shù)咨詢/運營咨詢/技術(shù)建議/互聯(lián)網(wǎng)交流
樹數(shù)據(jù)結(jié)構(gòu)在我們編碼和面試中都是很重要的知識。使用數(shù)據(jù)結(jié)構(gòu)來組織數(shù)據(jù)，數(shù)據(jù)結(jié)構(gòu)越高效，程序就會越好。
云龍ssl適用于網(wǎng)站、小程序/APP、API接口等需要進(jìn)行數(shù)據(jù)傳輸應(yīng)用場景，ssl證書未來市場廣闊！成為創(chuàng)新互聯(lián)建站的ssl證書銷售渠道，可以享受市場價格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：18982081108（備注：SSL證書合作）期待與您的合作！
今天，我們將深入探討數(shù)據(jù)結(jié)構(gòu)之一：樹。
今天，我們將介紹：
數(shù)據(jù)結(jié)構(gòu)用于存儲和組織數(shù)據(jù)。我們可以使用算法來操縱和使用我們的數(shù)據(jù)結(jié)構(gòu)。通過使用不同的數(shù)據(jù)結(jié)構(gòu)可以更有效地組織不同類型的數(shù)據(jù)。
樹是非線性數(shù)據(jù)結(jié)構(gòu)。它們通常用于表示分層數(shù)據(jù)。舉一個現(xiàn)實的例子，分層的公司結(jié)構(gòu)使用樹來組織。
樹是節(jié)點（頂點）的集合，它們通過邊（指針）鏈接起來，代表節(jié)點之間的層次連接。節(jié)點包含任意類型的數(shù)據(jù)，但所有節(jié)點必須具有相同的數(shù)據(jù)類型。樹與圖類似，但樹中不能存在環(huán)。樹有哪些不同的組成部分？
根：樹的根是沒有傳入鏈接的節(jié)點（即沒有父節(jié)點）。將此視為樹的起點。
子節(jié)點：樹的子節(jié)點是一個節(jié)點，具有來自其上方節(jié)點（即父節(jié)點）的一個傳入鏈接。如果兩個子節(jié)點共享同一個父節(jié)點，則它們稱為兄弟節(jié)點。
父節(jié)點：父節(jié)點具有將其連接到一個或多個子節(jié)點的傳出鏈接。
葉子：葉子有一個父節(jié)點，但沒有到子節(jié)點的傳出鏈接。將此視為樹的端點。
子樹：子樹是包含在較大樹中的較小樹。該樹的根可以是較大樹中的任何節(jié)點。
深度：節(jié)點的深度是該節(jié)點與根之間的邊數(shù)。將此視為節(jié)點和樹的起點之間有多少步。
高度：節(jié)點的高度是從該節(jié)點到葉節(jié)點的最長路徑中的邊數(shù)。將此視為節(jié)點和樹端點之間有多少步。樹的高度是其根節(jié)點的高度。
度：節(jié)點的度是指子樹的數(shù)量。
樹可以應(yīng)用于很多事情。層次結(jié)構(gòu)賦予樹用于存儲、操作和訪問數(shù)據(jù)的獨特屬性。樹構(gòu)成了計算機(jī)最基本的組織結(jié)構(gòu)。我們可以將樹用于以下用途：
例如，要在Java中構(gòu)建樹，我們從根節(jié)點開始。
Node root = new Node<>("root"); 一旦我們有了根，我們就可以使用添加第一個子節(jié)點addChild，這會添加一個子節(jié)點并將其分配給父節(jié)點。我們將此過程稱為插入（添加節(jié)點）和刪除（刪除節(jié)點）。
Node node1 = root.addChild(new Node("node 1")); 我們繼續(xù)使用相同的過程添加節(jié)點，直到我們擁有復(fù)雜的層次結(jié)構(gòu)。
我們可以使用多種類型的樹在層次結(jié)構(gòu)中以不同的方式組織數(shù)據(jù)。我們使用的樹取決于我們要解決的問題。讓我們看一下可以在 Java 中使用的樹。我們將涵蓋：
在N叉樹中，一個節(jié)點可以有0-N個子節(jié)點。例如，如果我們有一個二叉樹（也稱為二叉樹），它最多有 0-2 個子節(jié)點。
注： 節(jié)點的平衡因子是左右子樹的高度差。
平衡樹是幾乎所有葉子節(jié)點都在同一級別的樹，最常應(yīng)用于子樹，即所有子樹都必須是平衡的。換句話說，我們必須使樹高平衡，左右子樹的高度差不超過1。這是平衡樹的直觀表示。
根據(jù)其結(jié)構(gòu)，二叉樹主要分為三種類型。
當(dāng)每一層（不包括最后一層）都被填滿并且最后一層的所有節(jié)點都盡可能靠左時，就存在完全二叉樹。這是完整二叉樹的直觀表示。
當(dāng)每個節(jié)點（不包括葉子）都有兩個子節(jié)點時，就存在滿二叉樹（有時稱為真二叉樹）。每一層都必須填滿，并且節(jié)點盡可能遠(yuǎn)離。查看此圖以了解完整二叉樹的外觀。
完美的二叉樹應(yīng)該是滿的和完整的。所有內(nèi)部節(jié)點都應(yīng)該有兩個子節(jié)點，并且所有葉子節(jié)點必須具有相同的深度。查看此圖以了解完美二叉樹的外觀。
注意：還可以擁有傾斜二叉樹，其中所有節(jié)點都向左或向右移動，但最佳實踐是在 Java 中避免這種類型的樹，因為搜索節(jié)點要復(fù)雜得多。
二叉搜索樹是一棵二叉樹，其中每個節(jié)點都有一個鍵和一個關(guān)聯(lián)值。這允許快速查找和編輯（添加或刪除），因此得名“搜索”。二叉搜索樹根據(jù)其node值有嚴(yán)格的條件。需要注意的是，每個二叉搜索樹都是二叉樹，但并非每個二叉樹都是二叉搜索樹。
是什么讓他們與眾不同？在二叉搜索樹中，子樹的左子樹必須包含鍵少于該節(jié)點鍵的節(jié)點，而右子樹將包含鍵大于該節(jié)點鍵的節(jié)點。查看此視覺效果以了解這種情況。
在此示例中，節(jié)點 Y 是具有兩個子節(jié)點的父節(jié)點。子樹 1 中的所有節(jié)點的值必須小于節(jié)點 Y，子樹 2 中的所有節(jié)點的值必須大于節(jié)點 Y。
AVL樹是一種特殊類型的二叉搜索樹，它通過檢查每個節(jié)點的平衡因子來實現(xiàn)自平衡。平衡因子應(yīng)該是+1、0或-1。左右子樹的最大高度差只能為1。
如果這種差異變得大于一個，我們必須使用旋轉(zhuǎn)技術(shù)重新平衡我們的樹以使其有效。這些對于搜索是最重要操作的應(yīng)用程序來說是最常見的。查看此視覺效果可以看到有效的 AVL 樹。
紅黑樹是另一種自平衡二叉搜索樹，但它具有 AVL 樹的一些附加屬性。節(jié)點的顏色為紅色或黑色，以幫助在插入或刪除后重新平衡樹。它們可以節(jié)省平衡時間。那么，我們?nèi)绾螢楣?jié)點著色呢？
2-3 樹與我們目前學(xué)到的有很大不同。與二叉搜索樹不同，2-3 樹是一種自平衡、有序、多路搜索樹。它始終是完美平衡的，因此每個葉節(jié)點與根的距離相等。除葉節(jié)點外，每個節(jié)點都可以是 2 節(jié)點（具有單個數(shù)據(jù)元素和兩個子節(jié)點的節(jié)點）或 3 節(jié)點（具有兩個數(shù)據(jù)元素和三個子節(jié)點的節(jié)點）。無論發(fā)生多少次插入或刪除，2-3 樹都會保持平衡。
2-3-4 樹是一種比 2-3 樹可以容納更多鍵的搜索樹。它涵蓋了與 2-3 樹相同的基礎(chǔ)知識，但添加了以下屬性：
要使用樹，我們可以通過訪問/檢查樹的每個節(jié)點來遍歷它們。如果一棵樹被“遍歷”，這意味著每個節(jié)點都被訪問過。遍歷一棵樹有四種方法。這四個過程屬于兩類之一：廣度優(yōu)先遍歷或深度優(yōu)先遍歷。
那么，廣度優(yōu)先遍歷和深度優(yōu)先遍歷有什么區(qū)別呢？讓我們看一下深度優(yōu)先搜索 (DFS) 和廣度優(yōu)先搜索 (BFS) 算法，以便更好地理解這一點。
注意：算法是用于執(zhí)行某些任務(wù)的指令序列。我們使用具有數(shù)據(jù)結(jié)構(gòu)的算法來操作我們的數(shù)據(jù)，在本例中是遍歷我們的數(shù)據(jù)。
概述：我們沿著從起始節(jié)點到結(jié)束節(jié)點的路徑，然后開始另一條路徑，直到訪問完所有節(jié)點。這通常使用堆棧來實現(xiàn)，并且它比 BFS 需要更少的內(nèi)存。它最適合拓?fù)渑判?，例如圖回溯或循環(huán)檢測。
算法步驟DFS如下：
概述：我們逐級訪問一級的所有節(jié)點，然后再進(jìn)入下一級。BFS算法通常使用隊列來實現(xiàn)，并且它比DFS算法需要更多的內(nèi)存。最適合尋找兩個節(jié)點之間的最短路徑。
算法步驟BFS如下：
了解如何在樹中執(zhí)行搜索非常重要。搜索意味著我們在數(shù)據(jù)結(jié)構(gòu)中定位特定元素或節(jié)點。由于二叉搜索樹中的數(shù)據(jù)是有序的，因此搜索非常容易。讓我們看看它是如何完成的。
在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;
}
}本篇讓我們更深入了解樹的數(shù)據(jù)結(jié)構(gòu)以及用的運用。
我們在微信上24小時期待你的聲音
解答本文疑問/技術(shù)咨詢/運營咨詢/技術(shù)建議/互聯(lián)網(wǎng)交流
微信二維碼
微信二維碼
移動版官網(wǎng)