現在看一些書，不太愿意在書上面做一些標記，也沒啥特殊的原因。。哈哈。

樹的定義

無環連通圖，極小連通圖，極大無環圖。

度

某個節點，描述它的度，一般默認是出度，分叉的邊的條數。或者說孩子的個數。孩子和后代是不一樣的，注意區分。

長度

路徑長度就是邊數，直觀上也是這樣。應該不難理解。

深度和高度

規定根節點的深度為 0 ，空樹的高度為 -1 .

一個問題

$$depth(v)+height(v)\le height(T)$$
什么時候取等號，v 表示的是任意一個節點， T 表示的是根節點。當 v 所在的子樹的最深的葉節點是全樹最深的葉節點的時候，取到等號。

內部節點

我們發現，一些定義假設不是非常清晰，實際上，自己內心是感覺沒有完全掌握這些知識點的，內部節點是指除了葉節點之外的所有節點，也包括根節點。這里沒有考慮極端情況。極端情況只有一個根節點，根節點是內部節點，也是葉節點。

二叉樹

二叉樹的定義是節點的度不超過 2 ， 也就是說不一定要求嚴格是二叉，一叉也是二叉樹，零叉也是二叉樹。

有序多叉樹可以轉換為二叉樹

也就是說，二叉樹可以很簡潔地刻畫有序多叉樹，類似，我寫一萬字，描述清楚一個知識點，一個大佬兩百字描述清楚一個知識點，功能上面都是一致的。轉換的步驟就是，首先把有序多叉樹的長子保留，假設最左邊的孩子就是長子，然后把其他的邊的斷掉，斷掉邊不是舍棄孩子，舍棄孩子就會損失一些重要信息。然后把長子和親兄弟連接起來。一定是要連接親兄弟。然后對新的二叉樹做適當的旋轉，注意是有序的多叉樹，所以右邊的孩子一般比左邊的孩子更大一些，根據這個條件來進行旋轉，就能得到一個我們肉眼看上去像二叉樹的結構，當然實際上這個就是二叉樹。

二叉樹的高度

$$h+1\le n\le 2^{h+1}?1$$
左側取等號是二叉樹是單鏈的情況。右側取等號是滿二叉樹的情況。單鏈的二叉樹并不一定是左側鏈或者右側鏈，可以是兩者的結合，只要最后是單鏈就好。從你的全世界路過里面不是說，只要最后是你就好，么。

練習

非常奇怪，比如說數學練習題，就只有幾個，一個章節可能一二十個練習題，為什么大家的最后的成績差距非常大呢。難道是因為天賦么，可是就這么點考試題就真的能判斷一個人的天賦嗎。哈哈哈。早幾天看了一篇推文，說是看起來非常扎實穩的人，最后居然沒有上岸。我感覺是我本人，非常慌，于是取關了那個博主。假努力，他才是假努力呢，我是真努力。

最優編碼樹的雙子性

什么是最優編碼樹，什么是雙子性。假設真是自己需要理解的知識點，我感覺一個字都不能復制，可能每個字都需要形成自己的理解，才能把里面的邏輯關系搞清楚。我感覺一個練習題的質量的一個重要評價標準就是能不能綜合很多知識點，或者需要極多的前置知識（前置知識也屬于考試范圍內的，不屬于超綱范圍這種），我把這個部分的標題作為我這篇筆記的標題了，嘿嘿，比較高級。有些希臘字母不會讀，感覺有點影響自己閱讀了。谷歌的搜索貌似用不了。edge 搜出來是 sigma 。我還是習慣用搜索引擎，很多時候，大模型有時候要反應一下，我想要即時反饋。幾秒鐘都不太愿意等他。編碼就是把一些信息轉換為二進制的，非常神奇，一些非常復雜的信息，居然在電腦上能用一串 01 數字表示。

編碼的過程是，首先自底向上構建 PFC 編碼樹，然后構建編碼表，對于文本信息，查詢編碼表進行編碼，類似于以前間諜工作，用一本書里面的字，對應真正要傳遞的信息。合并的次數是樹的數目減去 1 .很容易理解，比如說，兩棵樹合并成一棵樹，只需要合并一次，最后剩下一棵樹就好。

下面是我之前寫的一個非常經典的哈夫曼編碼的題。看了一個大佬的博客，他說能體現一個人的科研素養的就是數學能力和編程能力，感覺有道理，說到底就是邏輯能力。

#include<iostream>
#include<queue> 
#include<vector>using namespace std;int n;
priority_queue<int, vector<int>, greater<int>> heap;int main() {cin >> n;for ( int i = 0; i < n; i++ ) {int x;cin >> x;heap.push( x );}long long ans = 0;while ( heap.size() > 1 ) {int a = heap.top(); heap.pop();int b = heap.top(); heap.pop();ans += a + b;heap.push( a + b );}cout << ans << endl;return 0;
}

然后我們來解答前面的問題，最優編碼樹就是讓平均編碼長度最小的二叉樹。最優二叉編碼樹一定是真二叉樹，真二叉樹的定義是任一節點的度數都是偶數。也就是說要么沒有孩子，有孩子就一定有兩個。二叉樹要求沒有那么嚴格，只要不超過兩個孩子就行了，僅有一個孩子也是可以接受并且是嚴格接受的。這個就是雙子性。就是真二叉樹的定義呀。原來。

雙子性更加優雅的定義：內部節點的左右孩子雙全。（內部節點就是除了葉節點的節點，葉節點沒有孩子，考慮一般的情況，內部節點一定是有孩子的，有孩子就一定是有兩個孩子，一個左孩子，一個右孩子）

最優編碼樹的構造

最優編碼樹的葉節點只能出現在最低兩層。假設不是出現在最低兩層，
可以把左下方的子樹移動到右上方。也不是移動，是交換這兩個部分的節點。平均編碼長度是取決于葉節點的深度的，所以葉節點的深度是越小越好，體現在二叉樹里面是二叉樹越低越好，但是在人類世界里面，貌似正好相反。

完全二叉樹

幾種二叉樹的定義，感覺一直有點繞不清楚。。但是今天可能也繞不清楚，但是可以努力區分一下，我現在不認為有一勞永逸的方法。

二叉樹是分叉不能大于二，小于等于二都是可以接受的。滿二叉樹是每一層都鋪滿，每個有孩子的節點都是有兩個孩子，葉節點只出現在最下面一層。完全二叉樹是葉節點可以出現在最下面兩層。完全二叉樹把最下面一層去掉，就是滿二叉樹，當然滿二叉樹是特殊的完全二叉樹。真二叉樹是任一節點的度是偶數。可能列表描述更加清晰一些。（我自己看自己的筆記發現還是圖和表格會讓自己理解起來更加輕松，大片的文字，哪怕是自己寫的，閱讀起來也是比較費勁的了，哪怕作者非常賣力地闡述和分析這里面的邏輯，這可能就是我看不懂專業書籍的原因，閱讀大段的文字本身就是一件比較困難的事情。所以以后做筆記，我可以盡量用圖片，表格，各種形式來進行。加深自己對于知識點的理解。）

分類	描述
二叉樹	任一節點的度小于等于二
完全二叉樹	除了最后一層，上面的部分是滿二叉樹，最后一層可能是滿的，可能不是滿的，每個節點的度都是偶數，應該不會出現內部節點只有一個孩子的情況。
滿二叉樹	每一層都鋪滿
真二叉樹 proper binary tree	每個節點的度都是偶數

我太喜歡表格了，非常清晰。以后寫筆記多寫一些表格。

考慮實際情況的優化

考慮實際情況，我們對一些知識點，或者一些網站，或者一些書籍，或者一些文字，肯定是有使用頻率的差異的。比如說，考試，考察算法，基礎算法，數據結構，搜索與圖論，數學，動態規劃，貪心，這些板塊的出現頻率一定是不一樣的，就像一本書有它的重點，重點我們要多花時間復習，非重點我們可以少花一些時間。全面發展等于全面平庸。也就是說我們要發揮長板思維，不要當一個六邊形戰士，因為我們的時間和精力是有限的，只能做好少部分事情。所以，不要平均用力，要有重點地用力，重點的部分，可以多用用力，不重點的部分，可以少用力甚至不用力。哈夫曼樹對編碼問題的解決，就是讓出現頻率最高的字母排列在哈夫曼樹的靠近根節點的部分，盡可能讓它的深度比較小，這樣代價就比較小。類似于我們把一些常用的網站收藏在瀏覽器首頁，雖然我擔心別人看到我經常訪問的網站把收藏夾隱藏了，但是我記住了一些常用網站的域名，或者編輯了收藏的備注，搜一下就有了。學習也是，經常用的書放在手邊，盡可能減小我們做這件事情的代價，我們才能更多地做這件事情。假設要去健身房鍛煉，需要走很遠的路，通過很多道安檢，然后要帶很多裝備，要花很長的一段完整的時間，很可能就會勸退很多人。小事很多人可以輕松地堅持，就是這個道理。降低門檻就是減小代價。更快進入狀態是最重要的。一些專業的書籍還是太深入了。看一遍根本理解不了里面的意思。。

二叉樹的遍歷的迭代形式

這塊大佬可能認為比較簡單，但是對我來說，屬于絕對的門檻。需要付出巨大努力都不一定能跨越的門檻。我需要把我的精力都貫注到這個知識點上面。

前序遍歷的迭代版本，需要用到輔助棧存右子樹，棧有先進后出，后進先出的特點，先盡可能地遍歷左子樹，哦這個叫做先序遍歷啊，我還以為是前序遍歷呢。。查了一下，好像是一個意思。先序遍歷的迭代版本的輔助棧，入棧的時候可以對右子樹判空進行優化，判斷確認不是 NULL 之后才允許入棧，NULL 不用入棧，節省了空間，判斷這個操作增加了判斷時間，可能可以減少入棧和出棧的時間。考慮兩個極端情況。

情況	分析
幾乎都有右孩子	增加了判斷的時間
幾乎都沒有右孩子	增加了判斷的時間，節省了空間，節省了入棧出棧的時間
總結	綜合來看，大概率是節省時間和空間的

最后

感覺專業課還有很遠的路要走，心態最重要，然后慢慢學一些知識點吧。