概念

二叉树中所有结点的度不大于2的树，可以为空，但是只要存在结点，结点的度不能大于2；
二叉树是一种有序树，树的左右子树不能颠倒，颠倒后则是一棵新二叉树，即使只有左或右子树也不能颠倒；

二叉树性质

1、度为0的结点树(即叶子结点数计为n0)和度为2的结点数(计为n2)有一个等式关系：n0 = n2 + 1；
2、非空二叉树第 i 层至多有 2^(i -1) 个结点；
3、高度为 h 的二叉树至多有 (2^h)-1 个结点；

二叉树的存储结构

顺序存储

1、顺序存储即使用数组进行树结构的存储；
2、用数组存储时，为了保持二叉树本身的性质，故需要预留一些位置来存储左或右孩子不存在的结点；
3、因此用数组存储时，数据的长度为 (2^h)-1；
4、故数组存储对空间浪费极大；
5、最大堆与最小堆则是使用使用数据存储的，方便排序，时间复杂度为nlogn；

链式存储

1、链式存储能更充分利用资源，因此树一般使用链式存储；
2、存储结构为：数据域、左指针及右指针；
3、上述结构无法查找结点的父结点，故可加一个指向父结点的指针域；
4、链式存储中 n 个结点指使用了 n -1个指针，故可以利用 n +1 个指针，于是有了线索树；

常见二叉树

满二叉树

1、除最后一层外，每层结点的度都是2的二叉树，即不存在度为1的结点，要么为2要么为0；
2、非叶子结点只在最下面一层有；
3、高度为h的满二叉树结点总数为(2^h)-1;
4、若结点总树为n，则最后一个有孩子的结点编号为n/2(从1编号)；
5、如果根结点从1开始依次编号，则第i个结点的左孩子结点编号为2i，右孩子结点编号为2i+1（用数组存时，由于数组从0编号，故左孩子为2i+1，右孩子为2i+2）；

完全二叉树

1、与同高度满二叉树的结点能一一对应的树即为完全二叉树，它是一种最后一层没有存满的状态；
2、其实这个概念要强调的是，完全二叉树度为1的结点的状态，即度为1的结点只能有左孩子结点；
3、完全二叉树，只有最后两层有叶子结点即度为0的结点；
4、完全二叉树最多只能有一个度为1的结点，可以没有度为1的结点；
5、若结点总树为n，则最后一个父结点编号为n/2(从1编号)；
6、如果根结点从1开始依次编号，则第i个结点的左孩子结点编号为2i，右孩子结点编号为2i+1（用数组存时，由于数组从0编号，故左孩子为2i+1，右孩子为2i+2）；
7、由于 n0 = n2 + 1 ，再设总结点数为n
度为1的结点数n1由完全二叉树性质可知，只能取0或1(即n1=0或n1=1)，则有：
a、当n1=0时，n - 1 = 2n2 + 1n1 + 0n0 得 n = 2n2 + 1(奇数)；
推论可知，总结点数为奇数时，完全二叉树没有度为1的结点；
b、当n1=1时，n -1 = 2n2 + 1n1 + 0n0 得 n = 2n2 + 2(偶数)；
推论可知，总结点数为偶数时，完全二叉树只有一个度为1的结点，且该结点为左孩子结点；
8、有 n 个结点的完全二叉树的高度为[log(n + 1)]或[logn] + 1，对数以2为底；

二叉排序树

1、由名字可以它是一种排序的树，可以方便搜索，故也称为二叉搜索树；
2、其排序顺序为：左子树 < 根 < 右子树；
3、左右子树又各是一棵二叉排序树；

平衡二叉树

1、它是一种特殊二叉排序树，**即它总需要保持左子树与右子树的高度差不超过 1 即只能为 0 或 1 **，由于其特性，所以得名平衡二叉树也叫AVL树；
2、由于要保持平衡故在数据插入时就需要涉及旋转，来保持树的平衡，这个过程代价相对比较高；
3、这里需要理解的是保持平衡的原因，保持平衡就是为了方便查找，因为树的查找和树的高度有关系，而平衡二叉树的特性可以保持树高度尽可能低，故查找就快了；

红黑树

它是一种平衡二叉树的变体，它的左右子树高差有可能大于 1，因此严格来说它不算是平衡二叉树；
红黑树减少了平衡二叉树的平衡性， 因此也就减少了平衡二叉树保持平衡时的代价；
红黑树相对平衡二叉树来说，虽然平衡性略有损失，但是保持平衡的代价小了很多；
总体上红黑树的性能要高于平衡二叉树，故在实际工作中经常使用红黑树；

线索二叉树

基础概率

1、线索二叉树的线索其实就是指针，是用于查找结点的前驱和后继的，包括前驱线索和后继线索；
2、线索二叉树是使用链式存储实现的二叉树；

背景介绍

设树的总结点数为n：
1、链式存储实现的二叉树的结点，每个结点都有两个指针即左指针和右指针即有 2n 个指针；
2、由树那一篇介绍过，一棵树的边数即指针数为 n -1;
3、由上可只一棵结点为 n 的树中有 2n - (n - 1) = n +1 个结点是没被使用的；
4、线索二叉树就是将剩余的 n + 1 个结点利用起来；
5、如果当前结点没有左或右孩子，就可将该指针指向当前结点的前驱结点和后继结点；

性质介绍

1、由于树的遍历分为前序、中序和后序三种，不同的遍历方式其前驱和后继也是不同的；
2、因此线索二叉树也分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种；
3、它解决了在二叉树中查找前驱和后继结点困难的问题，同过它能很方便查找；
4、其利用了二叉树本身闲置的指针来存储，没有添加额外的开销，是一种值得借鉴的思想；

霍夫曼树

概念

1、将N个带权值的结点作为叶子结点，去构造二叉树，在构造的二叉树中带权路径最小的二叉树就被称为霍夫曼树，所以可能有多个；
2、它只要求来带权路径最小，所以可能有多个并不唯一；
3、权值就是在现实有意义的某个数值，比如某个字符出现的频率或者总个数等；
4、带权路径长度是指叶子结点和根结点之间包含边的总数，即从叶子结点到根结点要经历的边数；
5、树的带权路径长度就是将所有叶子结点的带权路径长度的总和，也称为WPL；
6、可以应用于编码或者数据压缩等，称为霍夫曼编码；

构造

1、将给定的 n 个结点作为由 n 个只有根结点构成的森林 F；
2、选择森林 F 中结点值最小的两棵树，将这两棵树的结点值相加作为新结点的结点值；
3、把新结点作为根结点，这两棵树为其左右孩子结点合成一棵新树；
4、将合成的新树加入到 F 中，并且删除 F 中最小的两棵树，这时森林 F 中的树会少一棵；
5、继续重复 2 和 3 两个过程，直至森林 F 中只有一棵树，那么该树就是一棵霍夫曼树

性质

1、最初给定的这 n 这结点最终只会是这颗霍夫曼树的叶子结点；
2、在最初给定的 n 个结点中，结点值越小的结点到树根的路径长度越长；
3、霍夫曼树的总结点个数为 2n - 1；
4、霍夫曼树中没有度为1的结点，要么度为 0，那么度为 2；
5、霍夫曼树的个数并不唯一，但是每棵霍夫曼树对应的带权路径长度肯定想等且最小；