树和二叉树的定义、遍历
一、树的定义
顾名思义，树是一种把数据组织成“倒置的树”状的结构。从上往下看，有一个总的起源，称为树的根（如上图的A点）；
每个数据元素可能有多个后继，如上图A有三个后继，B有两个后继，K有0个后继。每个后继称为对应节点的儿子节点。如A有三个儿子B、C、D；注意，不特别声明，儿子节点都是没有顺序之分的。下面两棵树本质是一样的树。
儿子节点没有顺序之分的称为无序树，有顺序之分的称为有序树。
对应的，A称为B、C、D的父亲，每条边连接的是一对父子关系。AB是一对父子节点。
没有后继的节点称为叶子节点；
根和叶子节点之外的称为分支节点；
具有相同父亲的节点互称为兄弟节点。
树的定义是递归的，某个子节点往下的所有节点称为他的子树，例如以A为根的树（A往下的所有节点）有三棵子树，分别是以B为根的子树、以C为根的子树，以D为根的子树。
子树上的所有节点都称为他的子孙节点。例如E、F、K、L都称为B得到子孙节点。
某节点往上直到根为止都称为他的祖先节点。例如A、D、H都是H的祖先节点。
两个节点的共有的祖先称为公共祖先。例如B、A是K和F的公共祖先，其中B点距离K和F最近，把B点称为他们的最近公共祖先。
两个节点的路径：一个节点向上走到最近公共祖先，再走到另外一个节点，沿途经过的点和边称为二者的路径。树中任意两点之间都有唯一的一条路径。
树的度：每个节点的儿子的个数称为节点的度，最大的节点的度称为树的度。
树的深度：树中节点是分层的，根位于第一层，节点所处的层数称为该节点的深度，节点的最大深度称为树的深度。
树中节点每个节点不是平等的。树中有根，有叶子，有父亲，有儿子。如果打破这种层次关系，认为每个节点平等的，把他称为树图。
树图不是树，所有节点都是平等，没有根，也没有叶子节点。树图中一条边连接的两个点互称为邻接点。每个节点的邻接点个数称为该点的度，所以树中节点的度一般比树图中点的度小1（根节点除外）。
树图的性质：
1）n个点被n-1条边联通起来。
2）任意两点之间都有唯一的一条路径。
3）把任意一个点当做根开始划分层次都得到一棵树，所以树图和树在处理问题时有时候被认为是等同的。
二、树的表示
1、父亲表示法（并查集）
2、树形表示法（向量实现、邻接表实现）
树的向量实现：
vector <int> tree[101];
3、长子兄弟法（二叉树概念）、树转二叉树
树转二叉树核心代码：
for(int i=1;i<n;i++)
{
int a,b;
cin>>a>>b;//a是b的父亲
if(z[a]==0)
{
z[a]=b; tree[a].l=b;
}
else
{
tree[z[a]].r=b; z[a]=b;
}
}
三、树的遍历（题号：020000）
1、先根遍历
void dfs1(int num)
{
cout << num << endl;
for(int i = 0; i < tree[num].size(); i ++) //如果num是叶子节点，本循环不执行
dfs1(tree[num][i]);
}
2、后根遍历
3、长子兄弟法（二叉树）的遍历（题号0200002）
1）、二叉树的表示：
struct node{ int l,r; };
node tree[100005];
2）、前序遍历（遍历结果与先根遍历相同）
void xian(int x)
{
cout << x << endl;
if(tree[x].l) xian(tree[x].l); //如果存在左儿子，递归处理左边
if(tree[x].r) xian(tree[x].r);
}
3）、中序遍历（遍历结果与树的后根遍历相同）
4）、后序遍历
5）、中序与前序推后序（题号：020016）
代码：
string fr, md; //fr是前序字符串，md是中序字符串
void go(int ll, int lr, int ml, int mr)
{
int pos = md.find(fr[ll]); //在中序中找根的下标位置
if (pos > ml) go(ll + 1, ll + pos - ml, ml, pos - 1);
if (pos < mr) go(ll + pos - ml + 1, lr, pos + 1, mr);
cout << fr[ll];
}