【前言】关于二叉树知识的考察主要分两部分，第一部分在初赛中体现，一般考察二叉树的节点个数、树高和遍历问题。
1、二叉树定义
在计算机科学中，二叉树是每个结点最多有两个子树的树结构。
通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。
2、二叉树的存储
（1）可以继续沿用存储树的方法，来存储二叉树。
struct node{
int value;
vector<int> childs; //用来记彔所有子节点的编号
}nodes[10000];
int root; //root为根节点
（2）也可以利用二叉树的特性，用左右子树的方式，来存储二叉树。
? 用结构体来表示二叉树的节点， 每个节点存储了当前节点的值， 以及左子树和右子树的编号。
struct node{
int value;
int left;
int right;
}nodes[10000];
int root; //root为根节点
3、二叉树的遍历
遍历二叉树的方法可以沿用遍历树的方法——递归。
DS(当前节点u){
DS(u.left);
DS(u.right);
}
先序遍历
遍历顺序规则为：根左右
遍历方法：
（1）访问根节点
（2）采用先序递归遍历左子树
（3）采用先序递归遍历右子树
中序遍历
遍历顺序规则为：左根右
遍历方法：
（1）采用中序遍历左子树
（2）访问根节点
（3）采用中序遍历右子树
后序遍历
遍历顺序规则为：左右根
遍历方法：
（1）采用后序递归遍历左子树
（2）采用后序递归遍历右子树
（3）访问根节点
例1：淘汰赛
例2：二叉树深度
例3：普通二叉树
例4：求先序排列