数据结构--二叉树

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

1、二叉树定义

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。
通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。

2、二叉树的存储

（1）可以继续沿用存储树的方法，来存储二叉树。

struct node{
int value;
vector<int> childs; //用来记彔所有子节点的编号
}nodes[10000];
int root; //root为根节点
1
2
3
4
5

（2）也可以利用二叉树的特性，用左右子树的方式，来存储二叉树。
 用结构体来表示二叉树的节点， 每个节点存储了当前节点的值， 以及左子树和右子树的编号。

struct node{
int value;
int left;
int right;
}nodes[10000];
int root; //root为根节点
1
2
3
4
5
6

3、二叉树的遍历

遍历二叉树的方法可以沿用遍历树的方法——递归。

DS(当前节点u){
DS(u.left);
DS(u.right);
}
1
2
3
4

先序遍历
遍历顺序规则为：根左右
遍历方法：
（1）访问根节点
（2）采用先序递归遍历左子树
（3）采用先序递归遍历右子树

中序遍历
遍历顺序规则为：左根右
遍历方法：
（1）采用中序遍历左子树
（2）访问根节点
（3）采用中序遍历右子树

后序遍历
遍历顺序规则为：左右根
遍历方法：
（1）采用后序递归遍历左子树
（2）采用后序递归遍历右子树
（3）访问根节点

例1：淘汰赛

例2：二叉树深度

例3：普通二叉树

例4：求先序排列

课后练习：

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