[数据结构]——二叉树(二叉树的分类和二叉树的遍历)

一、二叉树的分类

1、满二叉树

一棵深度为h的树，最后一层无任何子结点，其余每一层上的所有结点都有两个子结点的二叉树。

2、完全二叉树

一棵深度为h的树，前h-1层为满二叉树，第h层的结点从左到右是连续的。

上图为一颗三层的平衡二叉树，前两层为满二叉树，最后一层从左到右的结点是连续的。

下面我们再举一个完全二叉树的反例：

3、平衡二叉树

一棵深度为h的二叉树，任意节点的子树的高度差都小于等于1。

再举一个平衡二叉树的反例：

二、二叉树的四种遍历

先根遍历，中根遍历，后根遍历统称为深度遍历；层序遍历成为广度遍历。

1、先根遍历

先根遍历又称先序遍历，在遍历二叉树时的顺序为根左右。顾名思义，就是先处理根结点，根结点处理完毕，在紧接着处理当前根的左右子树。
先根遍历演示：

void PrevOrder(Tree *root)
{
	if(root==NULL)
	return ;
	printf("%c ",root->val);
	PrevOrder(root->left);
	PrevOrder(root->right);
}
1
2
3
4
5
6
7
8

2、中根遍历

中根遍历又名中序遍历，顺序为左根右。
中根遍历顺序演示：

void InOrder(Tree *root)
{
	if(root==NULL)
	return ;
	InOrder(root->left);
	printf("%c ",root->val);
    InOrder(root->right);
}
1
2
3
4
5
6
7
8

3、后根遍历

后根遍历又称后序遍历，遍历顺序为左右根，先处理左子树，左子树处理完之后处理右子树，左右子树均处理完毕后再处理根结点。
后根遍历顺序演示：

void PostOrder(Tree *root)
{
	if(root==NULL)
	return ;
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%c ",root->val);
}
1
2
3
4
5
6
7
8

4、层序遍历

层序遍历顺序：从上到下，从左到右，依次遍历。层次遍历又称为广度遍历。