目錄
- 前言
- 回顧
- 樹形結構
- 樹的概念
- 有序樹，無序樹，森林
- 二叉樹（Binary Tree）
- 真二叉樹（Proper Binary Tree）
- 滿二叉樹（Full Binary Tree）
- 完全二叉樹（Complete Binary Tree）
- 小結
- 宣告
前言
回顧
在前面的資料結構學習中，無論是以順序結構存盤的 陣列 還是鏈式存盤結構的 鏈表、堆疊與佇列 等(沒有閱讀過之前的隨筆，可以點擊對應的名詞跳轉) ，實際上都可以歸類成線性結構，
今天復習另外一種資料結構，樹形結構，沒錯，就是生活中的那種樹，要倒過來的那種，
以樹干的分支數量為準，可以將樹分為二叉樹與多叉樹，二叉樹是我們要研究的重點
生活中的樹形結構也有很多，例如公司的股權圖，檔案目錄等等，使用樹形結構可以大大提高效率，同時樹形結構也是被廣泛應用于底層結構，例如資料庫索引
樹形結構
樹的概念
節點：根節點、父節點、子節點、兄弟節點
空樹：一棵樹可以沒有任何節點
一棵樹可以只有1個節點，也就是只有根節點
子樹：左子樹、右子樹
節點的度（degree）：子樹的個數
樹的度：所有節點度中的最大值
葉子節點（leaf）：度為 0 的節點
非葉子節點：度不為 0 的節點
層數（level）：根節點在第1層，根節點的子節點在第2層，以此類推（有些教程也從第0層開始計算）
節點的深度（depth）：從根節點到當前節點的唯一路徑上的節點總數
節點的高度（height）：從當前節點到最遠葉子節點的路徑上的節點總數
樹的深度：所有節點深度中的最大值
樹的高度：所有節點高度中的最大值
樹的深度等于樹的高度
有序樹，無序樹，森林
有序樹
- 樹中任意節點的子節點之間有順序關系
無序樹
- 樹中任意節點的子節點之間沒有順序關系，也稱為“自由樹”
森林
- 由m（m≥0）棵互不相交的樹組成的集合
二叉樹（Binary Tree）
1、二叉樹的特點
- 每個節點的度最大為2（最多擁有2棵子樹）
- 左子樹和右子樹是有順序的（有序樹）
- 即使某節點只有一棵子樹，也要區分左右子樹
2、二叉樹圖解
3、二叉樹的性質
- 非空二叉樹的第 i 層，最多有 $2^{i-1}$ 個節點（i ≥ 1）
- 在高度為 h 的二叉樹上最多有$2^{h-1}$個結點（h ≥ 1）
- 對于任何一棵非空二叉樹，如果葉子節點個數為n0，度為2的節點個數為n2，則有: n0 = n2 + 1
- 假設度為1的節點個數為n1，那么二叉樹的節點總數n= n0 + n1 + n2
- 二叉樹的邊數T = n1 + 2 * n2 = n–1 = n0 + n1 + n2–1
- 因此n0 = n2 + 1
真二叉樹（Proper Binary Tree）
概念：所有節點的度都要么為 0，要么為 2
滿二叉樹（Full Binary Tree）
概念：最后一層節點的度都為0，其他節點的度都為2
性質：
- 假設滿二叉樹的高度為h（h≥1），那么有：
- 第i層的節點數量： $2^{i-1}$
- 葉子節點數量： $2^{h-1}$
- 總節點數量 n，則 n = $2^h-1$ = $2^0$ + $2^1$ + $2^2$ + ... + $2^{h-1}$
- h = $\log_2n+1$
- 同樣高度的二叉樹中，滿二叉樹的葉子節點數量最多、總節點數量最多
- 滿二叉樹一定是真二叉樹，真二叉樹不一定是滿二叉樹
圖解：
完全二叉樹（Complete Binary Tree）
概念：葉子節點只會出現最后 2 層，且最后 1 層的葉子結點都靠左對齊
完全二叉樹與滿二叉樹是很相似的，所以也可以這么定義，完全二叉樹：對節點從上至下、左至右開始編號，其所有編號都能與相同高度的滿二叉樹中的編號對應
小結論：1、完全二叉樹從根結點至倒數第2層是一棵滿二叉樹，2、滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹
性質：
-
度為 1 的節點只有左子樹，度為1的節點要么是 1 個，要么是 0 個
-
同樣節點數量的二叉樹，完全二叉樹的高度最小（從上往下，從左往右滿排布）
-
假設完全二叉樹的高度為h（h ≥ 1），那么有：
- 至少有$2^{h?1}$個節點， $2^0$ + $2^1$ + $2^2$ + ... + $2^{h-2}$ + 1
- 最多有$2^h?1$個節點( 滿二叉樹 )， $2^0$ + $2^1$ + $2^2$ + ... + $2^{h-1}$
-
假設總節點數量為 n
- $2^{h?1}$ <= $2^h$
- $h-1$ <= $\log_2n$ < $h$
- $h$ = foor $(\log_2n) + 1$
floor是向下取整，另外，ceiling是向上取整
-
-
例題鞏固：如果一棵完全二叉樹有768個節點，求葉子節點的個數
求解：
- 假設葉子節點個數為n0，度為1的節點個數為n1，度為2的節點個數為n2，總結點個數為n，則
n = n0 + n1 + n2，且n0 = n2 + 1 - 等式替換：
n = 2n0 + n1 – 1 - 完全二叉樹的 n1 要么為 0，要么為 1
- (1) n1為1時，n = 2n0，n必然是偶數，葉子節點個數n0 = n / 2，非葉子節點個數n1 + n2 = n / 2
- (2) n1為0時，n = 2n0–1，n必然是奇數，葉子節點個數n0 = (n + 1) / 2，非葉子節點個數n1 + n2 = (n–1) / 2
結論：
- 葉子節點個數n0 = floor((n + 1) / 2) = ceiling(n / 2)
- 非葉子節點個數n1 + n2 = floor(n / 2) = ceiling((n–1) / 2)
- 因此葉子節點個數n0 = 384
小結
1、對于樹的一些基本概念要牢記，否則，你連筆試題目都看不懂
2、一些樹的性質是要記住的，不要覺得公式沒用，不然，代碼都敲不出來
3、對著目錄過一遍，樹的概念，以此作為筆記寫下，好記性不如爛筆頭
宣告
個人能力有限，有不正確的地方，還請指正
文章為原創，歡迎轉載，注明出處即可
文章有代碼的會上傳github,歡迎star
GitHub地址
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/37701.html
標籤：其他
上一篇：git 快速入門及常見用法