二叉树是一棵节点都不能有多于两个儿子的树。
这一章，主要学习二叉树的种类和应用。
一.实现
typedef struct TreeNode *PrtToNode;
typedef struct PrtToNode Tree;
struct TreeNode
{
ElementType Element;
SearchTree Left;
SearchTree Right;
};
二.特点
- 每个结点最多有两棵子树
- 二叉树是有次序的，其次序不能随意颠倒
二叉树
三.二叉树的基本形态
二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：
具有3个结点的树和具有3个结点的二叉树的形态
四.特殊的二叉树
1.斜树
所有结点都只有左子树的二叉树称为左斜树（Left Oblique Tree）；所有结点都只有右子树的二叉树称为右斜树（Right Oblique Tree）；左斜树和右斜树统称为斜树（Oblique Tree）。
在斜树中，每一层只有一个结点，所以斜树的结点个数与其深度相同。
2.满二叉树
在一棵二叉树中，所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。
其特点是：
- 叶子结点只能出现在最下一层。
- 只有度为0和度为2的结点。
3.完全二叉树
对一棵具有n个结点的二叉树按层序编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同，这棵树就是完全二叉树。
4.线索二叉树
a.线索链表
为什么要用线索？
- 二叉树的存储结构中没有反映出某结点的直接前驱结点与直接后继结点是什么。
- 二叉树的二叉链表存储结构中的那些空指针域可利用。
线索：将二叉链表中的空指针域指向前驱结点和后继结点的指针被称为线索；
线索化：使二叉链表中结点的空链域存放其前驱或后继信息的过程称为线索化；
线索二叉树：加上线索的二叉树称为线索二叉树。
b.线索二叉树
二叉树的遍历方式有4种，故有4中意义下的前驱和后继，相应的有4种线索二叉树：
（1）前序线索二叉树
前序序列为：ABCD
（2）中序线索二叉树
进入详细资料
（3）后序线索二叉树
后序序列为：BDCA
（4）层序线索二叉树（略）
5. 哈弗曼树
进入详细资料
6.查找二叉树
7.AVL
8.伸展树
9.B-树
10.……
五.二叉树的遍历
正在编写……
六.表达式树
1.下图表示一个表达式树。
(a-b)/[c*(d+e)]*f
表达式树的树叶是操作数(operand),比如常数和变量，其他节点为操作符(operator)。
2.表达式的表示
中缀表达式： (a-b)/[c*(d+e)]*f
后缀表达式：比如abc*+de*f+g*+
前缀记法：很少用的一种记法
3.构造一棵表达式树
我们看一个例子：ab+cde+**
前两个符号是操作数，因此我们创建两棵单节点树并将指向他们的指针压入栈中
接着，“+”被读入，因此指向这两棵树的指针被弹出，一棵新的树形成，而指向该树的指针被压入栈中。
然后，c、d和e被读入，在每个单节点树创建后，指向对应的树的指针被压入栈中。
接下来读入“+”号，因此两棵树合并。
继续进行读入“*”号，因此，我们弹出两个数指针并形成一个新的树，“*”号是它的根。
最后，读入最后一个符号，两棵树合并,而指向最后的树的指针留在栈中。
