[数据结构与算法]数据结构——二叉树定义以及遍历

一、二叉树的定义

	二叉树是一种每个结点至多有两棵子树（即每个结点的度最大为 2 ）的有序树。

• 1、满二叉树
  满二叉树的特点在于“满”，即每层的结点数都是最大结点数。
  
• 2、完全二叉树
  完全二叉树的结点按「自上向下，自左向右」的顺序不能中断。
  

二、二叉树的遍历

	我们知道树是递归的定义，二叉树是由根结点、左子树、右子树这三部分递归地组合而成的。 所以我们要约定的就是这三部分谁先谁后。
	三种主要的遍历思想为：
	1、前序遍历：根结点 ---> 左子树 ---> 右子树
	2、中序遍历：左子树---> 根结点 ---> 右子树
	3、后序遍历：左子树 ---> 右子树 ---> 根结点
	例如：

	前序遍历：1  2  4  5  7  8  3  6 

	中序遍历：4  2  7  5  8  1  3  6

	后序遍历：4  7  8  5  2  6  3  1

三、程序实现

1、二叉树结构体定义

//二叉树节点信息
struct TreeNode {
     int data;
     struct TreeNode *left;//左子树
     struct TreeNode *right;//右子树
  };
  typedef struct TreeNode* root;

二叉树的创建

#include <stdio.h>
#include <stdlib.h>
//#define num 10
//二叉树创建
TreeNode *CreatTree( int *a,int num )
{
	int i;
	TreeNode  *root[num + 1] = {0};
	for ( i = 0; i < num; i++)
	{
		root[i] = (TreeNode *) malloc(sizeof(TreeNode));
		if ( NULL == root[i])
		{
			printf("malloc error!\n");
			exit(1);
		}
		root[i]->left = NULL;
		root[i]->right = NULL;
		root[i]->data = a[i];
	}
	for ( i = 0; i < num/2; i++)
	{
		root[i]->left = root[ 2 * (i + 1) - 1];
		root[i]->right = root[ 2 * (i + 1) + 1 - 1];
	}
	return root[0];
}

int main()
{
	int num = 10;
	int a[num] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
	TreeNode *root = NULL;
	
	root = CreatTree(a,num);
	
	return 0;
}

2、先序遍历
若二叉树为空，则空操作返回，否则先访问根节点，然后前序遍历左子树，再前序遍历右子树。

//先序遍历——递归
void PreOderTraverse(TreeNode *root)
{
    if(root == NULL)
        return;
    printf("%c",root->data);  //显示结点数据，可以更改为其他对结点操作
    PreOderTraverse(root->left);   //先遍历左子树
    PreOderTraverse(root->right);    //最后遍历右子树 
 } 

3、中序遍历
若树为空树，则空操作返回，否则从根节点开始，中序遍历根节点的左子树，然后访问根节点，最后中序遍历右子树。

/*中序遍历递归算法*/
void InOderTraverse(TreeNode *root)
{
    if(root==NULL)
        return ;
    InOderTraverse(root->left);   //中序遍历左子树
    printf("%c",root->data);   //显示结点数据，可以更改为其他对结点的操作
    InOderTraverse(root->right);  //最后中序遍历右子树 
 } 

4、后序遍历
若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点。

/*后序遍历递归算法*/
void PostOderTraverse(TreeNode *root)
{
    if(root==NULL)
        return;
    PostOderTraverse(root->left);   //先遍历左子树 
    PostsOderTraverse(root->right);  //再遍历右子树 
    printf("%c",root->data);    //显示结点数可以更改为其他对结点数据 
}