溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇文章為大家展示了什么是樹、二叉樹以及二叉查找樹，內容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細介紹希望你能有所收獲。
說起樹，大家都不陌生，畢竟是日常生活中常見的事物。但是今天的主角不是樹木，我們來聊聊數據結構中的樹、二叉樹和二叉查找樹，以及它們的基本操作！
一、樹與二叉樹
樹是一種數據結構，它是由n（n>=1）個有限結點組成一個具有層次關系的集合。把它叫做“樹”是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。
樹是由結點和邊組成的，不存在環的一種數據結構。通過下圖，我們就可以更直觀的認識樹的結構。
樹滿足遞歸定義的特性。也就是說，如果一個數據結構是樹結構，那么剔除掉根結點后，得到的若干個子結構也是樹，通常稱作子樹。
在一棵樹中，根據結點之間層次關系的不同，對結點的稱呼也有所不同。我們來看下面這棵樹，如下圖所示:
不同結點的關系與稱呼如下：
A 結點是 B 結點和 C 結點的上級，則 A 就是 B 和 C 的父結點，B 和 C 是 A 的子結點。
B 和 C 同時是 A 的“孩子”，則可以稱 B 和 C 互為兄弟結點。
A 沒有父結點，則可以稱 A 為根結點。
G、H、I、F 結點都沒有子結點，則稱 G、H、I、F 為葉子結點。
當有了一棵樹之后，還需要用深度、層來描述這棵樹中結點的位置。如上圖所示，結點的層次從根結點算起：
根為第一層，比如：A
根的“孩子”為第二層，比如B、C
根的“孩子”的“孩子”為第三層，比如D、E、F
依此類推，第四層（最后一層）就是：G、H、I
樹中結點的最大層次數，就是這棵樹的樹深（稱為深度，也稱為高度）因此這是一棵深度為 4 的樹。
在樹的大家族中，有一種被高頻使用的特殊樹，它就是二叉樹。在二叉樹中，每個結點最多有兩個分支，即每個結點最多有兩個子結點，分別稱作左子結點和右子結點。
在二叉樹中，有兩個最為特殊的類型，如下圖所示：
滿二叉樹，定義為除了葉子結點外，所有結點都有 2 個子結點。
完全二叉樹，定義為除了最后一層以外，其他層的結點個數都達到最大，并且最后一層的葉子結點都靠左排列。
你可能會困惑，完全二叉樹看上去并不完全，但為什么這樣稱呼它呢？這其實和二叉樹的存儲有關系。存儲二叉樹有兩種辦法，一種是基于指針的鏈式存儲法，另一種是基于數組的順序存儲法。
鏈式存儲法，也就是像鏈表一樣，每個結點有三個字段，一個存儲數據，另外兩個分別存放指向左右子結點的指針，如下圖所示：
順序存儲法，就是按照規律把結點存放在數組里，如下圖所示，為了方便計算，我們會約定把根結點放在下標為 1 的位置。隨后，B 結點存放在下標為 2 的位置，C 結點存放在下標為 3 的位置，依次類推。
之所以稱為完全二叉樹，是從存儲空間利用效率的視角來看的。對于一棵完全二叉樹而言，僅僅浪費了下標為 0 的存儲位置。而如果是一棵非完全二叉樹，則會浪費大量的存儲空間。
如下圖所示的非完全二叉樹，它既需要保留出 5 和 6 的位置。同時，還需要保留 5 的兩個子結點 10 和 11 的位置，以及 6 的兩個子結點 12 和 13 的位置。這樣的二叉樹，沒有完全利用好數組的存儲空間。
接下來，我們以二叉樹為例介紹樹的操作，其他類型的樹的操作與二叉樹基本相似。
可以發現，我們以前學到的數據結構都是“一對一”的關系，即前面的數據只跟下面的一個數據產生了連接關系，例如鏈表、棧、隊列等。而樹結構則是“一對多”的關系，即前面的父結點，跟下面若干個子結點產生了連接關系。
在“一對一”的結構中，查找具有某個數值，可以直接按順序遍歷每一條數據。可是，樹是“一對多”的關系，那該按什么順序遍歷呢？
其實，遍歷一棵樹，有非常經典的三種方法，分別是前序遍歷、中序遍歷、后序遍歷。這里的序指的是父結點的遍歷順序，前序就是先遍歷父結點，中序就是中間遍歷父結點，后序就是最后遍歷父結點。
不管哪種遍歷，都是通過遞歸調用完成的。如下圖所示：
前序遍歷，對樹中的任意結點來說，先打印這個結點，然后前序遍歷它的左子樹，最后前序遍歷它的右子樹。
中序遍歷，對樹中的任意結點來說，先中序遍歷它的左子樹，然后打印這個結點，最后中序遍歷它的右子樹。
后序遍歷，對樹中的任意結點來說，先后序遍歷它的左子樹，然后后序遍歷它的右子樹，最后打印它本身。
對于沒有任何特殊性質的二叉樹而言，拋開遍歷的時間復雜度以外，真正執行增加和刪除操作的時間復雜度是 O(1)。樹數據的查找操作和鏈表一樣，都需要遍歷每一個數據去判斷，所以時間復雜度是 O(n)。
但當二叉樹具備一些特性的時候（比如二叉查找樹），則可以利用這些特性實現時間復雜度的降低。
二叉查找樹（也稱作二叉搜索樹）具備以下幾個的特性：
在二叉查找樹中的任意一個結點，其左子樹中的每個結點的值，都要小于這個結點的值；其右子樹中每個結點的值，都要大于這個結點的值。
在二叉查找樹中，會盡可能規避兩個結點數值相等的情況。
對二叉查找樹進行中序遍歷，就可以輸出一個從小到大的有序數據隊列。如下圖所示，中序遍歷的結果就是 10、13、15、16、20、21、22、26。
所以二叉查找樹可以簡單的認為是，是一個按規則排好序的二叉樹。
在利用二叉查找樹執行查找操作時，我們可以進行以下判斷：
首先判斷根結點是否等于要查找的數據，如果是就返回。
如果根結點大于要查找的數據，就在左子樹中遞歸執行查找動作，直到葉子結點。
如果根結點小于要查找的數據，就在右子樹中遞歸執行查找動作，直到葉子結點。
這樣的“二分查找”所消耗的時間復雜度就可以降低為 O(logn)。關于二分查找，后面會在算法部分文章講到。
在二叉查找樹執行插入操作也很簡單。從根結點開始，如果要插入的數據比根結點的數據大，且根結點的右子結點不為空，則在根結點的右子樹中繼續嘗試執行插入操作。直到找到為空的子結點執行插入動作。
如下圖所示，如果要插入數據 X 的值為 14，則需要判斷 X 與根結點的大小關系：
由于 14 小于 16，則聚焦在其左子樹，繼續判斷 X 與 13 的關系。
由于 14 大于 13，則聚焦在其右子樹，繼續判斷 X 與15 的關系。
由于 14 小于 15，則聚焦在其左子樹。
因為此時左子樹為空，則直接通過指針建立 15 結點的左指針指向結點 X 的關系，就完成了插入動作。
二叉查找樹插入數據的時間復雜度是 O(logn)。但這并不意味著它比普通二叉樹要復雜。原因在于這里的時間復雜度更多是消耗在了遍歷數據去找到查找位置上，真正執行插入動作的時間復雜度仍然是 O(1)。
二叉查找樹的刪除操作會比較復雜，這是因為刪除完某個結點后的樹，仍然要滿足二叉查找樹的性質。我們分為下面三種情況討論。
（1）如果要刪除的結點是某個葉子結點，則直接刪除，將其父結點指針指向 null 即可。
（2）如果要刪除的結點只有一個子結點，只需要將其父結點指向的子結點的指針換成其子結點的指針即可。
（3）如果要刪除的結點有兩個子結點，則有兩種可行的操作方式。
第一種，找到這個結點的左子樹中最大的結點，替換要刪除的結點。
第二種，找到這個結點的右子樹中最小的結點，替換要刪除的結點。
上述內容就是什么是樹、二叉樹以及二叉查找樹，你們學到知識或技能了嗎？如果還想學到更多技能或者豐富自己的知識儲備，歡迎關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
