前言

歡迎蒞臨姜行運主頁
https://blog.csdn.net/2401_84320036?type=blog
歡迎指導本人數據結構專欄(https://blog.csdn.net/2401_84320036/category_12950167.html)

1.樹

1.1樹的概念和結構

定義：樹是一種非線性的數據結構，它是由 n(n>=0)個有限結點組成?個具有層次關系的集合。為什么叫樹，因為它看起來像一棵倒掛的樹。

• 有一個特殊的結點，稱為根結點，根結點沒有前驅結點。
• 除了根結點外，每個結點有且僅有一個父結點。
• 子樹不相交。
• 一棵N個結點的樹有N-1條邊。

1.2樹的相關術語

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

1.3樹的表示方法

struct TreeNode
{struct Node* child; // 左邊開始的第?個孩?結點struct Node* brother; // 指向其右邊的下?個兄弟結點int data; // 結點中的數據域
};

1.4 樹形結構實際運用場景

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

2.二叉樹

2.1二叉樹的概念和結構

在樹形結構中，常用的就是二叉樹，?棵二叉樹是結點的?個有限集合，該集合由（?個根結點加上兩棵別稱為左子樹和右用樹的二叉樹組成）或者為（空）。

2.2二叉樹具備以下特點：

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

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

2.3二叉樹分類

1. 滿二叉樹
2. 完全二叉樹

3.滿二叉樹

一個二叉樹，如果每一層的結點數都達到最大值，則這個二叉樹就是滿二叉樹。
如果?
個?叉樹的層數為 K ，且結點總數是
，則它就是滿二叉樹。
等比數列計算，從二的指數從零到一計算。

4.完全二叉樹

除了最后一層，其他每層的結點個數都達到最大，最后一層結點個數不一定最大，最后一次的結點按照順序由左到右依次排列。

5.二叉樹性質

根據滿二叉樹的特點可知：

6.附：樹和二叉樹圖示