什么是樹、二叉樹以及二叉查找樹

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

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

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

一、樹與二叉樹

1.1 什么是樹？

樹是一種數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=1）個(gè)有限結(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做“樹”是因?yàn)樗雌饋硐褚豢玫箳斓臉?，也就是說它是根朝上，而葉朝下的。

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

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

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

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

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

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

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

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

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

• 根為第一層，比如：A

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

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

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

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

1.2 什么是二叉樹？

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

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

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

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

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

• 鏈?zhǔn)酱鎯Ψ?，也就是像鏈表一樣，每個(gè)結(jié)點(diǎn)有三個(gè)字段，一個(gè)存儲數(shù)據(jù)，另外兩個(gè)分別存放指向左右子結(jié)點(diǎn)的指針，如下圖所示：

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

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

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

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

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

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

在“一對一”的結(jié)構(gòu)中，查找具有某個(gè)數(shù)值，可以直接按順序遍歷每一條數(shù)據(jù)。可是，樹是“一對多”的關(guān)系，那該按什么順序遍歷呢？

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

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

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

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

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

三、二叉查找樹的特性

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

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

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

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

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

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

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

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

3.1 查找操作

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

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

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

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

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

3.2 插入操作

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

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

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

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

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

因?yàn)榇藭r(shí)左子樹為空，則直接通過指針建立 15 結(jié)點(diǎn)的左指針指向結(jié)點(diǎn) X 的關(guān)系，就完成了插入動作。

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

3.3 刪除操作

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

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

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

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

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

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