最优编码树的双子性

现在看一些书，不太愿意在书上面做一些标记，也没啥特殊的原因。。哈哈。

树的定义

无环连通图，极小连通图，极大无环图。

度

某个节点，描述它的度，一般默认是出度，分叉的边的条数。或者说孩子的个数。孩子和后代是不一样的，注意区分。

长度

路径长度就是边数，直观上也是这样。应该不难理解。

深度和高度

规定根节点的深度为 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;
}

然后我们来解答前面的问题，最优编码树就是让平均编码长度最小的二叉树。最优二叉编码树一定是真二叉树，真二叉树的定义是任一节点的度数都是偶数。也就是说要么没有孩子，有孩子就一定有两个。二叉树要求没有那么严格，只要不超过两个孩子就行了，仅有一个孩子也是可以接受并且是严格接受的。这个就是双子性。就是真二叉树的定义呀。原来。

双子性更加优雅的定义：内部节点的左右孩子双全。（内部节点就是除了叶节点的节点，叶节点没有孩子，考虑一般的情况，内部节点一定是有孩子的，有孩子就一定是有两个孩子，一个左孩子，一个右孩子）

最优编码树的构造

最优编码树的叶节点只能出现在最低两层。假设不是出现在最低两层，
可以把左下方的子树移动到右上方。也不是移动，是交换这两个部分的节点。平均编码长度是取决于叶节点的深度的，所以叶节点的深度是越小越好，体现在二叉树里面是二叉树越低越好，但是在人类世界里面，貌似正好相反。

完全二叉树

几种二叉树的定义，感觉一直有点绕不清楚。。但是今天可能也绕不清楚，但是可以努力区分一下，我现在不认为有一劳永逸的方法。

二叉树是分叉不能大于二，小于等于二都是可以接受的。满二叉树是每一层都铺满，每个有孩子的节点都是有两个孩子，叶节点只出现在最下面一层。完全二叉树是叶节点可以出现在最下面两层。完全二叉树把最下面一层去掉，就是满二叉树，当然满二叉树是特殊的完全二叉树。真二叉树是任一节点的度是偶数。可能列表描述更加清晰一些。（我自己看自己的笔记发现还是图和表格会让自己理解起来更加轻松，大片的文字，哪怕是自己写的，阅读起来也是比较费劲的了，哪怕作者非常卖力地阐述和分析这里面的逻辑，这可能就是我看不懂专业书籍的原因，阅读大段的文字本身就是一件比较困难的事情。所以以后做笔记，我可以尽量用图片，表格，各种形式来进行。加深自己对于知识点的理解。）

我太喜欢表格了，非常清晰。以后写笔记多写一些表格。

考虑实际情况的优化

考虑实际情况，我们对一些知识点，或者一些网站，或者一些书籍，或者一些文字，肯定是有使用频率的差异的。比如说，考试，考察算法，基础算法，数据结构，搜索与图论，数学，动态规划，贪心，这些板块的出现频率一定是不一样的，就像一本书有它的重点，重点我们要多花时间复习，非重点我们可以少花一些时间。全面发展等于全面平庸。也就是说我们要发挥长板思维，不要当一个六边形战士，因为我们的时间和精力是有限的，只能做好少部分事情。所以，不要平均用力，要有重点地用力，重点的部分，可以多用用力，不重点的部分，可以少用力甚至不用力。哈夫曼树对编码问题的解决，就是让出现频率最高的字母排列在哈夫曼树的靠近根节点的部分，尽可能让它的深度比较小，这样代价就比较小。类似于我们把一些常用的网站收藏在浏览器首页，虽然我担心别人看到我经常访问的网站把收藏夹隐藏了，但是我记住了一些常用网站的域名，或者编辑了收藏的备注，搜一下就有了。学习也是，经常用的书放在手边，尽可能减小我们做这件事情的代价，我们才能更多地做这件事情。假设要去健身房锻炼，需要走很远的路，通过很多道安检，然后要带很多装备，要花很长的一段完整的时间，很可能就会劝退很多人。小事很多人可以轻松地坚持，就是这个道理。降低门槛就是减小代价。更快进入状态是最重要的。一些专业的书籍还是太深入了。看一遍根本理解不了里面的意思。。

二叉树的遍历的迭代形式

这块大佬可能认为比较简单，但是对我来说，属于绝对的门槛。需要付出巨大努力都不一定能跨越的门槛。我需要把我的精力都贯注到这个知识点上面。

前序遍历的迭代版本，需要用到辅助栈存右子树，栈有先进后出，后进先出的特点，先尽可能地遍历左子树，哦这个叫做先序遍历啊，我还以为是前序遍历呢。。查了一下，好像是一个意思。先序遍历的迭代版本的辅助栈，入栈的时候可以对右子树判空进行优化，判断确认不是 NULL 之后才允许入栈，NULL 不用入栈，节省了空间，判断这个操作增加了判断时间，可能可以减少入栈和出栈的时间。考虑两个极端情况。

最后

感觉专业课还有很远的路要走，心态最重要，然后慢慢学一些知识点吧。