# 樹的專題進階思考

?

author ： chase

time： 2022-4-30

前言

以前實現過了基本的樹結構，包括基本二叉樹、AVLTree、BSTree、BTree、RBTree、tire Tree等，詳情見一月版樹總結。

Data-structure/tree樹專題(二叉、bbst、avl、bt、rbt).pdf at main · hanfeijiang/Data-structure · GitHub

但是隨著學習的深入，有接觸到了很多其他的知識，有了很多思考和啟發，例如操作系統和數據庫中的樹、并查集和大根堆的邏輯樹結構、樹的拓撲等價等等知識都在這里做一個補充； 還有一些以前沒實現的結構： 比如huffman樹、線索樹、表達式樹等；還有一些樹存儲方式的補充，每種方式其實都對應了一種應用，這也是以前沒有注意到的，就比如說孩子表示法對應哈希表、雙親表示法對應并查集......

常用公式

重要的拿到前面總結一下：

n0 = n2 + 1，對于任何二叉樹成立

下面是對于Complete Binary Tree而言的：

第一個非葉子結點序號： size/2

葉子結點個數： size - size/2

2度節點個數： size - size/2 - 1

1度節點個數： 1，最多只能有一個，且只有左子樹沒有右子樹

• 二叉樹

• 滿二叉樹（極限葉子數）

同樣高度的二叉樹中，滿二叉樹的葉子節點數量最多、總節點數量最多；

• 完全二叉樹（Complete Binary Tree）

? 葉子節點只會出現最后 2 層，最后 1 層的葉子結點都靠左對齊 ? 完全二叉樹從根結點至倒數第 2 層是一棵滿二叉樹 ? 滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹

? 相同節點數，完全二叉樹的高度最低

樹的存儲方式

順序存儲（二叉）

以前只學過鏈表表示二叉樹（雖然這種方式比較靈活），現在補充幾種順序的存儲。

順序存儲的應用：

1.構建(完全)二叉堆。因為堆的需求僅僅是找到最大值或者最小值，因此僅僅使用完全二叉樹即可(一顆有一定大小排序規則的完全二叉樹，不同于二叉搜索樹，其對搜索的需求不高，因此對層數的需求不大，沒必要使用平衡樹)

2.并查集(嚴格來說，并查集已經不是二叉樹了而是多叉樹，只不過也是用順序表實現的)

二叉樹的順序存儲，指的是使用順序表（數組）存儲二叉樹。需要注意的是，順序存儲一般適用于完全二叉樹。換句話說，只有完全二叉樹才可以使用順序表存儲。因此，如果我們想順序存儲普通二叉樹，需要提前將普通二叉樹轉化為完全二叉樹。

普通二叉樹轉完全二叉樹的方法很簡單，只需給二叉樹額外添加一些節點，將其"拼湊"成完全二叉樹即可。如1 所示：

圖 1 普通二叉樹的轉化

圖 1 中，左側是普通二叉樹，右側是轉化后的完全（滿）二叉樹。

解決了二叉樹的轉化問題，接下來學習如何順序存儲完全（滿）二叉樹。

完全二叉樹的順序存儲，僅需從根節點開始，按照層次依次將樹中節點存儲到數組即可。

圖 2 完全二叉樹示意圖

例如，存儲圖 2 所示的完全二叉樹，其存儲狀態如圖 3 所示：

圖 3 完全二叉樹存儲狀態示意圖

同樣，存儲由普通二叉樹轉化來的完全二叉樹也是如此。例如，圖 1 中普通二叉樹的數組存儲狀態如圖 4 所示：

圖 4 普通二叉樹的存儲狀態

由此，我們就實現了完全二叉樹的順序存儲。

不僅如此，從順序表中還原完全二叉樹也很簡單。我們知道，完全二叉樹具有這樣的性質，將樹中節點按照層次并從左到右依次標號（1,2,3,...），若節點 i 有左右孩子，則其左孩子節點為 2i，右孩子節點為 2i+1。此性質可用于還原數組中存儲的完全二叉樹，也就是實現由圖 3 到圖 2、由圖 4 到圖 1 的轉變。

順序存儲的缺陷：

空間利用率不高。因為采用的是完全二叉樹架構，因此有很多空位無法填入。

只能層序遍歷，功能受限制

只能適合存儲和遍歷，對于AVL樹、紅黑樹等需要復雜操作的樹不合適，沒有使用鏈式結構方便。

普通樹的表示結構

以前只關注了二叉樹，因為有具體功能的AVL樹、紅黑樹、BST、b樹都是用二叉/三叉鏈表結構實現的。但是如果有一顆普通的樹，也應該能用一個結構來表示。

• 兄弟孩子表示法： 普通樹和二叉樹的邏輯轉換

• 雙親表示法： 并查集

• 孩子表示法： 類似哈希表結構

普通樹轉換為二叉樹存儲-兄弟孩子表示法

《計算之魂》

其實把任意一顆樹轉換為二叉樹的方法也可以按照孩子兄弟方法存放這棵樹。

本質上上面那本書里面并沒有給定每個節點應該有什么指針，孩子兄弟表示法詳細說明了兩種指針的類型：

向右指的指針：sibling指針，指向一串兄弟節點

向下指的指針：child指針，指向孩子節點

用 C 語言代碼表示節點結構為：

?#define ElemType chartypedef struct CSNode{ElemType data;struct CSNode * firstchild,*nextsibling;}CSNode,*CSTree;

• 普通樹的前中后序遍歷和二叉樹保持一致，又因為樹的作用往往就是存儲和遍歷，因此任意樹的存儲和遍歷可以等價于二叉樹的存儲和遍歷。

這就是普通樹和二叉樹對應的內在邏輯。

普通樹的雙親表示法

（一）、

雙親表示法其實可以用在并查集結構里：

• 順序表存放每個節點對應的parent

• 根節點的parent是其本身（優化的）

• 每個根節點代表一個集合

（二）、

這種結構也可以用于圖的表示，但是太辣雞了，不做描述。

普通樹的孩子表示法

（一）、

類似于哈希表的結構，但是哈希表只是映射邏輯，樹還有繼承邏輯在里面：

• bucket是一維數組

• 籃子后面的存儲結構可以是鏈表

下圖是一個哈希表的圖片，來源于百度，看起來是不是和上面樹的孩子表示法的存儲結構很像：

當然java的紅黑樹還可以在bucket上掛一棵紅黑樹，儲存、增加、刪除、搜索的性能都比鏈表更好。

（二）、

其實圖的鄰接矩陣表示法和樹的孩子表示法結構很相似。

例如，存儲圖 1a) 所示的有向圖，其對應的鄰接表如圖 1b) 所示：

圖 1 鄰接表存儲有向圖

拿頂點 V1 來說，與其相關的鄰接點分別為 V2 和 V3，因此存儲 V1 的鏈表中存儲的是 V2 和 V3 在數組中的位置下標 1 和 2。

從圖 1 中可以看出，存儲各頂點的節點結構分為兩部分，數據域和指針域。數據域用于存儲頂點數據信息，指針域用于鏈接下一個節點，如圖 2 所示：

圖 2 鄰接表節點結構

在實際應用中，除了圖 2 這種節點結構外，對于用鏈接表存儲網（邊或弧存在權）結構，還需要節點存儲權的值，因此需使用圖 3 中的節點結構：

圖 3 鄰接表存儲網結構使用的節點

（三）、

操作系統中文件系統的文件存儲時，使用一張索引表映射不同的文件（順序表），表中存盤塊地址、低階索引表。看起來和哈希表的結構很像。

樹、森林與二叉樹的轉換

樹?二叉樹?森林

1.樹轉換為二叉樹

使用孩子兄弟表示法。結點的左子樹為該結點的第一個左孩子；右子樹為該結點的兄弟結點。

具體步驟:

所有兄弟結點用線連起來

每個結點只保留與第一個左孩子之間的連線，去掉其余連線

調整層次。

2.二叉樹轉換為樹

將某結點的右孩子（右孩子的右孩子、右孩子的右孩子的右孩子……）與該結點的雙親結點連線

將原二叉樹的所有結點與右孩子之間的連線去掉

調整層次

3.森林轉換為二叉樹

先將每一棵普通樹轉化為二叉樹

第一棵樹的根結點作為二叉樹的根節點，從第二棵樹開始，將每棵樹的根節點作為上一課樹的右孩子

調整層次

4.二叉樹轉換為森林

如果二叉樹的根節點有右孩子，則可以轉換為森林，否則不行

將根節點與右孩子分開，右孩子作為第二棵樹；將第二棵樹的根節點與右孩子分開……直到最后一顆樹的根節點沒有右孩子

將分離出的二叉樹變為樹

樹的需求-內存、數據庫、文件

樹，是一種儲存結構。

為什么要有樹？ 為了存儲、為了查詢、為了使用樹二叉的特性進行分類。

內存對應了樹的核心需求：遍歷、查找。內存要進行大量的讀寫操作，而讀操作是最最最重要的。

如果是一顆樹形結構，就必須有比線性結構更優的搜索性能。

因此內存采用紅黑樹進程存儲。

原因如下：

簡單的樹高度不定，因此為了使得高度盡量降低因此有了完全二叉樹，但是完全二叉樹要求太高了，因此有了要求稍微低一點的平衡二叉樹，即高度差維持在正負一以內。但是對AVL樹只進行存儲還好，要進行添加刪除就需要每次進行平衡操作，開銷很大。內存不只用來存儲還用來添刪，因此再降低一些AVL樹的要求，就形成了紅黑樹，紅黑樹能保證平均高度logn，最壞高度2logn，但是其增添性能均高于AVl樹。二叉搜索樹可以建立在AVL樹或紅黑樹的基礎上。

除了內存，數據庫也用到了樹。數據庫由數據庫管理系統、數據庫應用程序、數據庫三部分組成，主要實現的對數據文件的存儲和操作。想要把一個大文件一次載入內存有時是很困難的，如果還用紅黑樹存放文件那一次性可能沒辦法直接載入一棵樹，因此產生了b樹。b樹進一步壓縮了高度，而且可以每次只載入其一個節點。

（在b樹基礎上建立的b+樹更適合數據庫的存儲，mysql就是b+樹）

補充：操作系統、計算機組成原理綜合思考b樹的需求

計算機存儲設備一般分為兩種：

• 內存儲器(main memory)，存取速度快，不能長期保存數據

• 外存儲器(external memory)，磁盤讀取數據靠的是機械運動

• • 尋道時間指的是磁臂移動到指定磁道所需要的時間，主流磁盤一般在5ms以下

• • 旋轉延遲就是我們經常聽說的磁盤轉速

  • 傳輸時間指的是從磁盤讀出或將數據寫入磁盤的時間

一些事實：

• 一次磁盤IO的時間約等于5+4.17 = 9ms

• 一臺500 -MIPS的機器每秒可以執行5億條指令

• 執行一次IO的時間可以執行40萬條指令，數據庫動輒十萬百萬乃至千萬級數據，每次9毫秒的時間，在此期間cpu只能中斷去進行io操作，無法執行指令，這樣會有大量的io開銷。

• 從磁盤中載入數據到內存時，是按照一頁page載入的，一頁可以是4k或8k（局部性原理）。我們讀取一頁內的數據時候，實際上才發生了一次IO。

事實1 ： 不同容量的存儲器，訪問速度差異懸殊。

• 磁盤(ms級別) << 內存(ns級別)， 100000倍

• 若內存訪問需要1s，則一次外存訪問需要一天

• 為了避免1次外存訪問，寧愿訪問內存100次...所以將最常用的數據存儲在最快的存儲器中

事實2 ： 從磁盤中讀 1 B，與內存讀寫 1KB 的時間成本幾乎一樣

從以上數據中可以總結出一個道理，索引查詢的數據主要受限于硬盤的I/O速度，查詢I/O次數越少，速度越快，所以B樹的結構才應需求而生；

B樹的每個節點的元素可以視為一次I/O讀取，樹的高度表示最多的I/O次數，在相同數量的總元素個數下，每個節點的元素個數越多，高度越低，查詢所需的I/O次數越少；假設，一次硬盤一次I/O數據為8K，索引用int(4字節)類型數據建立，理論上一個節點最多可以為2000個元素，2000*2000*2000=8000000000，80億條的數據只需3次I/O（理論值），可想而知，B樹做為索引的查詢效率有多高；

樹的遞歸特性

樹（二叉樹）的定義是遞歸的：

1.遞歸出口：空樹是一棵樹 -> 后面很多問題用遞歸，則出口判斷就是node是否為空

2.遞推式： 每棵樹都有一個根節點，根節點可以有左右子樹，子樹本身也是一棵（二叉）樹

樹的結構是遞歸的：

?class Binarytree{ELETYPE element;Binarytree* left;BInarytree* right;}

遞歸求樹高

左右孩紙也是樹，所以求樹高是遞歸問題

? int Hight(){return Hight(m_root);}/*一個節點的高度 = 1 + 這個節點左右節點的高度中的最大的那一個*/int Hight(Node<T>* node){if (node == NULL) return 0;?return 1 + max(Hight(node->left), Hight(node->right));} ? //** 循環實現----層序遍歷int hight(){return hight(m_root);}?int hight(Node<T>* node){if (node == NULL) return 0;?int hight = 0; // 高度int levelSize = 1; // 每層節點數queue<Node<T>*> que;que.push(node);?while (!que.empty()) {Node<T>* n = que.front();que.pop();levelSize--;?if (n->left != NULL) que.push(n->left);if (n->right != NULL) que.push(n->right);?if (levelSize == 0) {levelSize = que.size();hight++;} // end if} // end while?return hight;}

翻轉二叉樹

翻轉一棵樹，根節點是不需要變的，只需要翻轉左右子樹即可，所以翻轉樹問題的子問題還是翻轉樹，是遞歸的（尾遞歸）。

? // **************翻轉二叉樹*************void VerseTree(){cout << "*****使用遞歸前序遍歷反轉樹******" << endl << endl;VerseTree(m_root);}?// 節點node最后指向的就是交換完后的根節點void VerseTree(Node<T>* node) ?// 遞歸實現{if (node == NULL) return;?Node<T>* n = node->left;node->left = node->right;node->right = n;?VerseTree(node->left);VerseTree(node->right);} ? void VerseTree2(){cout << "*****使用迭代層次遍歷反轉樹******" << endl << endl;if (m_root == NULL) return;?queue<Node<T>*> que;que.push(m_root);?while (!que.empty()) {Node<T>* node = que.front();que.pop();?Node<T>* n = node->left;node->left = node->right;node->right = n;?if (node->left != NULL) que.push(node->left);if (node->right != NULL) que.push(node->right);}?}

前中后序遍歷

遍歷一棵樹先從其根節點開始，根節點的左右又是子樹的根節點，因此遍歷是遞歸的

? // 先序遍歷 -遞歸void preorder2(){preorder(m_root);}?void preorder2(Node<T>* node){if (node == NULL) ?return;?operate(node->Element);preorder(node->left);preorder(node->right);}??//中序遍歷void inorder2(){inorder(m_root);}?void inorder2(Node<T>* node){if (node == NULL) return;?inorder(node->left);operate(node->Element);inorder(node->right);}??//后序遍歷void postorder2(){postorder(m_root);}?void postorder2(Node<T>* node){if (node == NULL) ?return;?postorder(node->left);postorder(node->right);operate(node->Element);}

樹的遍歷-經典前中后層-非遞歸

正在上傳…重新上傳取消

?/*--------------------------------------------非遞歸實現前中后序便利------------------------------------*///先序遍歷void preorder(){if (m_root == NULL) ?return;preorder(m_root);}void preorder(Node<T>* node){stack<Node<T>*> nodeStack;nodeStack.push(node);while (!nodeStack.empty()){Node<T>* tnode = nodeStack.top();nodeStack.pop();if(this->m_op(tnode->Element)) ?return;?if (tnode->right != nullptr) {nodeStack.push(tnode->right);}?if (tnode->left != nullptr) {nodeStack.push(tnode->left);}}}

葉子結點是一個根節點，左右子樹為空；

葉子結點又是另一棵樹A的左子節點；

樹A的右節點也是一棵樹；

訪問完A左、A根、A右后，樹A就訪問完了；

樹A又是另一棵樹B的左子樹；

樹B的右子樹也是一棵樹；

訪問完B左（A樹）、B根、B右后，樹B就訪問完了；

......

當前訪問的根節點其實就是下一步要訪問的樹的左節點，因此不需要考慮左節點了，只需要考慮根節點和右節點。

? //中序遍歷void inorder(){if (m_root == NULL) ?return;inorder(m_root);}?void inorder(Node<T>* node){Node<T>* tnode = node;stack<Node<T>*> nodeStack;?while (true){// 先找到最左邊的葉子節點，并再此過程中入棧各個左節點if (tnode != nullptr){nodeStack.push(tnode);tnode = tnode->left;}else // 上一步已經把左子樹訪問完了，因此下面只需要訪問根節點、右子樹即可{if (nodeStack.empty()) ?return;?// 訪問根節點tnode = nodeStack.top();nodeStack.pop();if (this->m_op(tnode->Element)) ?return;?// 處理完根節點，接著處理右子樹tnode = tnode->right;}}}

? void postorder_reverse(Node<T>* node){vector<Node<T>*> temp;stack<Node<T>*> nodeStack;nodeStack.push(node);while (!nodeStack.empty()){Node<T>* tnode = nodeStack.top();nodeStack.pop();temp.push_back(tnode);?if (tnode->left != nullptr) {nodeStack.push(tnode->left);}?if (tnode->right != nullptr) {nodeStack.push(tnode->right);}??}reverse(temp.begin(), temp.end());?for (Node<T>* i : temp){if (this->m_op(i->Element)) ?return;}}???void postorder(Node<T>* node){Node<T>* tnode = node;Node<T>* prev = nullptr;stack<Node<T>*> nodeStack;nodeStack.push(tnode);?while (!nodeStack.empty()){// 后序遍歷的棧頂元素必定是根節點，所以此時得到的tnode可以看成是子樹的根節點// 得到根節點后再把其右節點和左節點入棧即可tnode = nodeStack.top();?// 入棧完成后：tnode為棧頂節點// 如果棧頂節點是葉子節點 或者 上一次訪問的節點是棧頂節點的子節點// 初次進來時prev可能時null，需要判斷。只有當壓棧全部完成，prev才不會為0if (tnode->IsLeaf() || (prev != nullptr && prev->parent == tnode)){// 對棧頂節點加工if (m_op(tnode->Element)) return;?// 保留棧頂節點，并出棧prev = tnode;nodeStack.pop();}else {if (tnode->right != nullptr) {nodeStack.push(tnode->right);}?if (tnode->left != nullptr) {nodeStack.push(tnode->left);}}}}

遍歷的應用

前序遍歷

• 顯示文件層次結構，因為文件一般存在于磁盤里，是用樹存儲的，所以使用先序遍歷可以打印出文件的層級結構，即根目錄在上面，子目錄在后面。

中序遍歷

• BST+中序遍歷可以實現升序或降序排列

后序遍歷

• 刪除節點時可以使用，因為遍歷到某個節點時此節點的子節點一定一定遍歷(刪除)過了。

層序遍歷

• 求樹高

• 判斷是否為完全二叉樹

• DFS

邏輯上抽象的樹-并查集和二叉堆

這里的樹 可以是抽象的樹形結構，比如UnionFInd這個數據結構，雖然看起來像是一個個的集合，但是在邏輯拓撲上是一個多叉樹形結構，Union和Find操作時是借助等價的樹形結構進行分析，優化時也用樹形結構分析其樹高、樹節點數等參數，但是實際上UnionFind的本質還是一個一維數組。

UnionFind可以用來表示等價類。

定位聚類后元素屬于哪一個聚類。

基本操作時等價為樹進行分析：根節點嫁接

正在上傳…重新上傳取消正在上傳…重新上傳取消

線索二叉樹*

• 線索二叉樹的存在意義：

普通二叉樹要實現遍歷需要用到棧或隊列（不論迭代還是遞歸），在不使用存儲結構的情況下無法實現遍歷操作，因此可以先在能使用棧或隊列的地方構建一顆線索二叉樹，把建好的模型放到另一個不能使用棧和隊列的地方進行遍歷操作。

線索二叉樹可以保留遍歷過程中節點出現的先后次序，這個次序可以用來還原原來需要借助棧或隊列才能實現的遍歷

構建好一顆線索二叉樹后，遍歷的時間復雜度是線性的，優于普通樹的遞歸和迭代

傳統的二叉樹鏈式存儲結構表示的二叉樹中，存在大量的空閑指針。若能利用這些空指針域來存放指向該節點的直接前驅或是直接后繼的指針，則可以進行某些更方便的運算。這些被重新利用起來的空指針就被稱為線索，加上了這些線索的二叉樹就是線索二叉樹。

線索化：對二叉樹以某種遍歷順序進行掃描并為每個節點添加線索的過程稱為二叉樹的線索化。

進行線索化的目的是為了加快查找二叉樹中某節點的前驅和后繼的速度。 那么在有N個節點的二叉樹中需要利用N+1個空指針添加線索。這是因為在N個節點的二叉樹中，每個節點有2個指針，所以一共有2N個指針，除了根節點以外每一個節點都有一個指針從它的父節點指向它，所以一共使用了N-1個指針。所以剩下2N-(N-1)個空指針。

• 左指針： 指向前驅或左節點

• 右指針： 指向后繼或右節點

二叉樹的線索化有三種：前序、中序和后序線索化，見下圖：

霍夫曼樹*

• huffman存在的意義：

誕生的原因就是用來編碼的。編碼可以用來做無損壓縮和譯碼傳輸

huffman Tree是一顆帶權路徑長度最小的樹，權重大的節點高度小（距離根節點近）。

• 基本術語：

路徑：在一棵樹中，一個結點到另一個結點之間的通路，稱為路徑。圖 1 中，從根結點到結點 a 之間的通路就是一條路徑。

路徑長度：在一條路徑中，每經過一個結點，路徑長度都要加 1 。例如在一棵樹中，規定根結點所在層數為1層，那么從根結點到第 i 層結點的路徑長度為 i - 1 。圖 1 中從根結點到結點 c 的路徑長度為 3。

結點的權：給每一個結點賦予一個新的數值，被稱為這個結點的權。例如，圖 1 中結點 a 的權為 7，結點 b 的權為 5。

結點的帶權路徑長度：指的是從根結點到該結點之間的路徑長度與該結點的權的乘積。例如，圖 1 中結點 b 的帶權路徑長度為 2 * 5 = 10 。

樹的帶權路徑長度：樹中所有葉子結點的帶權路徑長度之和。通常記作 “WPL” 。例如圖中所示的這顆樹的帶權路徑長度為：

WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3

• 構建的本質：

huffman Tree是通過貪心方法構建的，每次選擇最小的兩個節點進行合并，合并出來的節點權重為兩子節點之和。因此考慮使用優先隊列。

huffman Tree是靜態構建的，這里只討論靜態霍夫曼樹，當然也有動態霍夫曼樹

代碼：

• 注意優先隊列使用的是最大堆，即比較器使用less，需要重載<號或實現仿函數

• 方法易懂，就是從優先隊列拿兩個節點進行合并。但是內存開銷大，后面有優化再補充吧。

?#pragma once#include<queue>#include<vector>#include<unordered_map>#include<iostream>#include<stack>using namespace std;????template<class V>class HuffmanTree{private:struct HuffmanNode{V val;double weight;HuffmanNode* left;HuffmanNode* right;HuffmanNode* parent;HuffmanNode() {}HuffmanNode(V v,double w, HuffmanNode* l = nullptr, HuffmanNode* r = nullptr, HuffmanNode* p = nullptr){val = v;weight = w;left = l;right = r;parent = p;}?bool isLeft(){return this != nullptr ? (this->parent->left == this) : false;}?bool isRight(){return this != nullptr ? (this->parent->right == this) : false;}?bool haveLeft(){return this != nullptr ? (this->left != nullptr) : false;}?bool haveRight(){return this != nullptr ? (this->right != nullptr) : false;}?bool operator > (HuffmanNode* p){return this->weight > p->weight;}};?struct mycmp {bool operator()(const HuffmanNode* a, const HuffmanNode* b) {return a->weight < ?b->weight;}};/*** 需要把lambda表達式作為優先隊列參數進行初始化* 并且指定priority_queue的模板實參，decltype(cmp)，c++11 declare type，聲明類型* 可以認為是確定函數的類型* bool (const student & a,const student & b)**/priority_queue<HuffmanNode*, vector<HuffmanNode*>, mycmp> pri_que;stack<int> code;int m_size;?public:HuffmanTree(unordered_map<V,double> map){for (auto i : map){pri_que.push(new HuffmanNode(i.first, i.second));}m_size = map.size();?//while (!pri_que.empty())//{// cout << pri_que.top()->val << endl;// pri_que.pop();//}}?int size(){return m_size;}?void StartConstruct(){if (pri_que.size() == 1) return;?while (pri_que.size() > 1){HuffmanNode* top1 = pri_que.top();pri_que.pop();HuffmanNode* top2 = pri_que.top();pri_que.pop();?HuffmanNode* newNode = new HuffmanNode(top1->weight + top2->weight, top1->weight + top2->weight, top1, top2);top1->parent = newNode;top2->parent = newNode;pri_que.push(newNode);}}??HuffmanNode* getNode(V val){HuffmanNode* root = pri_que.top();// 層序遍歷queue<HuffmanNode*> queue;queue.push(root);?while (!queue.empty()){HuffmanNode* node = queue.front();queue.pop();if (node->val == val){cout << "node:" << node->val << endl;return node;}?if (node->haveLeft()){queue.push(node->left);}if (node->haveRight()){queue.push(node->right);}}return NULL;}???void MakeCode(V val){HuffmanNode* node = getNode(val);while (node != pri_que.top()){if (node->parent->left == node){//cout << "左" << endl;code.push(1);}else if (node->parent->right == node){// cout << "右" << endl;code.push(0);}node = node->parent;}}??void PrintCode(V val){MakeCode(val);while (!code.empty()){cout << code.top();code.pop();}cout << endl;}??};

表達式樹

• 表達式樹可以實現并行計算

• 中序遍歷表達式樹得到的就是我們常見的四則運算順序

• 中綴表達式+前、后綴表達式可以唯一確定一顆表達式樹

建樹規則與樹的種類，以及預處理對數據結構性能提高分析

• 樹間元素的規則

• 高度差不超過1 -> AVLTree 搜索效率高（優化高度）

• 節點顏色限制 -> RBTree 搜索+增刪效率高（條件比AVL寬松）

• 節點取值大小分類 -> BST 搜索效率高（二分）、BTree & B+Tree（數據庫存儲）

• 節點取值大小最值靠前規則 -> Binary Heap 找最值復雜的O(1)

• 貪心選擇最小節點合并 —> HuffmanTree 編碼、壓縮（真完全二叉樹），目的是存儲

• *將點集E中的點按照某種規則建樹 -> KDTree

• 使用空指針保存遍歷順序 --> 線索二叉樹

• 不同的預處理后，某一特性功能的性能就會收到影響。

總結

以上是生活随笔為你收集整理的数据结构-树的进阶-串联各科知识的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。