数据结构--二叉树

【前言】关于二叉树知识的考察主要分两部分，第一部分在初赛中体现，一般考察二叉树的节点个数、树高和遍历问题。

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）访问根节点

二叉树遍历总结
二叉树的先序、中序、后序遍历我们已经学会了， 那么给定其中任意两种遍历， 我们能否推出唯一的第三种遍历么?
答案：

给定先序+中序可以推出后序。
后序+中序可以推出先序。
但是先序+后序是无法推出中序的。

要完成这个任务，我们首先要利用以下几个特性：

 特性A：对于先序遍历，第一个肯定是根节点 特性B：对于后序遍历，最后一个肯定是根节点
特性C：利用先序戒后序遍历，确定根节点，在中序遍历中，根节点的两边就可以分出左子树和右子树；
特性D：对左子树和右子树分别做前面3点的分析和拆分；相当于做递归，我们就可以重建出完整的二叉树。
**所以我们可以靠保存先序+中序，戒者后序+中序2个顺序，来保存整个二叉树的结构。**

例1：淘汰赛

例2：二叉树深度

例3：医院设置

例4：遍历问题
【题解】在知道前序后序的情况下有不同的中序遍历，当且仅当这个结点只有一个儿子。
假设有x个结点只有一个儿子，按照乘法原理，每个这样的结点有两种可能：有做儿子或者有右儿子，于是答案是2^x种可能的二叉树。

课后练习：

1、二叉树先序遍历
2、二叉树中序遍历
3、二叉树后序遍历