個人主頁，點擊這里~
數據結構專欄，點擊這里~

一、樹

1.1什么是樹？

這是我們生活中常見的樹：

（以上圖片來自網絡，如若侵權聯系自刪）

生活中許多東西都可以抽象成為一棵樹，例如一本書的目錄：

它們都像自然界中的樹一樣，從根衍生出許多枝干，再由枝干衍生出許多更小的枝干，最終衍生出了許多葉子。

1.2 樹的概念與結構

樹是?種非線性的數據結構，它是由n（n>=0）個有限結點組成?個具有層次關系的集合。把它叫做樹是因為它看起來像?棵倒掛的樹，也就是說它是根朝上，而葉朝下的。

• 有?個特殊的結點，稱為根結點，根結點沒有前驅結點。
• 除根結點外，其余結點被分成 M(M>0) 個互不相交的集合 T1、T2、……、Tm ，其中每?個集合Ti(1 <= i <= m) 又是?棵結構與樹類似的子樹。每棵子樹的根結點有且只有?個前驅，可以有 0 個或多個后繼。因此，樹是遞歸定義的。

注意：樹形結構中，子樹之間不能有交集，否則就不是樹形結構。

非樹形結構：

關于樹：

• 子樹是不相交的（如果存在相交就是圖了）；
• 除了根結點外，每個結點有且僅有?個父結點；
• ?棵N個結點的樹有N-1條邊！

1.3樹的相關術語

父結點/雙親結點：若?個結點含有子結點，則這個結點稱為其子結點的父結點；如上圖：A是B的父結點。
子結點/孩子結點：?個結點含有的子樹的根結點稱為該結點的子結點； 如上圖：B是A的孩子結點。
結點的度：?個結點有幾個孩子，它的度就是多少；比如A的度為6，F的度為2，K的度為0。
樹的度：?棵樹中，最大的結點的度稱為樹的度； 如上圖：樹的度為 6。
葉子結點/終端結點：度為 0 的結點稱為葉結點； 如上圖：B、C、H、I...等結點為葉結點。
分支結點/非終端結點：度不為0的結點； 如上圖：D、E、F、G...等結點為分支結點。
兄弟結點：具有相同父結點的結點互稱為兄弟結點(親兄弟)； 如上圖：B、C 是兄弟結點。
結點的層次：從根開始定義起，根為第 1 層，根的子結點為第 2 層，以此類推；
樹的高度或深度：樹中結點的最大層次； 如上圖：樹的高度為 4。
結點的祖先：從根到該結點所經分支上的所有結點；如上圖： A 是所有結點的祖先。
路徑：?條從樹中任意節點出發，沿父節點-子節點連接，達到任意節點的序列；比如A到Q的路徑為：A-E-J-Q；H到Q的路徑H-D-A-E-J-Q。
子孫：以某結點為根的子樹中任?結點都稱為該結點的子孫。如上圖：所有結點都是A的子孫。
森林：由 m（m>0） 棵互不相交的樹的集合稱為森林；

1.4 樹形結構實際運用場景

文件系統是計算機存儲和管理文件的?種方式，它利用樹形結構來組織和管理文件和文件夾。在文件系統中，樹結構被?泛應?，它通過父結點和子結點之間的關系來表示不同層級的文件和文件夾之間的關聯。

二、二叉樹

2.1 概念與結構

在樹形結構中，我們最常用的就是二叉樹，?棵二叉樹是結點的?個有限集合，該集合由?個根結點加上兩棵別稱為左子樹和右子樹的二叉樹組成，或者為空。
從上圖可以看出二叉樹具備以下特點：

• 二叉樹不存在度大于 2 的結點。
• 二叉樹的子樹有左右之分，次序不能顛倒，因此?叉樹是有序樹。

注意：對于任意的二叉樹都是由以下幾種情況復合而成的：

自然界的二叉樹：

（以上圖片來自網絡，如若侵權聯系自刪）

2.2 特殊的二叉樹

2.2.1 滿二叉樹

一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果?個二叉樹的層數為 K ，且結點總數是 2^k ? 1，則它就是滿二叉樹。

2.2.2 完全二叉樹

完全二叉樹是效率很高的數據結構，完全二叉樹是由滿二叉樹而引出來的。對于深度為 K 的，有 n 個結點的二叉樹，當且僅當其每?個結點都與深度為K的滿二叉樹中編號從 1 ?n 的結點??對應時稱之為完全二叉樹。要注意的是滿二叉樹是?種特殊的完全二叉樹。

注意：這里如果J是E的右孩子樹，那就不是一一對應的關系了，那這棵樹就不是完全二叉樹。

特點：

• 除了最后一層，每層結點個數達到最大。
• 最后一層結點個數不一定達到最大。
• 結點從左到右依次排列。

二叉樹的性質：

• 若規定根結點的層數為 1 ，則?棵非空二叉樹的第i層上最多有 2ⁱ?1 個結點。
• 若規定根結點的層數為 1 ，則深度為 h 的二叉樹的最大結點數是 2^h ? 1。
• 若規定根結點的層數為 1 ，具有 n 個結點的滿二叉樹的深度 h = log(2) (n + 1) 。( log以2為底， n+1 為對數)。

總結：
以上就是本期博客分享的全部內容啦！如果覺得文章還不錯的話可以三連支持一下，你的支持就是我前進最大的動力！
技術的探索永無止境! 道阻且長，行則將至！后續我會給大家帶來更多優質博客內容，歡迎關注我的CSDN賬號，我們一同成長！
(～￣▽￣)～