現(xiàn)，掌握堆與優(yōu)先隊(duì)列的基石)
1. 從“滿”到“完全”二叉樹家族中的效率典范在數(shù)據(jù)結(jié)構(gòu)的世界里二叉樹因其清晰的層次結(jié)構(gòu)和高效的查找、排序能力一直是程序員手中的利器。但二叉樹家族成員眾多從最普通的二叉樹到追求極致平衡的AVL樹、紅黑樹再到我們今天要聊的主角——完全二叉樹它們各有各的脾氣和適用場景。很多朋友在初次接觸“完全二叉樹”時(shí)容易把它和“滿二叉樹”搞混或者覺得這個(gè)概念有點(diǎn)“繞”。其實(shí)完全二叉樹是二叉樹家族中一個(gè)非常特殊且實(shí)用的存在它完美地平衡了存儲效率和操作復(fù)雜度是堆Heap這種重要數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)形態(tài)更是實(shí)現(xiàn)優(yōu)先級隊(duì)列、堆排序等算法的基石。簡單來說你可以把完全二叉樹想象成一座正在建造中的、嚴(yán)格按照從上到下、從左到右順序添磚加瓦的樓房。這座樓房的每一層都必須盡可能地被填滿只有最后一層允許出現(xiàn)空缺并且空缺只能出現(xiàn)在最右邊。這種“近乎滿”的結(jié)構(gòu)特性使得它能夠被高效地存儲在一個(gè)簡單的數(shù)組中從而避免了使用指針鏈?zhǔn)酱鎯淼目臻g開銷和緩存不友好問題。理解完全二叉樹不僅僅是記住定義更是理解其背后“用數(shù)組實(shí)現(xiàn)樹”這一經(jīng)典思想的鑰匙。接下來我們就從定義和特征入手一步步拆解它并最終用C將其實(shí)現(xiàn)出來。2. 定義與特征辨析不僅僅是“看起來整齊”完全二叉樹的定義嚴(yán)謹(jǐn)而精妙。一棵深度為k、有n個(gè)節(jié)點(diǎn)的二叉樹當(dāng)且僅當(dāng)其每一個(gè)節(jié)點(diǎn)都與深度為k的滿二叉樹中編號從1到n的節(jié)點(diǎn)一一對應(yīng)時(shí)這棵樹才被稱為完全二叉樹。這個(gè)定義讀起來有點(diǎn)拗口我們可以用更直觀的方式來理解它的兩個(gè)核心特征特征一層序填充的強(qiáng)制性。這是完全二叉樹最顯著的特點(diǎn)。節(jié)點(diǎn)必須按照層序從上到下從左到右的順序依次放置。這意味著除了最后一層其他所有層的節(jié)點(diǎn)數(shù)都達(dá)到了該層所能容納的最大值即第i層最多有2^(i-1)個(gè)節(jié)點(diǎn)。最后一層的節(jié)點(diǎn)可以不滿但所有節(jié)點(diǎn)必須向左靠齊。也就是說最后一層如果有空缺空缺只能出現(xiàn)在該層的最右邊。特征二與滿二叉樹的編號對應(yīng)關(guān)系。這個(gè)特征是定義中的數(shù)學(xué)化表述也是我們實(shí)現(xiàn)數(shù)組存儲的理論基礎(chǔ)。想象一棵深度為k的滿二叉樹它的節(jié)點(diǎn)從上到下、從左到右連續(xù)編號為 1, 2, 3, ...,2^k - 1。如果一棵樹是完全二叉樹那么它的n個(gè)節(jié)點(diǎn)其形狀和位置必須能和這棵滿二叉樹的前n個(gè)編號節(jié)點(diǎn)完全重合。為了更清晰地與相似概念區(qū)分我們來看一個(gè)對比特性滿二叉樹 (Full Binary Tree)完全二叉樹 (Complete Binary Tree)定義每一層的節(jié)點(diǎn)數(shù)都達(dá)到最大值。即深度為k的樹有2^k - 1個(gè)節(jié)點(diǎn)。深度為k的樹其前k-1層是滿的第k層節(jié)點(diǎn)從左到右連續(xù)排列。形態(tài)一個(gè)完美的三角形沒有任何缺失。一個(gè)“可能被從右下角切掉一小塊”的三角形。最后一層從左到右是連續(xù)的。關(guān)系滿二叉樹一定是完全二叉樹。完全二叉樹不一定是滿二叉樹當(dāng)最后一層未滿時(shí)。示例圖示深度3有7個(gè)節(jié)點(diǎn)每層分別1,2,4個(gè)。深度3可能有6個(gè)節(jié)點(diǎn)最后一層缺最右一個(gè)或7個(gè)節(jié)點(diǎn)此時(shí)為滿二叉樹。注意國內(nèi)一些教材或資料可能會使用不同的術(shù)語例如將“Full Binary Tree”譯為“嚴(yán)格二叉樹”或“正規(guī)二叉樹”其定義為每個(gè)節(jié)點(diǎn)要么有0個(gè)要么有2個(gè)子節(jié)點(diǎn)。這與我們這里討論的“每一層都滿”的“滿二叉樹”是不同的概念。本文采用在堆和優(yōu)先隊(duì)列語境下最常用的定義。在實(shí)際閱讀和討論時(shí)務(wù)必確認(rèn)上下文中的具體含義。一個(gè)常見的誤解與糾正很多人認(rèn)為“葉子節(jié)點(diǎn)只在最后一層”的樹就是完全二叉樹這是不準(zhǔn)確的。例如一棵樹只有左子樹很長右子樹很淺即使葉子節(jié)點(diǎn)都在最大深度那層但由于中間層的節(jié)點(diǎn)沒有盡可能向左靠齊右子樹有空缺它也不是完全二叉樹。判斷的關(guān)鍵在于層序編號的連續(xù)性。3. 核心價(jià)值為什么完全二叉樹如此重要完全二叉樹之所以在計(jì)算機(jī)科學(xué)中占據(jù)核心地位并非因?yàn)樗螤詈每炊窃从谄鋬蓚€(gè)無可替代的實(shí)踐優(yōu)勢。3.1 空間效率完美的數(shù)組映射這是完全二叉樹最強(qiáng)大的特性。對于一棵有n個(gè)節(jié)點(diǎn)的完全二叉樹我們可以將其節(jié)點(diǎn)按層序遍歷順序依次存儲到一個(gè)大小為n的數(shù)組或向量中。此時(shí)節(jié)點(diǎn)之間的父子關(guān)系可以通過簡單的數(shù)組下標(biāo)計(jì)算得到而無需顯式地存儲左、右孩子指針。對于一個(gè)存儲在數(shù)組arr中下標(biāo)從0開始的完全二叉樹節(jié)點(diǎn)其索引為i父節(jié)點(diǎn)索引parent(i) (i - 1) / 2整數(shù)除法。左孩子索引left_child(i) 2 * i 1。右孩子索引right_child(i) 2 * i 2。為什么可以這樣這正是由完全二叉樹的層序連續(xù)性保證的。數(shù)組的第0個(gè)元素就是樹的根節(jié)點(diǎn)。對于任意位置i它的左孩子一定排在它之后并且由于每層都是滿的或從左向右連續(xù)其左孩子在數(shù)組中的位置恰好是2i1。這種計(jì)算關(guān)系是確定且唯一的。帶來的好處節(jié)省空間鏈?zhǔn)酱鎯γ總€(gè)節(jié)點(diǎn)需要至少3個(gè)指針數(shù)據(jù)、左孩、右孩而數(shù)組存儲只需要數(shù)據(jù)本身。在存儲大量數(shù)據(jù)時(shí)節(jié)省的空間非?？捎^。緩存友好數(shù)組在內(nèi)存中是連續(xù)存儲的。遍歷特別是層序遍歷或訪問相鄰節(jié)點(diǎn)時(shí)能有效利用CPU緩存行顯著提高訪問速度。鏈?zhǔn)酱鎯Φ墓?jié)點(diǎn)則可能散落在內(nèi)存各處容易導(dǎo)致緩存失效Cache Miss。實(shí)現(xiàn)簡單無需復(fù)雜的指針操作內(nèi)存管理也更為簡單一個(gè)數(shù)組搞定。3.2 時(shí)間效率對數(shù)級操作復(fù)雜度的基礎(chǔ)完全二叉樹的高度深度是?log?n? 1或O(log n)。這個(gè)對數(shù)級的高度是許多高效算法的基礎(chǔ)。例如堆Heap堆就是一種特殊的完全二叉樹。大頂堆中每個(gè)節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)的值。基于完全二叉樹的堆其插入push和刪除最大/最小元素pop操作的時(shí)間復(fù)雜度都是O(log n)。插入時(shí)新元素被放到數(shù)組末尾對應(yīng)樹最后一層最左邊的空位然后通過“上浮”Sift Up操作沿路徑向上調(diào)整刪除時(shí)將堆頂元素與末尾元素交換刪除末尾然后新的堆頂元素通過“下沉”Sift Down操作向下調(diào)整。這些調(diào)整操作的路徑長度最多為樹高即O(log n)。堆排序Heap Sort利用堆的特性進(jìn)行排序時(shí)間復(fù)雜度為O(n log n)且是原地排序算法。優(yōu)先隊(duì)列Priority Queue通常用堆來實(shí)現(xiàn)保證每次都能在O(1)時(shí)間內(nèi)獲取最高優(yōu)先級的元素并在O(log n)時(shí)間內(nèi)插入或刪除元素。如果沒有完全二叉樹這種結(jié)構(gòu)我們將很難在數(shù)組上實(shí)現(xiàn)如此高效且簡單的O(log n)級調(diào)整操作。正是其結(jié)構(gòu)的規(guī)整性使得通過下標(biāo)計(jì)算就能快速定位父節(jié)點(diǎn)和子節(jié)點(diǎn)從而實(shí)現(xiàn)了高效的“上浮”和“下沉”。4. 算法實(shí)戰(zhàn)判斷給定二叉樹是否為完全二叉樹理解了定義和特征后一個(gè)很自然的實(shí)際問題就是給定一棵二叉樹的根節(jié)點(diǎn)如何用程序判斷它是否是完全二叉樹這是一個(gè)常見的面試題和算法練習(xí)題。其核心思路就是模擬“層序編號”和“連續(xù)填充”的過程。4.1 層序遍歷BFS判定法這是最直觀和常用的方法。我們利用隊(duì)列進(jìn)行廣度優(yōu)先搜索BFS但在遍歷過程中加入對“空節(jié)點(diǎn)”和“連續(xù)性”的檢查。算法步驟將根節(jié)點(diǎn)入隊(duì)。進(jìn)入循環(huán)直到隊(duì)列為空。 a. 隊(duì)頭節(jié)點(diǎn)出隊(duì)記為current。 b.關(guān)鍵檢查點(diǎn)1如果current是空節(jié)點(diǎn)nullptr則跳過后續(xù)子節(jié)點(diǎn)入隊(duì)操作直接進(jìn)入下一輪循環(huán)。但此時(shí)需要設(shè)置一個(gè)標(biāo)志例如end true表示“我們已經(jīng)遇到了第一個(gè)空節(jié)點(diǎn)”。 c.關(guān)鍵檢查點(diǎn)2在后續(xù)的遍歷中如果end標(biāo)志已為真即已遇到過空節(jié)點(diǎn)但又遇到了一個(gè)非空節(jié)點(diǎn)current說明這棵樹在層序排列中出現(xiàn)了“空洞”違反了連續(xù)性原則直接返回false。 d. 如果current非空則無論其左右子節(jié)點(diǎn)是否為空都將其按順序入隊(duì)左孩子先右孩子后。注意這里與普通BFS不同空子節(jié)點(diǎn)也需要入隊(duì)或用一個(gè)特殊標(biāo)記表示因?yàn)槲覀冃枰克鼈儊頇z測連續(xù)性。如果遍歷完所有節(jié)點(diǎn)都沒有觸發(fā)返回false的條件則說明這是一棵完全二叉樹返回true。為什么這個(gè)方法有效它模擬了完全二叉樹必須按層序連續(xù)填充的規(guī)則。一旦在層序序列中遇到了一個(gè)“洞”空節(jié)點(diǎn)那么之后的所有位置在數(shù)組中該位置之后的下標(biāo)都必須為空否則序列就不連續(xù)了。4.2 遞歸與節(jié)點(diǎn)計(jì)數(shù)判定法另一種思路是利用完全二叉樹的性質(zhì)如果一棵樹是完全二叉樹那么當(dāng)它某個(gè)節(jié)點(diǎn)沒有左孩子時(shí)它一定不能有右孩子因?yàn)樘畛浔仨殢淖蟮接?。同時(shí)我們可以計(jì)算樹的節(jié)點(diǎn)總數(shù)和最大深度利用完全二叉樹節(jié)點(diǎn)數(shù)與深度的關(guān)系n 2^h - 1進(jìn)行輔助判斷但這種方法實(shí)現(xiàn)起來稍復(fù)雜且容易出錯(cuò)層序遍歷法更為穩(wěn)健。4.3 C代碼實(shí)現(xiàn)示例下面給出一個(gè)基于層序遍歷BFS的C判斷實(shí)現(xiàn)。我們假設(shè)樹節(jié)點(diǎn)定義為TreeNode。#include queue using namespace std; // 二叉樹節(jié)點(diǎn)定義通常由題目給出 struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; class Solution { public: bool isCompleteTree(TreeNode* root) { if (!root) return true; // 空樹通常被認(rèn)為是完全二叉樹 queueTreeNode* q; q.push(root); bool end false; // 標(biāo)記是否已遇到空節(jié)點(diǎn) while (!q.empty()) { TreeNode* current q.front(); q.pop(); if (current nullptr) { // 遇到第一個(gè)空節(jié)點(diǎn)開啟結(jié)束模式 end true; } else { // 如果已經(jīng)在結(jié)束模式下又遇到了非空節(jié)點(diǎn)說明不連續(xù) if (end) { return false; } // 無論子節(jié)點(diǎn)是否為空都按順序入隊(duì) q.push(current-left); q.push(current-right); } } return true; } };代碼解析與注意事項(xiàng)end變量是整個(gè)算法的靈魂。它初始為false表示我們期待所有節(jié)點(diǎn)都是連續(xù)的。當(dāng)從隊(duì)列中取出一個(gè)nullptr時(shí)我們將其視為樹中層序序列的一個(gè)“空缺”并將end設(shè)為true。這意味著從這個(gè)空缺開始之后在數(shù)組層序序列中所有位置都應(yīng)該是空缺。因此當(dāng)end為true后如果再遇到任何一個(gè)非空的current就說明這個(gè)非空節(jié)點(diǎn)出現(xiàn)在了一個(gè)“應(yīng)該空缺”的位置上序列斷裂樹自然不是完全二叉樹。注意入隊(duì)順序一定是左孩子先右孩子后這保證了我們檢查的序列順序是標(biāo)準(zhǔn)的層序廣度優(yōu)先順序。這個(gè)算法的時(shí)間復(fù)雜度是 O(n)需要遍歷所有節(jié)點(diǎn)一次空間復(fù)雜度在最壞情況下也是 O(n)即隊(duì)列中可能存儲最后一層的所有節(jié)點(diǎn)。5. C簡單實(shí)現(xiàn)一個(gè)基于數(shù)組的完全二叉樹類理論最終要服務(wù)于實(shí)踐。我們現(xiàn)在來動手實(shí)現(xiàn)一個(gè)簡單的、基于數(shù)組這里用std::vector的完全二叉樹類。這個(gè)類將展示如何利用數(shù)組存儲并提供基本的插入、刪除保持完全二叉樹形態(tài)和遍歷操作。5.1 類的設(shè)計(jì)與成員變量我們的CompleteBinaryTree類將使用一個(gè)std::vectorT來存儲元素。為了通用性我們使用模板T。核心操作包括insert(const T value): 在樹末尾插入一個(gè)新元素對應(yīng)層序的下一個(gè)位置這可能會破壞堆的性質(zhì)但我們這里只保證完全二叉樹的結(jié)構(gòu)。removeLast(): 刪除最后一個(gè)元素對應(yīng)層序的最后一個(gè)節(jié)點(diǎn)。getParent(int index),getLeftChild(int index),getRightChild(int index): 根據(jù)下標(biāo)獲取父節(jié)點(diǎn)或子節(jié)點(diǎn)的值。levelOrder(): 進(jìn)行層序遍歷實(shí)際上就是數(shù)組順序。printTree(): 以樹形結(jié)構(gòu)打印輔助理解。#include iostream #include vector #include cmath #include queue template typename T class CompleteBinaryTree { private: std::vectorT data; // 核心存儲數(shù)組 public: CompleteBinaryTree() default; // 獲取當(dāng)前節(jié)點(diǎn)數(shù)量 size_t size() const { return data.size(); } bool empty() const { return data.empty(); } // 獲取根節(jié)點(diǎn)索引0 T root() { if (empty()) throw std::out_of_range(Tree is empty); return data[0]; } const T root() const { if (empty()) throw std::out_of_range(Tree is empty); return data[0]; } // 核心根據(jù)下標(biāo)計(jì)算父子關(guān)系 int getParentIndex(int i) const { if (i 0) return -1; // 根節(jié)點(diǎn)的父節(jié)點(diǎn)不存在 return (i - 1) / 2; } int getLeftChildIndex(int i) const { size_t left 2 * i 1; return (left data.size()) ? left : -1; // 返回-1表示不存在 } int getRightChildIndex(int i) const { size_t right 2 * i 2; return (right data.size()) ? right : -1; // 返回-1表示不存在 } // 通過索引獲取值帶邊界檢查 T getValue(int i) { if (i 0 || i data.size()) throw std::out_of_range(Index out of range); return data[i]; } // 插入新值到完全二叉樹的最后一個(gè)位置 void insert(const T value) { data.push_back(value); // 注意單純的插入操作只保證了結(jié)構(gòu)是完全二叉樹。 // 如果這是一個(gè)堆Heap此處通常還需要一個(gè)“上浮”(siftUp)操作來維護(hù)堆序性質(zhì)。 // siftUp(data.size() - 1); // 堆的插入操作 } // 刪除最后一個(gè)元素 void removeLast() { if (!empty()) { data.pop_back(); } } // 層序遍歷直接返回?cái)?shù)組的副本即可因?yàn)榇鎯樞蚓褪菍有颉?std::vectorT levelOrder() const { return data; // 因?yàn)閐ata本身就是按層序存儲的 } // 以更直觀的樹形格式打印輔助調(diào)試 void printTree() const { if (empty()) { std::cout (empty tree) std::endl; return; } // 計(jì)算樹的高度 int height static_castint(std::log2(data.size())) 1; int index 0; for (int level 0; level height; level) { int nodesInThisLevel std::pow(2, level); int spaces std::pow(2, (height - level)) - 2; // 打印前的空格數(shù)用于居中 // 打印前導(dǎo)空格 for (int s 0; s spaces; s) std::cout ; for (int i 0; i nodesInThisLevel index data.size(); i, index) { std::cout data[index]; // 打印節(jié)點(diǎn)間的間隔 int gap std::pow(2, (height - level 1)) - 2; for (int g 0; g gap; g) std::cout ; } std::cout std::endl std::endl; // 換行并空一行更好看 } } };5.2 使用示例與解析int main() { CompleteBinaryTreeint cbt; // 插入元素順序插入會自然形成完全二叉樹 for (int val : {1, 2, 3, 4, 5, 6, 7}) { cbt.insert(val); } std::cout 樹的大小: cbt.size() std::endl; std::cout 根節(jié)點(diǎn): cbt.root() std::endl; // 獲取特定節(jié)點(diǎn)的父子關(guān)系 int testIndex 2; // 第三個(gè)元素值為3 std::cout 節(jié)點(diǎn)[ testIndex ] cbt.getValue(testIndex) std::endl; int parentIdx cbt.getParentIndex(testIndex); if (parentIdx ! -1) { std::cout 父節(jié)點(diǎn)[ parentIdx ] cbt.getValue(parentIdx) std::endl; } int leftIdx cbt.getLeftChildIndex(testIndex); if (leftIdx ! -1) { std::cout 左孩子[ leftIdx ] cbt.getValue(leftIdx) std::endl; } int rightIdx cbt.getRightChildIndex(testIndex); if (rightIdx ! -1) { std::cout 右孩子[ rightIdx ] cbt.getValue(rightIdx) std::endl; } std::cout \n層序遍歷結(jié)果: ; for (auto val : cbt.levelOrder()) { std::cout val ; } std::cout std::endl; std::cout \n樹形結(jié)構(gòu)打印: std::endl; cbt.printTree(); // 刪除最后一個(gè)元素 cbt.removeLast(); std::cout \n刪除最后一個(gè)元素后的大小: cbt.size() std::endl; std::cout 刪除后的層序遍歷: ; for (auto val : cbt.levelOrder()) { std::cout val ; } std::cout std::endl; return 0; }5.3 實(shí)現(xiàn)要點(diǎn)與踩坑提醒下標(biāo)計(jì)算是核心getParentIndex,getLeftChildIndex,getRightChildIndex這三個(gè)函數(shù)是實(shí)現(xiàn)所有樹操作的基礎(chǔ)。務(wù)必注意整數(shù)除法的特性以及下標(biāo)從0開始的計(jì)算公式。邊界檢查至關(guān)重要在getValue或通過索引訪問父/子節(jié)點(diǎn)時(shí)必須檢查索引是否在有效范圍[0, size())內(nèi)。對于根節(jié)點(diǎn)索引0求父節(jié)點(diǎn)或?qū)θ~子節(jié)點(diǎn)求子節(jié)點(diǎn)都可能產(chǎn)生無效索引我們的代碼通過返回-1來表示。“插入”操作的含義我們這個(gè)基礎(chǔ)類的insert僅僅是將新元素追加到數(shù)組末尾這在結(jié)構(gòu)上保持了完全二叉樹的性質(zhì)。但這不等于堆的插入。堆的插入在push_back之后還需要一個(gè)siftUp上浮操作來維護(hù)堆序父節(jié)點(diǎn)大于/小于子節(jié)點(diǎn)。理解這兩者的區(qū)別很重要完全二叉樹是一種結(jié)構(gòu)堆是一種在此結(jié)構(gòu)上建立的數(shù)據(jù)組織規(guī)則。刪除的復(fù)雜性我們只實(shí)現(xiàn)了removeLast()因?yàn)樗芎唵吻也粫茐耐耆鏄浣Y(jié)構(gòu)。如果要?jiǎng)h除中間某個(gè)節(jié)點(diǎn)并保持完全二叉樹結(jié)構(gòu)標(biāo)準(zhǔn)做法通常是 a. 用最后一個(gè)元素的值覆蓋要?jiǎng)h除的節(jié)點(diǎn)。 b. 刪除最后一個(gè)元素。 c. 然后可能需要像堆一樣進(jìn)行siftDown下沉或siftUp操作來調(diào)整位置如果對元素順序有要求的話。如果只關(guān)心結(jié)構(gòu)步驟a和b就足夠了。內(nèi)存與性能使用std::vector自動管理內(nèi)存其push_back操作在大多數(shù)情況下是攤銷常數(shù)時(shí)間復(fù)雜度。如果需要頻繁在中間“插入”并保持完全二叉樹則不是一個(gè)好主意因?yàn)檫@會涉及大量元素的移動破壞O(log n)的優(yōu)勢。完全二叉樹的典型使用場景如堆都是只在末尾進(jìn)行添加和刪除。6. 從完全二叉樹到堆一個(gè)自然的演進(jìn)我們實(shí)現(xiàn)的CompleteBinaryTree類是一個(gè)“中性”的容器它只保證了形狀是完全二叉樹不關(guān)心節(jié)點(diǎn)之間數(shù)據(jù)的大小關(guān)系。而“堆”則是在此基礎(chǔ)上增加了一條關(guān)鍵的約束規(guī)則堆序性質(zhì)。最大堆每個(gè)節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)的值。因此根節(jié)點(diǎn)是最大值。最小堆每個(gè)節(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)的值。因此根節(jié)點(diǎn)是最小值。只需在我們的CompleteBinaryTree類中添加兩個(gè)私有方法siftUp(int index)和siftDown(int index)并在insert和removeRoot刪除根節(jié)點(diǎn)堆的典型操作中調(diào)用它們我們就能得到一個(gè)可用的堆。siftUp(上浮) 操作當(dāng)在末尾插入一個(gè)新元素后它可能比它的父節(jié)點(diǎn)大對于最大堆。這時(shí)我們需要將它與其父節(jié)點(diǎn)交換并重復(fù)這個(gè)過程直到它不大于其父節(jié)點(diǎn)或者到達(dá)根節(jié)點(diǎn)。這個(gè)過程就像氣泡上浮。void siftUp(int i) { while (i 0 data[i] data[getParentIndex(i)]) { // 最大堆示例 std::swap(data[i], data[getParentIndex(i)]); i getParentIndex(i); } } // 修改insert方法 void insertHeap(const T value) { data.push_back(value); siftUp(data.size() - 1); }siftDown(下沉) 操作當(dāng)根節(jié)點(diǎn)被移除通常用于提取最大/最小值后我們將最后一個(gè)元素移到根節(jié)點(diǎn)。這個(gè)元素可能比它的某個(gè)孩子小。這時(shí)我們需要將它與其較大的那個(gè)孩子對于最大堆交換并重復(fù)這個(gè)過程直到它不小于它的所有孩子或者成為葉子節(jié)點(diǎn)。void siftDown(int i) { int maxIndex i; int left getLeftChildIndex(i); int right getRightChildIndex(i); if (left ! -1 data[left] data[maxIndex]) { // 最大堆示例 maxIndex left; } if (right ! -1 data[right] data[maxIndex]) { maxIndex right; } if (i ! maxIndex) { std::swap(data[i], data[maxIndex]); siftDown(maxIndex); } } // 提取最大值并刪除 T extractMax() { if (empty()) throw std::out_of_range(Heap is empty); T max root(); data[0] data.back(); data.pop_back(); if (!empty()) { siftDown(0); } return max; }通過這個(gè)例子你可以清晰地看到完全二叉樹是堆的物理結(jié)構(gòu)而堆序性質(zhì)是它的邏輯規(guī)則。兩者結(jié)合才誕生了這樣一個(gè)高效的數(shù)據(jù)結(jié)構(gòu)。7. 總結(jié)與擴(kuò)展思考完全二叉樹這個(gè)看似簡單的結(jié)構(gòu)實(shí)則是計(jì)算機(jī)科學(xué)中許多高效算法和數(shù)據(jù)結(jié)構(gòu)的無聲英雄。它的價(jià)值在于將非線性的樹形關(guān)系通過極其規(guī)整的層序排列映射到了線性的、連續(xù)的數(shù)組空間里。這種映射帶來了無與倫比的空間局部性和操作效率?；仡櫼幌潞诵囊c(diǎn)判斷完全二叉樹的關(guān)鍵在于層序序列的連續(xù)性使用BFS配合一個(gè)狀態(tài)標(biāo)志是最穩(wěn)妥的方法。實(shí)現(xiàn)一個(gè)基于數(shù)組的完全二叉樹其核心在于利用下標(biāo)計(jì)算公式parent(i) (i-1)/2,left(i)2*i1,right(i)2*i2來維系節(jié)點(diǎn)間的邏輯關(guān)系。在實(shí)際開發(fā)中你很少需要從頭實(shí)現(xiàn)一個(gè)純粹的完全二叉樹類因?yàn)樗闹饕枧_是作為“堆”的底層容器。C標(biāo)準(zhǔn)庫中的std::priority_queue以及許多語言里的堆實(shí)現(xiàn)都默默地運(yùn)用著完全二叉樹的這些特性。理解它能讓你在用到優(yōu)先隊(duì)列、堆排序或者需要自己實(shí)現(xiàn)一個(gè)調(diào)度器、一個(gè)定時(shí)器隊(duì)列時(shí)明白其性能為何如此卓越以及在什么情況下它是最佳選擇。最后一個(gè)我個(gè)人的體會是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)時(shí)親手實(shí)現(xiàn)一遍哪怕是最簡單的版本和僅僅看懂代碼對概念的理解深度是完全不同的。在實(shí)現(xiàn)這個(gè)CompleteBinaryTree類的過程中去思考“如果我要?jiǎng)h除中間一個(gè)節(jié)點(diǎn)該如何操作才能保持結(jié)構(gòu)”或者“如何將這個(gè)類改造成一個(gè)最小堆”這些問題會驅(qū)使你去深入理解父子下標(biāo)計(jì)算、元素移動等細(xì)節(jié)而這些細(xì)節(jié)正是知識從“知道”到“掌握”的關(guān)鍵跨越。 完全二叉樹：從定義到C++實(shí)現(xiàn)，掌握堆與優(yōu)先隊(duì)列的基石
1. 從“滿”到“完全”二叉樹家族中的效率典范在數(shù)據(jù)結(jié)構(gòu)的世界里二叉樹因其清晰的層次結(jié)構(gòu)和高效的查找、排序能力一直是程序員手中的利器。但二叉樹家族成員眾多從最普通的二叉樹到追求極致平衡的AVL樹、紅黑樹再到我們今天要聊的主角——完全二叉樹它們各有各的脾氣和適用場景。很多朋友在初次接觸“完全二叉樹”時(shí)容易把它和“滿二叉樹”搞混或者覺得這個(gè)概念有點(diǎn)“繞”。其實(shí)完全二叉樹是二叉樹家族中一個(gè)非常特殊且實(shí)用的存在它完美地平衡了存儲效率和操作復(fù)雜度是堆Heap這種重要數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)形態(tài)更是實(shí)現(xiàn)優(yōu)先級隊(duì)列、堆排序等算法的基石。簡單來說你可以把完全二叉樹想象成一座正在建造中的、嚴(yán)格按照從上到下、從左到右順序添磚加瓦的樓房。這座樓房的每一層都必須盡可能地被填滿只有最后一層允許出現(xiàn)空缺并且空缺只能出現(xiàn)在最右邊。這種“近乎滿”的結(jié)構(gòu)特性使得它能夠被高效地存儲在一個(gè)簡單的數(shù)組中從而避免了使用指針鏈?zhǔn)酱鎯淼目臻g開銷和緩存不友好問題。理解完全二叉樹不僅僅是記住定義更是理解其背后“用數(shù)組實(shí)現(xiàn)樹”這一經(jīng)典思想的鑰匙。接下來我們就從定義和特征入手一步步拆解它并最終用C將其實(shí)現(xiàn)出來。2. 定義與特征辨析不僅僅是“看起來整齊”完全二叉樹的定義嚴(yán)謹(jǐn)而精妙。一棵深度為k、有n個(gè)節(jié)點(diǎn)的二叉樹當(dāng)且僅當(dāng)其每一個(gè)節(jié)點(diǎn)都與深度為k的滿二叉樹中編號從1到n的節(jié)點(diǎn)一一對應(yīng)時(shí)這棵樹才被稱為完全二叉樹。這個(gè)定義讀起來有點(diǎn)拗口我們可以用更直觀的方式來理解它的兩個(gè)核心特征特征一層序填充的強(qiáng)制性。這是完全二叉樹最顯著的特點(diǎn)。節(jié)點(diǎn)必須按照層序從上到下從左到右的順序依次放置。這意味著除了最后一層其他所有層的節(jié)點(diǎn)數(shù)都達(dá)到了該層所能容納的最大值即第i層最多有2^(i-1)個(gè)節(jié)點(diǎn)。最后一層的節(jié)點(diǎn)可以不滿但所有節(jié)點(diǎn)必須向左靠齊。也就是說最后一層如果有空缺空缺只能出現(xiàn)在該層的最右邊。特征二與滿二叉樹的編號對應(yīng)關(guān)系。這個(gè)特征是定義中的數(shù)學(xué)化表述也是我們實(shí)現(xiàn)數(shù)組存儲的理論基礎(chǔ)。想象一棵深度為k的滿二叉樹它的節(jié)點(diǎn)從上到下、從左到右連續(xù)編號為 1, 2, 3, ...,2^k - 1。如果一棵樹是完全二叉樹那么它的n個(gè)節(jié)點(diǎn)其形狀和位置必須能和這棵滿二叉樹的前n個(gè)編號節(jié)點(diǎn)完全重合。為了更清晰地與相似概念區(qū)分我們來看一個(gè)對比特性滿二叉樹 (Full Binary Tree)完全二叉樹 (Complete Binary Tree)定義每一層的節(jié)點(diǎn)數(shù)都達(dá)到最大值。即深度為k的樹有2^k - 1個(gè)節(jié)點(diǎn)。深度為k的樹其前k-1層是滿的第k層節(jié)點(diǎn)從左到右連續(xù)排列。形態(tài)一個(gè)完美的三角形沒有任何缺失。一個(gè)“可能被從右下角切掉一小塊”的三角形。最后一層從左到右是連續(xù)的。關(guān)系滿二叉樹一定是完全二叉樹。完全二叉樹不一定是滿二叉樹當(dāng)最后一層未滿時(shí)。示例圖示深度3有7個(gè)節(jié)點(diǎn)每層分別1,2,4個(gè)。深度3可能有6個(gè)節(jié)點(diǎn)最后一層缺最右一個(gè)或7個(gè)節(jié)點(diǎn)此時(shí)為滿二叉樹。注意國內(nèi)一些教材或資料可能會使用不同的術(shù)語例如將“Full Binary Tree”譯為“嚴(yán)格二叉樹”或“正規(guī)二叉樹”其定義為每個(gè)節(jié)點(diǎn)要么有0個(gè)要么有2個(gè)子節(jié)點(diǎn)。這與我們這里討論的“每一層都滿”的“滿二叉樹”是不同的概念。本文采用在堆和優(yōu)先隊(duì)列語境下最常用的定義。在實(shí)際閱讀和討論時(shí)務(wù)必確認(rèn)上下文中的具體含義。一個(gè)常見的誤解與糾正很多人認(rèn)為“葉子節(jié)點(diǎn)只在最后一層”的樹就是完全二叉樹這是不準(zhǔn)確的。例如一棵樹只有左子樹很長右子樹很淺即使葉子節(jié)點(diǎn)都在最大深度那層但由于中間層的節(jié)點(diǎn)沒有盡可能向左靠齊右子樹有空缺它也不是完全二叉樹。判斷的關(guān)鍵在于層序編號的連續(xù)性。3. 核心價(jià)值為什么完全二叉樹如此重要完全二叉樹之所以在計(jì)算機(jī)科學(xué)中占據(jù)核心地位并非因?yàn)樗螤詈每炊窃从谄鋬蓚€(gè)無可替代的實(shí)踐優(yōu)勢。3.1 空間效率完美的數(shù)組映射這是完全二叉樹最強(qiáng)大的特性。對于一棵有n個(gè)節(jié)點(diǎn)的完全二叉樹我們可以將其節(jié)點(diǎn)按層序遍歷順序依次存儲到一個(gè)大小為n的數(shù)組或向量中。此時(shí)節(jié)點(diǎn)之間的父子關(guān)系可以通過簡單的數(shù)組下標(biāo)計(jì)算得到而無需顯式地存儲左、右孩子指針。對于一個(gè)存儲在數(shù)組arr中下標(biāo)從0開始的完全二叉樹節(jié)點(diǎn)其索引為i父節(jié)點(diǎn)索引parent(i) (i - 1) / 2整數(shù)除法。左孩子索引left_child(i) 2 * i 1。右孩子索引right_child(i) 2 * i 2。為什么可以這樣這正是由完全二叉樹的層序連續(xù)性保證的。數(shù)組的第0個(gè)元素就是樹的根節(jié)點(diǎn)。對于任意位置i它的左孩子一定排在它之后并且由于每層都是滿的或從左向右連續(xù)其左孩子在數(shù)組中的位置恰好是2i1。這種計(jì)算關(guān)系是確定且唯一的。帶來的好處節(jié)省空間鏈?zhǔn)酱鎯γ總€(gè)節(jié)點(diǎn)需要至少3個(gè)指針數(shù)據(jù)、左孩、右孩而數(shù)組存儲只需要數(shù)據(jù)本身。在存儲大量數(shù)據(jù)時(shí)節(jié)省的空間非?？捎^。緩存友好數(shù)組在內(nèi)存中是連續(xù)存儲的。遍歷特別是層序遍歷或訪問相鄰節(jié)點(diǎn)時(shí)能有效利用CPU緩存行顯著提高訪問速度。鏈?zhǔn)酱鎯Φ墓?jié)點(diǎn)則可能散落在內(nèi)存各處容易導(dǎo)致緩存失效Cache Miss。實(shí)現(xiàn)簡單無需復(fù)雜的指針操作內(nèi)存管理也更為簡單一個(gè)數(shù)組搞定。3.2 時(shí)間效率對數(shù)級操作復(fù)雜度的基礎(chǔ)完全二叉樹的高度深度是?log?n? 1或O(log n)。這個(gè)對數(shù)級的高度是許多高效算法的基礎(chǔ)。例如堆Heap堆就是一種特殊的完全二叉樹。大頂堆中每個(gè)節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)的值。基于完全二叉樹的堆其插入push和刪除最大/最小元素pop操作的時(shí)間復(fù)雜度都是O(log n)。插入時(shí)新元素被放到數(shù)組末尾對應(yīng)樹最后一層最左邊的空位然后通過“上浮”Sift Up操作沿路徑向上調(diào)整刪除時(shí)將堆頂元素與末尾元素交換刪除末尾然后新的堆頂元素通過“下沉”Sift Down操作向下調(diào)整。這些調(diào)整操作的路徑長度最多為樹高即O(log n)。堆排序Heap Sort利用堆的特性進(jìn)行排序時(shí)間復(fù)雜度為O(n log n)且是原地排序算法。優(yōu)先隊(duì)列Priority Queue通常用堆來實(shí)現(xiàn)保證每次都能在O(1)時(shí)間內(nèi)獲取最高優(yōu)先級的元素并在O(log n)時(shí)間內(nèi)插入或刪除元素。如果沒有完全二叉樹這種結(jié)構(gòu)我們將很難在數(shù)組上實(shí)現(xiàn)如此高效且簡單的O(log n)級調(diào)整操作。正是其結(jié)構(gòu)的規(guī)整性使得通過下標(biāo)計(jì)算就能快速定位父節(jié)點(diǎn)和子節(jié)點(diǎn)從而實(shí)現(xiàn)了高效的“上浮”和“下沉”。4. 算法實(shí)戰(zhàn)判斷給定二叉樹是否為完全二叉樹理解了定義和特征后一個(gè)很自然的實(shí)際問題就是給定一棵二叉樹的根節(jié)點(diǎn)如何用程序判斷它是否是完全二叉樹這是一個(gè)常見的面試題和算法練習(xí)題。其核心思路就是模擬“層序編號”和“連續(xù)填充”的過程。4.1 層序遍歷BFS判定法這是最直觀和常用的方法。我們利用隊(duì)列進(jìn)行廣度優(yōu)先搜索BFS但在遍歷過程中加入對“空節(jié)點(diǎn)”和“連續(xù)性”的檢查。算法步驟將根節(jié)點(diǎn)入隊(duì)。進(jìn)入循環(huán)直到隊(duì)列為空。 a. 隊(duì)頭節(jié)點(diǎn)出隊(duì)記為current。 b.關(guān)鍵檢查點(diǎn)1如果current是空節(jié)點(diǎn)nullptr則跳過后續(xù)子節(jié)點(diǎn)入隊(duì)操作直接進(jìn)入下一輪循環(huán)。但此時(shí)需要設(shè)置一個(gè)標(biāo)志例如end true表示“我們已經(jīng)遇到了第一個(gè)空節(jié)點(diǎn)”。 c.關(guān)鍵檢查點(diǎn)2在后續(xù)的遍歷中如果end標(biāo)志已為真即已遇到過空節(jié)點(diǎn)但又遇到了一個(gè)非空節(jié)點(diǎn)current說明這棵樹在層序排列中出現(xiàn)了“空洞”違反了連續(xù)性原則直接返回false。 d. 如果current非空則無論其左右子節(jié)點(diǎn)是否為空都將其按順序入隊(duì)左孩子先右孩子后。注意這里與普通BFS不同空子節(jié)點(diǎn)也需要入隊(duì)或用一個(gè)特殊標(biāo)記表示因?yàn)槲覀冃枰克鼈儊頇z測連續(xù)性。如果遍歷完所有節(jié)點(diǎn)都沒有觸發(fā)返回false的條件則說明這是一棵完全二叉樹返回true。為什么這個(gè)方法有效它模擬了完全二叉樹必須按層序連續(xù)填充的規(guī)則。一旦在層序序列中遇到了一個(gè)“洞”空節(jié)點(diǎn)那么之后的所有位置在數(shù)組中該位置之后的下標(biāo)都必須為空否則序列就不連續(xù)了。4.2 遞歸與節(jié)點(diǎn)計(jì)數(shù)判定法另一種思路是利用完全二叉樹的性質(zhì)如果一棵樹是完全二叉樹那么當(dāng)它某個(gè)節(jié)點(diǎn)沒有左孩子時(shí)它一定不能有右孩子因?yàn)樘畛浔仨殢淖蟮接?。同時(shí)我們可以計(jì)算樹的節(jié)點(diǎn)總數(shù)和最大深度利用完全二叉樹節(jié)點(diǎn)數(shù)與深度的關(guān)系n 2^h - 1進(jìn)行輔助判斷但這種方法實(shí)現(xiàn)起來稍復(fù)雜且容易出錯(cuò)層序遍歷法更為穩(wěn)健。4.3 C代碼實(shí)現(xiàn)示例下面給出一個(gè)基于層序遍歷BFS的C判斷實(shí)現(xiàn)。我們假設(shè)樹節(jié)點(diǎn)定義為TreeNode。#include queue using namespace std; // 二叉樹節(jié)點(diǎn)定義通常由題目給出 struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; class Solution { public: bool isCompleteTree(TreeNode* root) { if (!root) return true; // 空樹通常被認(rèn)為是完全二叉樹 queueTreeNode* q; q.push(root); bool end false; // 標(biāo)記是否已遇到空節(jié)點(diǎn) while (!q.empty()) { TreeNode* current q.front(); q.pop(); if (current nullptr) { // 遇到第一個(gè)空節(jié)點(diǎn)開啟結(jié)束模式 end true; } else { // 如果已經(jīng)在結(jié)束模式下又遇到了非空節(jié)點(diǎn)說明不連續(xù) if (end) { return false; } // 無論子節(jié)點(diǎn)是否為空都按順序入隊(duì) q.push(current-left); q.push(current-right); } } return true; } };代碼解析與注意事項(xiàng)end變量是整個(gè)算法的靈魂。它初始為false表示我們期待所有節(jié)點(diǎn)都是連續(xù)的。當(dāng)從隊(duì)列中取出一個(gè)nullptr時(shí)我們將其視為樹中層序序列的一個(gè)“空缺”并將end設(shè)為true。這意味著從這個(gè)空缺開始之后在數(shù)組層序序列中所有位置都應(yīng)該是空缺。因此當(dāng)end為true后如果再遇到任何一個(gè)非空的current就說明這個(gè)非空節(jié)點(diǎn)出現(xiàn)在了一個(gè)“應(yīng)該空缺”的位置上序列斷裂樹自然不是完全二叉樹。注意入隊(duì)順序一定是左孩子先右孩子后這保證了我們檢查的序列順序是標(biāo)準(zhǔn)的層序廣度優(yōu)先順序。這個(gè)算法的時(shí)間復(fù)雜度是 O(n)需要遍歷所有節(jié)點(diǎn)一次空間復(fù)雜度在最壞情況下也是 O(n)即隊(duì)列中可能存儲最后一層的所有節(jié)點(diǎn)。5. C簡單實(shí)現(xiàn)一個(gè)基于數(shù)組的完全二叉樹類理論最終要服務(wù)于實(shí)踐。我們現(xiàn)在來動手實(shí)現(xiàn)一個(gè)簡單的、基于數(shù)組這里用std::vector的完全二叉樹類。這個(gè)類將展示如何利用數(shù)組存儲并提供基本的插入、刪除保持完全二叉樹形態(tài)和遍歷操作。5.1 類的設(shè)計(jì)與成員變量我們的CompleteBinaryTree類將使用一個(gè)std::vectorT來存儲元素。為了通用性我們使用模板T。核心操作包括insert(const T value): 在樹末尾插入一個(gè)新元素對應(yīng)層序的下一個(gè)位置這可能會破壞堆的性質(zhì)但我們這里只保證完全二叉樹的結(jié)構(gòu)。removeLast(): 刪除最后一個(gè)元素對應(yīng)層序的最后一個(gè)節(jié)點(diǎn)。getParent(int index),getLeftChild(int index),getRightChild(int index): 根據(jù)下標(biāo)獲取父節(jié)點(diǎn)或子節(jié)點(diǎn)的值。levelOrder(): 進(jìn)行層序遍歷實(shí)際上就是數(shù)組順序。printTree(): 以樹形結(jié)構(gòu)打印輔助理解。#include iostream #include vector #include cmath #include queue template typename T class CompleteBinaryTree { private: std::vectorT data; // 核心存儲數(shù)組 public: CompleteBinaryTree() default; // 獲取當(dāng)前節(jié)點(diǎn)數(shù)量 size_t size() const { return data.size(); } bool empty() const { return data.empty(); } // 獲取根節(jié)點(diǎn)索引0 T root() { if (empty()) throw std::out_of_range(Tree is empty); return data[0]; } const T root() const { if (empty()) throw std::out_of_range(Tree is empty); return data[0]; } // 核心根據(jù)下標(biāo)計(jì)算父子關(guān)系 int getParentIndex(int i) const { if (i 0) return -1; // 根節(jié)點(diǎn)的父節(jié)點(diǎn)不存在 return (i - 1) / 2; } int getLeftChildIndex(int i) const { size_t left 2 * i 1; return (left data.size()) ? left : -1; // 返回-1表示不存在 } int getRightChildIndex(int i) const { size_t right 2 * i 2; return (right data.size()) ? right : -1; // 返回-1表示不存在 } // 通過索引獲取值帶邊界檢查 T getValue(int i) { if (i 0 || i data.size()) throw std::out_of_range(Index out of range); return data[i]; } // 插入新值到完全二叉樹的最后一個(gè)位置 void insert(const T value) { data.push_back(value); // 注意單純的插入操作只保證了結(jié)構(gòu)是完全二叉樹。 // 如果這是一個(gè)堆Heap此處通常還需要一個(gè)“上浮”(siftUp)操作來維護(hù)堆序性質(zhì)。 // siftUp(data.size() - 1); // 堆的插入操作 } // 刪除最后一個(gè)元素 void removeLast() { if (!empty()) { data.pop_back(); } } // 層序遍歷直接返回?cái)?shù)組的副本即可因?yàn)榇鎯樞蚓褪菍有颉?std::vectorT levelOrder() const { return data; // 因?yàn)閐ata本身就是按層序存儲的 } // 以更直觀的樹形格式打印輔助調(diào)試 void printTree() const { if (empty()) { std::cout (empty tree) std::endl; return; } // 計(jì)算樹的高度 int height static_castint(std::log2(data.size())) 1; int index 0; for (int level 0; level height; level) { int nodesInThisLevel std::pow(2, level); int spaces std::pow(2, (height - level)) - 2; // 打印前的空格數(shù)用于居中 // 打印前導(dǎo)空格 for (int s 0; s spaces; s) std::cout ; for (int i 0; i nodesInThisLevel index data.size(); i, index) { std::cout data[index]; // 打印節(jié)點(diǎn)間的間隔 int gap std::pow(2, (height - level 1)) - 2; for (int g 0; g gap; g) std::cout ; } std::cout std::endl std::endl; // 換行并空一行更好看 } } };5.2 使用示例與解析int main() { CompleteBinaryTreeint cbt; // 插入元素順序插入會自然形成完全二叉樹 for (int val : {1, 2, 3, 4, 5, 6, 7}) { cbt.insert(val); } std::cout 樹的大小: cbt.size() std::endl; std::cout 根節(jié)點(diǎn): cbt.root() std::endl; // 獲取特定節(jié)點(diǎn)的父子關(guān)系 int testIndex 2; // 第三個(gè)元素值為3 std::cout 節(jié)點(diǎn)[ testIndex ] cbt.getValue(testIndex) std::endl; int parentIdx cbt.getParentIndex(testIndex); if (parentIdx ! -1) { std::cout 父節(jié)點(diǎn)[ parentIdx ] cbt.getValue(parentIdx) std::endl; } int leftIdx cbt.getLeftChildIndex(testIndex); if (leftIdx ! -1) { std::cout 左孩子[ leftIdx ] cbt.getValue(leftIdx) std::endl; } int rightIdx cbt.getRightChildIndex(testIndex); if (rightIdx ! -1) { std::cout 右孩子[ rightIdx ] cbt.getValue(rightIdx) std::endl; } std::cout \n層序遍歷結(jié)果: ; for (auto val : cbt.levelOrder()) { std::cout val ; } std::cout std::endl; std::cout \n樹形結(jié)構(gòu)打印: std::endl; cbt.printTree(); // 刪除最后一個(gè)元素 cbt.removeLast(); std::cout \n刪除最后一個(gè)元素后的大小: cbt.size() std::endl; std::cout 刪除后的層序遍歷: ; for (auto val : cbt.levelOrder()) { std::cout val ; } std::cout std::endl; return 0; }5.3 實(shí)現(xiàn)要點(diǎn)與踩坑提醒下標(biāo)計(jì)算是核心getParentIndex,getLeftChildIndex,getRightChildIndex這三個(gè)函數(shù)是實(shí)現(xiàn)所有樹操作的基礎(chǔ)。務(wù)必注意整數(shù)除法的特性以及下標(biāo)從0開始的計(jì)算公式。邊界檢查至關(guān)重要在getValue或通過索引訪問父/子節(jié)點(diǎn)時(shí)必須檢查索引是否在有效范圍[0, size())內(nèi)。對于根節(jié)點(diǎn)索引0求父節(jié)點(diǎn)或?qū)θ~子節(jié)點(diǎn)求子節(jié)點(diǎn)都可能產(chǎn)生無效索引我們的代碼通過返回-1來表示。“插入”操作的含義我們這個(gè)基礎(chǔ)類的insert僅僅是將新元素追加到數(shù)組末尾這在結(jié)構(gòu)上保持了完全二叉樹的性質(zhì)。但這不等于堆的插入。堆的插入在push_back之后還需要一個(gè)siftUp上浮操作來維護(hù)堆序父節(jié)點(diǎn)大于/小于子節(jié)點(diǎn)。理解這兩者的區(qū)別很重要完全二叉樹是一種結(jié)構(gòu)堆是一種在此結(jié)構(gòu)上建立的數(shù)據(jù)組織規(guī)則。刪除的復(fù)雜性我們只實(shí)現(xiàn)了removeLast()因?yàn)樗芎唵吻也粫茐耐耆鏄浣Y(jié)構(gòu)。如果要?jiǎng)h除中間某個(gè)節(jié)點(diǎn)并保持完全二叉樹結(jié)構(gòu)標(biāo)準(zhǔn)做法通常是 a. 用最后一個(gè)元素的值覆蓋要?jiǎng)h除的節(jié)點(diǎn)。 b. 刪除最后一個(gè)元素。 c. 然后可能需要像堆一樣進(jìn)行siftDown下沉或siftUp操作來調(diào)整位置如果對元素順序有要求的話。如果只關(guān)心結(jié)構(gòu)步驟a和b就足夠了。內(nèi)存與性能使用std::vector自動管理內(nèi)存其push_back操作在大多數(shù)情況下是攤銷常數(shù)時(shí)間復(fù)雜度。如果需要頻繁在中間“插入”并保持完全二叉樹則不是一個(gè)好主意因?yàn)檫@會涉及大量元素的移動破壞O(log n)的優(yōu)勢。完全二叉樹的典型使用場景如堆都是只在末尾進(jìn)行添加和刪除。6. 從完全二叉樹到堆一個(gè)自然的演進(jìn)我們實(shí)現(xiàn)的CompleteBinaryTree類是一個(gè)“中性”的容器它只保證了形狀是完全二叉樹不關(guān)心節(jié)點(diǎn)之間數(shù)據(jù)的大小關(guān)系。而“堆”則是在此基礎(chǔ)上增加了一條關(guān)鍵的約束規(guī)則堆序性質(zhì)。最大堆每個(gè)節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)的值。因此根節(jié)點(diǎn)是最大值。最小堆每個(gè)節(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)的值。因此根節(jié)點(diǎn)是最小值。只需在我們的CompleteBinaryTree類中添加兩個(gè)私有方法siftUp(int index)和siftDown(int index)并在insert和removeRoot刪除根節(jié)點(diǎn)堆的典型操作中調(diào)用它們我們就能得到一個(gè)可用的堆。siftUp(上浮) 操作當(dāng)在末尾插入一個(gè)新元素后它可能比它的父節(jié)點(diǎn)大對于最大堆。這時(shí)我們需要將它與其父節(jié)點(diǎn)交換并重復(fù)這個(gè)過程直到它不大于其父節(jié)點(diǎn)或者到達(dá)根節(jié)點(diǎn)。這個(gè)過程就像氣泡上浮。void siftUp(int i) { while (i 0 data[i] data[getParentIndex(i)]) { // 最大堆示例 std::swap(data[i], data[getParentIndex(i)]); i getParentIndex(i); } } // 修改insert方法 void insertHeap(const T value) { data.push_back(value); siftUp(data.size() - 1); }siftDown(下沉) 操作當(dāng)根節(jié)點(diǎn)被移除通常用于提取最大/最小值后我們將最后一個(gè)元素移到根節(jié)點(diǎn)。這個(gè)元素可能比它的某個(gè)孩子小。這時(shí)我們需要將它與其較大的那個(gè)孩子對于最大堆交換并重復(fù)這個(gè)過程直到它不小于它的所有孩子或者成為葉子節(jié)點(diǎn)。void siftDown(int i) { int maxIndex i; int left getLeftChildIndex(i); int right getRightChildIndex(i); if (left ! -1 data[left] data[maxIndex]) { // 最大堆示例 maxIndex left; } if (right ! -1 data[right] data[maxIndex]) { maxIndex right; } if (i ! maxIndex) { std::swap(data[i], data[maxIndex]); siftDown(maxIndex); } } // 提取最大值并刪除 T extractMax() { if (empty()) throw std::out_of_range(Heap is empty); T max root(); data[0] data.back(); data.pop_back(); if (!empty()) { siftDown(0); } return max; }通過這個(gè)例子你可以清晰地看到完全二叉樹是堆的物理結(jié)構(gòu)而堆序性質(zhì)是它的邏輯規(guī)則。兩者結(jié)合才誕生了這樣一個(gè)高效的數(shù)據(jù)結(jié)構(gòu)。7. 總結(jié)與擴(kuò)展思考完全二叉樹這個(gè)看似簡單的結(jié)構(gòu)實(shí)則是計(jì)算機(jī)科學(xué)中許多高效算法和數(shù)據(jù)結(jié)構(gòu)的無聲英雄。它的價(jià)值在于將非線性的樹形關(guān)系通過極其規(guī)整的層序排列映射到了線性的、連續(xù)的數(shù)組空間里。這種映射帶來了無與倫比的空間局部性和操作效率?；仡櫼幌潞诵囊c(diǎn)判斷完全二叉樹的關(guān)鍵在于層序序列的連續(xù)性使用BFS配合一個(gè)狀態(tài)標(biāo)志是最穩(wěn)妥的方法。實(shí)現(xiàn)一個(gè)基于數(shù)組的完全二叉樹其核心在于利用下標(biāo)計(jì)算公式parent(i) (i-1)/2,left(i)2*i1,right(i)2*i2來維系節(jié)點(diǎn)間的邏輯關(guān)系。在實(shí)際開發(fā)中你很少需要從頭實(shí)現(xiàn)一個(gè)純粹的完全二叉樹類因?yàn)樗闹饕枧_是作為“堆”的底層容器。C標(biāo)準(zhǔn)庫中的std::priority_queue以及許多語言里的堆實(shí)現(xiàn)都默默地運(yùn)用著完全二叉樹的這些特性。理解它能讓你在用到優(yōu)先隊(duì)列、堆排序或者需要自己實(shí)現(xiàn)一個(gè)調(diào)度器、一個(gè)定時(shí)器隊(duì)列時(shí)明白其性能為何如此卓越以及在什么情況下它是最佳選擇。最后一個(gè)我個(gè)人的體會是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)時(shí)親手實(shí)現(xiàn)一遍哪怕是最簡單的版本和僅僅看懂代碼對概念的理解深度是完全不同的。在實(shí)現(xiàn)這個(gè)CompleteBinaryTree類的過程中去思考“如果我要?jiǎng)h除中間一個(gè)節(jié)點(diǎn)該如何操作才能保持結(jié)構(gòu)”或者“如何將這個(gè)類改造成一個(gè)最小堆”這些問題會驅(qū)使你去深入理解父子下標(biāo)計(jì)算、元素移動等細(xì)節(jié)而這些細(xì)節(jié)正是知識從“知道”到“掌握”的關(guān)鍵跨越。