每个宝宝的头上都只有一根天线
树的高度：4(默认从1开始算)
D节点的度：3
这棵树的度：3
3棵树组成一个森林
相互转换是重点
树的度：最大的那个节点的度为3
m叉树：每个节点最多有m个孩子 0 1 2 3 ...m
比如二叉树：
完全二叉树：只有叶子节点的右边能缺少，其余和满二叉树一模一样
最多只有一个度为1的节点
4也重要
你想插入68其实很简单，只要从根开始对比关键字，大了就往右走，小了就往左走
希望你长胖而不是长高，这样对比关键词的次数就会减少，别走那么深吗，受不了啊
任何一个节点的左右子树的高度之差不超过1
顺序存储只适合存储完全二叉树
左孩子2i 右孩子2i+1
i的父节点：i/2向下取整
i所在层次：[log2n] +1也是向下取整
普通二叉树
判断左孩子只能通过isempty字段
也都要按照满二叉树的标准来分配存储空间
因此引出了二叉树的链式存储：
一共有n+1个空链域，可用于构造线索二叉树
这里重点解释一下为什么是n+1个空炼狱：在一棵二叉树当中，除了根节点之外，每个天线宝宝头上都只有一根天线(每个天线消耗一个指针)，一共使用了n-1个指针，所以还剩2n-(n-1)=n+1个空炼狱
二叉树的链式存储
大多情况其实是使用的链式存储，插入根节点的时候只要初始化根即可，后面加入新的节点就再malloc即可
子节点好找，但是父节点镇TM难找啊！！！
方便找父节点：三叉链表
多练几遍呗
代码实现二叉树的先序中序后序遍历
visit访问的代码放在前面就是先序遍历，放到中间就是中序遍历，放到后面就是后序遍历
空间复杂度：O(h) 与高度有关
先序第一次碰到的就是喽，其余的使用前面的方法吧
求树的高度
分别递归遍历左右子树的高度取其最大值为树高
每访问一个节点就把它的左右孩子依次入队，同时根节点出队
使用链队列 代码实现：
最终结果：注意验证！
首先由先序/后续/层次遍历确定根节点的位置，然后根据中序遍历序列确定左右
结果和上面的一样的嘿嘿
普通二叉树的缺陷：只能从根开始遍历，我从第二个元素开始都不刑😂😂
找到中序遍历序列的前驱和后继节点讲实话蛮麻烦的
以下是访问前驱后继的步骤：在visit当中添加操作，一般要从根节点来从头进行中序遍历等等
中序线索二叉树：
术语：二叉链表
建立线索二叉树的目的就是为了方便地找它的前驱和后继：
最左下角的这个节点就是p的后继节点
只有中序线索二叉树才能同时找到前驱和后继
普通的树应该设计什么样的数据结构来存储它呢？
使用二叉链表来存储树可以方便地进行二叉树和树之间的转换
只不过它的指针是*firstchild和*nextsibling，即左孩子是第一个孩子，右孩子是兄弟
树和二叉树的相互转换：
森林和二叉树的相互转换
哈夫曼树
方法二：
思考：有没有更好的编码方案呢？
哈夫曼编码可以用于数据的压缩
我一路向北，判断是不是同一个爹地
并查集就两个操作一个是查一个是并
使用双亲表示法来实现并查集那是相当滴容易啊，只要修改指向就🆗辽
使用一个数组就可以表示他们之间的集合关系
集合初始化代码：
并和查的代码实现：
注意：这里的x指的是下标
合并的时候把小树合并到大树上面，就不会增加树的高度h了
使用根节点的绝对值来表示树的高度(-2 -3 -5 -7 -8这样子)
最终结果：
