一、基本概念
1、概念
森林：指m棵不相交的树的集合。
结点的层次：从根到该结点的层数（根为第1层）。结点的最大层次是树的深度（高度）。
终端结点（叶子）：度为0的结点；非终端结点（分支结点）：度不为0的结点。除根结点外，分支结点也称为内部结点。
平衡树：左右子树深度差<=1。
排序树：左小右大。
字典树：由字符串构成的二叉排序树。
判定树：如12个球只称三次分出轻重。
带权树：路径长度带权值。
最优树：Huffman树，带权路径长度最短的树，主要用于压缩编码。
2、树的逻辑结构：一对多
3、树的存储
a.顺序存储：不能唯一复原，没有实用价值。（只有满二叉树和完全二叉树可以唯一复原，实现顺序存储）
b.链式存储：先研究二叉树，再设法将一般的树转化为二叉树。（所有树都能转为唯一对应的二叉树）
二、二叉树
1、定义：每个结点至多只有两棵子树（不存在度大于2的结点），并且有左右之分，不能任意交换次序（有序树）。
例题：具有三个结点的二叉树有几种？普通树呢？5种、2种。
2、性质
（1）第i层至多有2i-1个结点（i>0）；
提问：第i层上至少有 1 个结点。
（2）深度为k的二叉树至多有2k-1个结点（k>0）；
提问：深度为k的二叉树至少有 k 个结点。
一棵深度为k且有2k-1个结点的二叉树为满二叉树；深度为k，有n个结点的二叉树，当且仅当其每个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称之为完全二叉树。
（3）叶子树n0=n2+1；（n2是度为2的结点数）
推倒：n0+n1+n2=2n2+n1+1
对于满二叉树和完全二叉树还具有以下两条性质：
（4）具有n个结点的完全二叉树的深度 [log2n]下取整+1
（5）对完全二叉树，若从上至下，从左至右编号，则编号为i的结点，其左孩子编号必为2i，其右孩子编号必为2i+1；其双亲编号必为i/2（i=1时为根，除外）
3、存储
（1）顺序存储：自上而下、自左而右编号，用一组连续的存储单元存储。
a.只有满二叉树和完全二叉树可以唯一复原，实现顺序存储。且下标值存在性质（5）中的规律。如Array[2]的孩子必为Array[4]和Array[5]（Array[0]不用）。
b.不是完全二叉树的，转为完全二叉树再存储。即将各层空缺处补“空”。但这样浪费空间，插入删除不方便。
（2）链式存储
a.二叉链表：数据域和左、右指针域。链表的头指针指向二叉树的根结点。
易证：含有n个结点的二叉链表中，有2n个指针域，这2n个指针域指向n-1个点（根除外），所以有n+1个空链域。
可以利用这些空链域存储其他有用信息，得到另一种链式存储结构--线索链表。
b.三叉链表：在二叉链表基础上，增加一个指向其双亲结点的指针域。
三、遍历二叉树
1、遍历：每个结点均被访问且仅被访问一次。
2、遍历规则：（1）深度遍历：先序遍历DLR、中序遍历LDR、后序遍历LRD。（2）广度遍历：层次遍历
3、四种遍历算法编程（递归、非递归）。
Struct BinaryTreeNode{ int m_nValue; Node* m_pLeft; Node* m_pRight; }; //先序遍历，非递归 void preorder(Node * root){ if(root==NULL){ return; } stack<Node*> S; S.push(root); while(!S.empty()){ cout<<S.top()->data<<" "; S.pop(); if(S.top()->right!=NULL) S.push(S.top()->right); if(S.top()->left!=NULL) S.push(S.top()->left); } cout<<endl; } //先序遍历，递归 void preorder(Node* root){ if(root!=NULL){ printf("%d",root->data); preorder(root->m_pLeft); preorder(root->m_pRight); } } //中序遍历，递归 void inorder(Node* root){ if(root!=NULL){ inorder(root->m_pLeft); printf("%d",root->data); inorder(root->m_pRight); } } //后序遍历，递归 void postorder(Node* root){ if(root!=NULL){ postorder(root->m_pLeft); postorder(root->m_pRight); printf("%d",root->data); } } //分层遍历，递归 int printNodeAtLevel(Node * root,int level){ if(!root||level<=0){ return 0; } if(level==1){ printf("%d ",root->data); return 1; } return printNodeAtLevel(root->Left,level-1)+ printNodeAtLevel(root->Right,level-1); } void printNodeByLevel(Node * root){ for(int level=1;;level++){ if(! printNodeAtLevel(root,level)){ break; } printf(" "); } }
由上面三种遍历（先、中、后序）递归算法可以看出，如果将printf语句抹去，这三种算法完全相同。时间复杂度O(n)，栈占用的最大辅助空间，即空间复杂度O(n)。深度为k的二叉树遍历需要k+1个辅助单元。
题目：编写递归算法，计算二叉树中叶子结点数目。
int sum=0; void findLeafNum(Node * root){ if(root!=NULL){ if(!root->left&&!root->right){ sum++; } findLeafNum(root->left); findLeafNum(root->right); } }
4、常见题型：已知先序/后序和中序遍历，可唯一恢复二叉树。已知先序和后序遍历恢复二叉树（阿里）。
腾讯：表达式“X=A+B*（C--D）/E”的后缀表示形式可以为（）
A、XAB+CDE/-*= B、XA+BC-DE/*= C、XABCD-*E/+= D、XABCDE+*/=
答：C。根据优先级将X=A+B*（C--D）/E写成二叉树的形式，后序顺利的结果就是后缀表示形式
在A*B*C这样的运算中，两个运算符优先级相同，从左往右依次计算。
四、线索二叉树
含有n个结点的二叉链表中，有2n个指针域，这2n个指针域指向n-1个点（根除外），所以有n+1个空链域。可以利用这些空链域存储其他有用信息，得到另一种链式存储结构--线索链表。
普通二叉树只能找到左右孩子，而线索二叉树利用n+1个空链域存放前驱指针、后继指针。这两个指针分别存放在左右孩子的位置。为区分到底该域是指向孩子还是前驱后继，分别增加两个标识域Tag。（0为正常情况，1为线索情况）这种含有Tag的二叉链表称为线索链表。
线索化：对二叉树以某种次序遍历（先序、中序、后序），过程中修改空指针（将空指针改为前驱或后继），使其变为线索二叉树。
例1：某先序遍历结果如下表所示，请画出对应的二叉树。
例2：给定（如下左图）二叉树，请画出与其对应的中序线索二叉树。
因为中序遍历序列是：55 40 25 60 28 08 33 54。对应线索树应当按此规律连线，即在原二叉树中添加虚线（上右图）。
线索二叉树的中序遍历算法（非递归）（略）。
五、树和森林
1、树的存储
（1）双亲表示法：用一组连续空间来存储树的结点，同时在每个结点中附设一个指示器，指示其双亲结点在链表中的位置。缺点是求结点的孩子时需要遍历整个结构。
（2）孩子表示法：将每个结点的孩子排列起来，形成一个带表头（装父结点）的线性表（n个结点要设立n个链表）；再将n个表头用数组存放起来，这样就形成一个混合结构。
（3）孩子兄弟表示法：用二叉链表来表示树，但链表中的两个指针域含义不同。左指针指向该结点的第一个孩子；右指针指向该结点的下一个兄弟结点。
问：树转二叉树的“连线—抹线—旋转” 如何由计算机自动实现？
答：用“左孩子右兄弟”表示法来存储树即可实现树转二叉树的“连线—抹线—旋转”，对应二叉树的二叉链表。存储的过程就是转换的过程！
2、树和二叉树的转换
（1）树->二叉树（根结点肯定没有右孩子）
step1: 将树中同一结点的兄弟相连;（加线）
step2: 保留结点的最左孩子连线，删除其它孩子连线；（抹线）
step3: 将同一孩子的连线绕左孩子旋转45度角。（旋转）
例如：
（2）二叉树->树
要点：把所有右孩子变为兄弟（例如上图的反向变换）
（3）森林->二叉树
要点：森林直接变兄弟，再转为二叉树（兄弟相连 长兄为父 孩子靠左 头根为根）
例如：
（4）二叉树->森林
要点：把最右边的子树变为森林，其余右子树变为兄弟
例如：
3、树和森林的遍历
（1）树的遍历（没有中序遍历）
•先序遍历（对应二叉树的先序遍历）
先访问根结点，再依次先根遍历每棵子树。
•后序遍历（对应二叉树的中序遍历）
先依次后根遍历每棵子树，再访问根结点。
（2）森林的遍历（没有后序遍历）
六、Huffman赫夫曼树（最优二叉树）
1、概念
路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径
路径长度：路径上的分支数目称做路径长度
树的路径长度：是从树根到每个结点的路径长度之和。完全二叉树就是这种路径长度最短的二叉树
带权结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积
树的带权路径长度：树中所有叶子结点的带权路径长度之和，记作WPL
Huffman树：WPL最小的二叉树
2、在解决某些判定问题时，Huffman树可以得到最佳判定算法。例如：将百分制转换为五级分制的程序。
| 分数 | 0-59 | 60-69 | 70-79 | 80-89 | 90-100 |
| 比例 | 0.05 | 0.15 | 0.40 | 0.30 | 0.10 |
这时，就需要构造Huffman树以提高程序质量，以使得大部分数据（比例大的）经过较少比较次数，使总比较次数最小。构造时以5,15,40,30,10为权构造一棵5个叶子结点的Huffman树（图b）。将判定框中的两次比较分开，得到判定树（图c）。图c优于图a。
3、Huffman算法（用于构造Huffman树）
4、Huffman编码
基本思想：概率大的字符用短码，概率小的用长码。
若要设计长短不等的编码，必须是任意个字符的编码都不是另一个字符的编码的前缀，称为前缀编码。Huffman编码是前缀码。
例如：a,b,c,d共4个字符，出现频度分别是7,5,2,4，用Huffman编码可以使得它们组成的报文在网络中传输最快。
方案：首先构造Huffman树（上图），之后按照“左0右1”对Huffman树的所有分支编号。Huffman编码结果是a=0,b=10,c=110,d=111。WPL=1*7+2*5+3*2+3*4=35，WPL最小说明比特数（bit）最少。
比较：如果使用一般编码方式，则4（22=4）个字符每个是2bit(00，01，10，11)，WPL=2*(7+5+2+4)=36>35。