二叉树分类
完全二叉树
<font color="#c41230">胜者树败者树是完全二叉树</font>
二叉排序树
二叉排序树不一定就是平衡二叉树
二叉排序树的中序遍历是有序的
平衡二叉树
ll型和rr型lr型和rl型
找到从下到上第一个不平衡的树
这课树上下二个节点的左右位置如果分别为左右则为lr型，以此类推
平衡因子是左子树的高度减去右子树的高度，<font color="#c41230">不可颠倒</font>
平衡调整规则
ll型rr型
左旋将上去的节点断掉右子节点连接它的节点成为新的右节点，并将断掉的节点放入合适的位置
右旋将上去的节点断掉左子节点连接它的节点成为新的左节点，并将断掉的节点放入合适的位置
lr型和rl型
先旋转下面的节点使的整个编程rr型的或者是ll型的
根据ll型和rr型由上之下找到第一个不平衡的节点rr或者ll旋转
n个节点有多少种二叉树的形态卡特兰公式
c2n，n/(n+1)
树与二叉树树的转换
树转二叉树
按照左孩子和右兄弟的规则存放
一颗树因此生成二叉树的根节点是没有右孩子的否则这个就不是树而是森林
森林转二叉树
按照左孩子右兄弟的规则
森林可以看做是多个树，多个树生成的二叉树的根节点是有右孩子的，否则就是一个数树
哈夫曼树
常见的哈夫曼树是二阶的
k叉树的的哈夫曼树中只有度为k的节点和度为0的节点
k叉树的哈夫曼树的满足公式
向上取整（(n-1)/(k-1)）=m
其中n为叶子节点个数m为非叶子节点的个数
构建k叉树的叶子节点不能构建满足树的度只有k和0时增加权值为0的节点（类似于最佳归并树增加的虚段）
哈夫曼编码和前缀编码的不同在于，前缀编码只要求前缀不重复，哈夫曼编码还要求最短比如00,11可以作为前缀码，但是不能作为哈夫曼编码
<font color="#c41230">树和森林赫尔和二叉树的转换</font>
树和二叉树
<font color="#c41230">树的后根遍历序列与这棵树对应二叉树（孩子兄弟表示法）的中序遍历序列相同</font>
<font color="#c41230">树的先根遍历序列与这棵树对应二叉树</font>（孩子兄弟表示法）<font color="#c41230">的先序遍历序列相同</font>
森林和二叉树
森林的先序遍历和二叉树（孩子兄弟表表示法）的先遍历相同
森林的<font color="#c41230">中序</font>遍历 和二叉树（孩子兄弟表示法）的中序遍历相同
区别
树不存在中序遍历
<font color="#c41230">森林不存在后序遍历</font>
