【數據結構】二叉樹、堆

文章目錄

二叉樹的概念及結構
- 定義
- 特殊的二叉樹
- 核心性質
- 存儲方式
二叉樹的鏈式存儲
- 前序遍歷
- 中序遍歷
- 后序遍歷
- 層序遍歷
二叉樹的順序存儲
- 父子關系的推導
- 堆（heap）
- - 堆的概念
  - 向上調整算法和向下調整算法
  - - 向上調整算法
    - 向下調整算法
  - 堆的創建
  - 堆的插入
  - 堆的刪除
- 堆的應用
- - 堆排序
  - TOP-K 問題

二叉樹的概念及結構

定義

二叉樹是每個節點最多有兩個子節點的樹結構，分別稱為左子節點和右子節點。子樹區分左右順序，即使僅有一個子節點也需明確方向。二叉樹可以為空（無節點）。

特殊的二叉樹

滿二叉樹：所有非葉子節點均有左右子節點，且所有葉子在同一層。
完全二叉樹：除最后一層外，其他層節點全滿，最后一層從左到右連續填充。
平衡二叉樹：任意節點左右子樹高度差不超過1（如AVL樹）。
二叉搜索樹（BST）：左子樹節點均小于根，右子樹節點均大于根。

核心性質

節點關系：
- 每個節點最多有兩個子節點
- 若樹的高度為 h，則最大節點數為 2^h - 1（即滿二叉樹的情況）
層次與深度：
- 根節點位于第一層（或第零層，依定義不同）
- 根節點的深度為從根節點到該節點的路徑長度

存儲方式

鏈式存儲：
- 節點包含數據、左指針和右指針。
- 靈活，適合動態增刪。
順序存儲（數組）：
- 適用于完全二叉樹，父節點下標 i 的左子節點為 2i，右子節點為 2i + 1
- 非完全二叉樹可能浪費存儲空間。

二叉樹的鏈式存儲

根據定義，我們很容易就知道二叉樹節點分為一個數據域和兩個分別指向左右子樹的指針域，于是就有：

typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}TreeNode;

對于鏈式結構的二叉樹，我們主要得掌握它的三種深度優先遍歷和一種層序遍歷的方式
對于三種深度優先遍歷，它這個前、中、后指的是根節點的前、中、后。

前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根節點的操作發生在遍歷其左右子樹之前。
中序遍歷(Inorder Traversal)——訪問根節點的操作發生在遍歷其左右子樹之中（間）。
后序遍歷(Postorder Traversal)——訪問根節點的操作發生在遍歷其左右子樹之后。

前序遍歷

因為是遞歸調用，所以代碼極其簡單

void PrevOrder(TreeNode* root)
{if (root == NULL){printf("N\n");return;}printf("%d ", root->data); // 訪問根節點PrevOrder(root->left);	   // 訪問左子樹PrevOrder(root->right);	   // 訪問右子樹
}

中序遍歷

void InOrder(TreeNode* root)
{if (root == NULL){printf("N\n");return;}InOrder(root->left);		// 訪問左子樹printf("%d ", root->data);	// 訪問根節點InOrder(root->right);		// 訪問右子樹
}

后序遍歷

void PostOrder(TreeNode* root)
{if (root == NULL){printf("N\n");return;}PostOrder(root->left);		// 訪問左子樹PostOrder(root->right);		// 訪問右子樹printf("%d ", root->data);	// 訪問根節點
}

從代碼中，我們不難看出，這三種遍歷方式僅是訪問根節點的時機不同。

層序遍歷

對于層序遍歷，也就是字面意思，我們需要按層逐層訪問節點。
那么如何做到呢？
這就得使用一個隊列去保存樹中的節點。
首先讓根節點入隊列，當隊列不為空的時候，取出隊列中隊頭節點，訪問該節點的元素。然后判斷該節點是否存在左右節點，存在則入隊列。重復這個過程直到隊列為空

vector<int> breadthFirstTraversal(TreeNode* root) {vector<int> result;		   // 用于存放層序遍歷的結果if (!root) return result;  // 處理空樹情況queue<TreeNode*> q;		   // 創建隊列q.push(root);			   // 根節點入隊列while (!q.empty()) {	   // 直到隊列為空TreeNode* current = q.front();	// 取隊頭節點q.pop();						result.push_back(current->val);	// 將該節點的元素放入數組中if (current->left) q.push(current->left);	// 存在左節點就入隊列if (current->right) q.push(current->right);	// 存在右節點就入隊列}return result;
}

注釋寫的已經很清楚了，應該能看懂吧。
考慮到可能有些同學剛接觸二叉樹，可能看不懂這代碼。沒事，先有個印象就行了，等到后面對于數據結構的理解加深自然就理解了。

二叉樹的順序存儲

普通的二叉樹并不適合使用順序存儲，因為這可能會導致大量的空間浪費。在使用順序存儲時，一定是完全二叉樹。
父子下標關系本質上是完全二叉樹層序遍歷在數組中的直接映射：

左子下標 = 父下標 x 2（根從1開始）或父下標 x 2 + 1（根從0開始）
右子下標 = 左子下標 + 1

父子關系的推導

因為數組是從 0 下標開始的，所以這里就以根節點從 0 開始推導

完全二叉樹的層次遍歷特性
完全二叉樹的節點按層次遍歷順序連續存儲在數組中，且滿足以下性質：

第 k 層的節點數：2^k
第 k 層的起始下標：2^k - 1
第 k 層的第 m 個節點的下標：2^k - 1 + m

父子節點位置關系

父節點在第 k 層第 m 個位置：
- 下標：i = 2^k - 1 + m
左子節點在第 k+1 層的第 2m 個位置：
- 下標：left_child = 2^k+1 - 1 + 2m
- 代入 $i=2^k-1+m$ ，化簡得：
  left_child = 2i + 1
右子節點為左子節點下標 + 1
- right_child = 2i + 2

推導就到這里，數學好點的同學可以使用數學歸納法來證明一下。markdown的語法不太好寫，這里就不再證明了

堆（heap）

說起二叉樹的順序存儲就不得不提堆了。如果你存的數據都是些非常雜亂的，且你對它并沒有做出些什么修正，那你用二叉樹干嘛？搞得這么花里胡哨，不如直接使用數組。而堆就不一樣了。

堆的概念

堆（Heap）是一種特殊的完全二叉樹，具有以下核心性質，可分為 最大堆 和 最小堆 兩種類型：

性質：

結構性：完全二叉樹

堆在邏輯上是完全二叉樹，所有層（除最后一層）節點全滿，最后一層節點從左到右連續填充。
順序存儲實現：通常用數組存儲，利用下標關系快速定位父子節點：

堆序性：節點值的有序性

最大堆（Max-Heap）：
- 每個節點的值 ≥ 其子節點的值。
- 根節點是樹中的最大值。
最小堆（Min-Heap）：
- 每個節點的值 ≤ 其子節點的值。
- 根節點是樹中的最小值。

核心操作與性質維護
堆通過以下操作維護其性質：
1. 插入（Insert）：
  - 新元素插入末尾，通過上浮（Percolate Up）調整位置。
  - 時間復雜度：O(logN)
2. 刪除堆頂（Extract-Max/Min）：
  - 移除堆頂元素，將末尾元素移至堆頂，通過下沉（Percolate Down）調整位置。
  - 時間復雜度：O(logN)

向上調整算法和向下調整算法

在建堆之前，我們需要理解向上調整和向下調整算法。
以小堆為例

向上調整算法

向上調整算法，聽名字就知道是向上比較，那么就是孩子節點（我們選擇的節點）與父節點的比較。
使用場景：插入新元素后，將其從堆尾逐步向上調整到合適位置

void AdjustUp(HDataType* a, int child)
{int parent = (child - 1) / 2;	// 通過下標關系計算出父節點下標while (child > 0)				// 當子節點下標大于 0 時就繼續調整{if (a[child] < a[parent])	// 這里以小堆為例，所以子小于父的時候交換兩節點數據，將小的元素往上調{Swap(&a[parent], &a[child]);child = parent;parent = (child - 1) / 2;}else{break; // 到達合適位置的時候跳出循環}}
}

向下調整算法

向下調整需要一直調整到葉子節點

void AdjustDown(HDataType* a, int n, int parent)
{// 假設左孩子小int child = parent * 2 + 1;while (child < n) // child >= n說明孩子不存在，調整到葉子了{// 找出小的那個孩子，確保child指向的是小的孩子節點if (child + 1 < n && a[child + 1] < a[child]){++child;}if (a[child] < a[parent])	// 孩子節點比父節點小就進行交換{Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;	// 到合適的位置跳出循環}}
}

堆的創建

建堆有兩種方法：

一種是不斷插入新節點（新節點肯定是葉子節點啦），插入一個節點就對其進行一次向上調整，直到建好堆。
還有一種是將已知的數組視為一個堆，從最后一個非葉子節點開始進行向下調整，直到調整到根節點。

那么這兩種建堆方式推薦使用哪種呢？
推薦使用向下調整的方式建堆！

為什么呢？因為更快。
這里很明確的告訴你向上調整建堆的時間復雜度是 O(Nlog N)，而向下調整建堆的時間復雜度是 O(N)。
具體的證明這里就不寫了，有興趣的同學可以自己去推導一下，這里只說明個大概。

向上調整建堆，越深的節點，它要調整的次數越多（根節點到它的距離），并且越深的節點數量越多（在滿二叉樹的情況下）。
而向下調整建堆，越深的節點，它要調整的次數越少（它到葉子節點的距離），并且越深的節點數量越多。
那么在二者數量相同的情況下，向上調整：
（一層里）數量多的節點要調整的次數多，（一層里）數量少的節點調整的次數少。
向下調整：
（一層里）數量多的節點要調整的次數少，（一層里）數量少的節點調整的次數多。
很明顯向下調整的次數更少，并且向下調整本身要調整的節點數量就小于向上調整要調整的節點數量，很明顯向下調整建堆更快。

堆的插入

插入位置是在葉子節點，直接將其向上調整

void HeapPush(Heap* ph, HDataType x)
{assert(ph);if (ph->size == ph->capacity){int newcapacity = ph->capacity == 0 ? 4 : ph->capacity * 2;HDataType* tmp = (HDataType*)realloc(ph->a, newcapacity * sizeof(HDataType));if (tmp == NULL){perror("realloc fail!\n");return;}ph->a = tmp;ph->capacity = newcapacity;}ph->a[ph->size++] = x;AdjustUp(ph->a, ph->size - 1);
}

堆的刪除

因為堆刪除只能刪除堆頂元素。
將堆頂元素和堆尾元素交換，刪除掉原先的堆頂元素，再將新的堆頂元素向下調整即可。
解釋：
以小堆為例，原先堆頂元素是整個堆中最小的，而堆尾元素肯定是大于原先的堆頂的，且會大于中間層的幾個元素，將其放到堆頂，而向下調整又是將父節點的兩個子節點中更小的那個調整上去，自然就能夠保證堆頂為新的最小元素。

void HeapPop(Heap* ph)
{assert(ph);assert(ph->size > 0);Swap(&ph->a[0], &ph->a[ph->size - 1]);ph->size--;AdjustDown(ph->a, ph->size, 0);
}

堆的應用

堆排序

很明顯，是將數組排序，那么只要對需要排序的數組進行向下調整建堆，分為兩個步驟：

建堆
- 升序：建大堆
- 降序：建小堆
利用堆刪除的思想來進行排序

這兩個步驟都是使用了向下調整算法，所以其實理解了向下調整算法，那么堆排序也挺簡單的。

TOP-K 問題

找出 n 個元素中，前 K 大的元素。
直接建堆再取 K 次堆頂即可。
當然，如果 n 的值非常非常大，也可以維護一個 K 大小的堆，對整個數據遍歷一遍，最后剩下來的 K 個數據便是我們所需要的答案。

我記得前幾年的藍橋杯省賽中 c++ b、c組中就有幾題需要用到這個，就自己實現一下 node 節點，再不斷地對堆頂進行操作，出堆，入堆，有興趣的話也可以自己去找來看看。