本篇文章為大家展示了什么是樹、二叉樹以及二叉查找樹，內(nèi)容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細介紹希望你能有所收獲。

創(chuàng)新互聯(lián)建站專注于企業(yè)營銷型網(wǎng)站、網(wǎng)站重做改版、北鎮(zhèn)網(wǎng)站定制設(shè)計、自適應(yīng)品牌網(wǎng)站建設(shè)、H5網(wǎng)站設(shè)計、成都商城網(wǎng)站開發(fā)、集團公司官網(wǎng)建設(shè)、成都外貿(mào)網(wǎng)站制作、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁設(shè)計等建站業(yè)務(wù)，價格優(yōu)惠性價比高，為北鎮(zhèn)等各大城市提供網(wǎng)站開發(fā)制作服務(wù)。

說起樹，大家都不陌生，畢竟是日常生活中常見的事物。但是今天的主角不是樹木，我們來聊聊數(shù)據(jù)結(jié)構(gòu)中的樹、二叉樹和二叉查找樹，以及它們的基本操作！

一、樹與二叉樹

1.1 什么是樹？

樹是一種數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=1）個有限結(jié)點組成一個具有層次關(guān)系的集合。把它叫做“樹”是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。

樹是由結(jié)點和邊組成的，不存在環(huán)的一種數(shù)據(jù)結(jié)構(gòu)。通過下圖，我們就可以更直觀的認識樹的結(jié)構(gòu)。

樹滿足遞歸定義的特性。也就是說，如果一個數(shù)據(jù)結(jié)構(gòu)是樹結(jié)構(gòu)，那么剔除掉根結(jié)點后，得到的若干個子結(jié)構(gòu)也是樹，通常稱作子樹。

在一棵樹中，根據(jù)結(jié)點之間層次關(guān)系的不同，對結(jié)點的稱呼也有所不同。我們來看下面這棵樹，如下圖所示:

不同結(jié)點的關(guān)系與稱呼如下：

• A 結(jié)點是 B 結(jié)點和 C 結(jié)點的上級，則 A 就是 B 和 C 的父結(jié)點，B 和 C 是 A 的子結(jié)點。

• B 和 C 同時是 A 的“孩子”，則可以稱 B 和 C 互為兄弟結(jié)點。

• A 沒有父結(jié)點，則可以稱 A 為根結(jié)點。

• G、H、I、F 結(jié)點都沒有子結(jié)點，則稱 G、H、I、F 為葉子結(jié)點。

當有了一棵樹之后，還需要用深度、層來描述這棵樹中結(jié)點的位置。如上圖所示，結(jié)點的層次從根結(jié)點算起：

• 根為第一層，比如：A

• 根的“孩子”為第二層，比如B、C

• 根的“孩子”的“孩子”為第三層，比如D、E、F

• 依此類推，第四層（最后一層）就是：G、H、I

樹中結(jié)點的最大層次數(shù)，就是這棵樹的樹深（稱為深度，也稱為高度）因此這是一棵深度為 4 的樹。

1.2 什么是二叉樹？

在樹的大家族中，有一種被高頻使用的特殊樹，它就是二叉樹。在二叉樹中，每個結(jié)點最多有兩個分支，即每個結(jié)點最多有兩個子結(jié)點，分別稱作左子結(jié)點和右子結(jié)點。

在二叉樹中，有兩個最為特殊的類型，如下圖所示：

• 滿二叉樹，定義為除了葉子結(jié)點外，所有結(jié)點都有 2 個子結(jié)點。

• 完全二叉樹，定義為除了最后一層以外，其他層的結(jié)點個數(shù)都達到最大，并且最后一層的葉子結(jié)點都靠左排列。

你可能會困惑，完全二叉樹看上去并不完全，但為什么這樣稱呼它呢？這其實和二叉樹的存儲有關(guān)系。存儲二叉樹有兩種辦法，一種是基于指針的鏈式存儲法，另一種是基于數(shù)組的順序存儲法。

• 鏈式存儲法，也就是像鏈表一樣，每個結(jié)點有三個字段，一個存儲數(shù)據(jù)，另外兩個分別存放指向左右子結(jié)點的指針，如下圖所示：

• 順序存儲法，就是按照規(guī)律把結(jié)點存放在數(shù)組里，如下圖所示，為了方便計算，我們會約定把根結(jié)點放在下標為 1 的位置。隨后，B 結(jié)點存放在下標為 2 的位置，C 結(jié)點存放在下標為 3 的位置，依次類推。
  

之所以稱為完全二叉樹，是從存儲空間利用效率的視角來看的。對于一棵完全二叉樹而言，僅僅浪費了下標為 0 的存儲位置。而如果是一棵非完全二叉樹，則會浪費大量的存儲空間。

如下圖所示的非完全二叉樹，它既需要保留出 5 和 6 的位置。同時，還需要保留 5 的兩個子結(jié)點 10 和 11 的位置，以及 6 的兩個子結(jié)點 12 和 13 的位置。這樣的二叉樹，沒有完全利用好數(shù)組的存儲空間。

---

二、樹的前序、中序、后序遍歷

接下來，我們以二叉樹為例介紹樹的操作，其他類型的樹的操作與二叉樹基本相似。

可以發(fā)現(xiàn)，我們以前學(xué)到的數(shù)據(jù)結(jié)構(gòu)都是“一對一”的關(guān)系，即前面的數(shù)據(jù)只跟下面的一個數(shù)據(jù)產(chǎn)生了連接關(guān)系，例如鏈表、棧、隊列等。而樹結(jié)構(gòu)則是“一對多”的關(guān)系，即前面的父結(jié)點，跟下面若干個子結(jié)點產(chǎn)生了連接關(guān)系。

在“一對一”的結(jié)構(gòu)中，查找具有某個數(shù)值，可以直接按順序遍歷每一條數(shù)據(jù)?？墒牵瑯涫恰耙粚Χ唷钡年P(guān)系，那該按什么順序遍歷呢？

其實，遍歷一棵樹，有非常經(jīng)典的三種方法，分別是前序遍歷、中序遍歷、后序遍歷。這里的序指的是父結(jié)點的遍歷順序，前序就是先遍歷父結(jié)點，中序就是中間遍歷父結(jié)點，后序就是最后遍歷父結(jié)點。

不管哪種遍歷，都是通過遞歸調(diào)用完成的。如下圖所示：

• 前序遍歷，對樹中的任意結(jié)點來說，先打印這個結(jié)點，然后前序遍歷它的左子樹，最后前序遍歷它的右子樹。

• 中序遍歷，對樹中的任意結(jié)點來說，先中序遍歷它的左子樹，然后打印這個結(jié)點，最后中序遍歷它的右子樹。

• 后序遍歷，對樹中的任意結(jié)點來說，先后序遍歷它的左子樹，然后后序遍歷它的右子樹，最后打印它本身。

---

三、二叉查找樹的特性

對于沒有任何特殊性質(zhì)的二叉樹而言，拋開遍歷的時間復(fù)雜度以外，真正執(zhí)行增加和刪除操作的時間復(fù)雜度是 O(1)。樹數(shù)據(jù)的查找操作和鏈表一樣，都需要遍歷每一個數(shù)據(jù)去判斷，所以時間復(fù)雜度是 O(n)。

但當二叉樹具備一些特性的時候（比如二叉查找樹），則可以利用這些特性實現(xiàn)時間復(fù)雜度的降低。

二叉查找樹（也稱作二叉搜索樹）具備以下幾個的特性：

• 在二叉查找樹中的任意一個結(jié)點，其左子樹中的每個結(jié)點的值，都要小于這個結(jié)點的值；其右子樹中每個結(jié)點的值，都要大于這個結(jié)點的值。

• 在二叉查找樹中，會盡可能規(guī)避兩個結(jié)點數(shù)值相等的情況。

• 對二叉查找樹進行中序遍歷，就可以輸出一個從小到大的有序數(shù)據(jù)隊列。如下圖所示，中序遍歷的結(jié)果就是 10、13、15、16、20、21、22、26。

所以二叉查找樹可以簡單的認為是，是一個按規(guī)則排好序的二叉樹。

---

四、二叉查找樹的增刪查操作

3.1 查找操作

在利用二叉查找樹執(zhí)行查找操作時，我們可以進行以下判斷：

• 首先判斷根結(jié)點是否等于要查找的數(shù)據(jù)，如果是就返回。

• 如果根結(jié)點大于要查找的數(shù)據(jù)，就在左子樹中遞歸執(zhí)行查找動作，直到葉子結(jié)點。

• 如果根結(jié)點小于要查找的數(shù)據(jù)，就在右子樹中遞歸執(zhí)行查找動作，直到葉子結(jié)點。

這樣的“二分查找”所消耗的時間復(fù)雜度就可以降低為 O(logn)。關(guān)于二分查找，后面會在算法部分文章講到。

3.2 插入操作

在二叉查找樹執(zhí)行插入操作也很簡單。從根結(jié)點開始，如果要插入的數(shù)據(jù)比根結(jié)點的數(shù)據(jù)大，且根結(jié)點的右子結(jié)點不為空，則在根結(jié)點的右子樹中繼續(xù)嘗試執(zhí)行插入操作。直到找到為空的子結(jié)點執(zhí)行插入動作。

如下圖所示，如果要插入數(shù)據(jù) X 的值為 14，則需要判斷 X 與根結(jié)點的大小關(guān)系：

• 由于 14 小于 16，則聚焦在其左子樹，繼續(xù)判斷 X 與 13 的關(guān)系。

• 由于 14 大于 13，則聚焦在其右子樹，繼續(xù)判斷 X 與15 的關(guān)系。

• 由于 14 小于 15，則聚焦在其左子樹。

因為此時左子樹為空，則直接通過指針建立 15 結(jié)點的左指針指向結(jié)點 X 的關(guān)系，就完成了插入動作。

二叉查找樹插入數(shù)據(jù)的時間復(fù)雜度是 O(logn)。但這并不意味著它比普通二叉樹要復(fù)雜。原因在于這里的時間復(fù)雜度更多是消耗在了遍歷數(shù)據(jù)去找到查找位置上，真正執(zhí)行插入動作的時間復(fù)雜度仍然是 O(1)。

3.3 刪除操作

二叉查找樹的刪除操作會比較復(fù)雜，這是因為刪除完某個結(jié)點后的樹，仍然要滿足二叉查找樹的性質(zhì)。我們分為下面三種情況討論。

（1）如果要刪除的結(jié)點是某個葉子結(jié)點，則直接刪除，將其父結(jié)點指針指向 null 即可。

（2）如果要刪除的結(jié)點只有一個子結(jié)點，只需要將其父結(jié)點指向的子結(jié)點的指針換成其子結(jié)點的指針即可。
（3）如果要刪除的結(jié)點有兩個子結(jié)點，則有兩種可行的操作方式。

• 第一種，找到這個結(jié)點的左子樹中最大的結(jié)點，替換要刪除的結(jié)點。

• 第二種，找到這個結(jié)點的右子樹中最小的結(jié)點，替換要刪除的結(jié)點。

上述內(nèi)容就是什么是樹、二叉樹以及二叉查找樹，你們學(xué)到知識或技能了嗎？如果還想學(xué)到更多技能或者豐富自己的知識儲備，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

分享題目：什么是樹、二叉樹以及二叉查找樹
網(wǎng)站鏈接：http://jinyejixie.com/article32/ghoisc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供ChatGPT、營銷型網(wǎng)站建設(shè)、網(wǎng)站建設(shè)、搜索引擎優(yōu)化、電子商務(wù)、域名注冊

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)