二叉树的遍历方式（C语言）

简介：

二叉树的遍历分为前序遍历、中序遍历和后序遍历。其存储结构分为顺序结构（数组）和链式结构。

顺序结构：

利用数组存储二叉树的结点的数据，其结点的父子关系是通过他们的数组的位置来反映的。顺序结构通常对与的是完全二叉树。存储的顺序是从上到下、从左到右。优点：存储空间利用率高、计算简单。缺点：不易实现增加、删除操作。

程序代码：

#include<stdio.h>
int a[101];
int n;
void qian(int a[],int i)
{
	if(i>n)
		return;
	printf("%d ",a[i]);
	qian(a,i*2);
	qian(a,i*2+1);
	
}
void zhong(int a[],int i)
{
	if(i>n)
		return;
	zhong(a,i*2);
	printf("%d ",a[i]);
	zhong(a,i*2+1);
}
void hou(int a[],int i)
{
	if(i>n)
		return;
	hou(a,i*2);
	hou(a,i*2+1);
	printf("%d ",a[i]); 
}
int main()
{
	int i,m,j,k;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		a[i]=i;
	printf("输入的数组为：\n");
	for(i=1;i<=n;i++)
		printf("%d ",a[i]);
	printf("\n输入前序遍历的数组：\n");
	qian(a,1);
	printf("\n输出中序遍历的数组：\n");
	zhong(a,1);
	printf("\n输出后序遍历的数组：\n");
	hou(a,1);
	return 0;
}

链式结构：

链式结构的存储是利用链表，二叉树的指针至少包括三部分：数据域、左指针域和右指针域。它的优点是节省空间但是操作麻烦。

程序代码：

#include<stdio.h>
#include<stdlib.h>
struct node
{
	int date;
	struct node *lift,*right;
};
typedef struct node LNode,*Link;
void creat(Link *head);
void qian(Link head);
void zhong(Link head);
void hou(Link head);
int main()
{
	Link head;
	head=NULL;
	printf("输入二叉树链式：\n");
	creat(&head);
	printf("输出前序遍历：\n");
	qian(head);
	printf("\n输出中序遍历：\n");
	zhong(head);
	printf("\n输出后序遍历：\n");
	hou(head);
	return 0;
}
void creat(Link *head)
{
	int a;
	scanf("%d",&a);
	if(a==0)
		*head=NULL;
	else
	{
		*head=(Link)malloc(sizeof(LNode));
		(*head)->date=a;
		creat(&(*head)->lift);
		creat(&(*head)->right);
	}
	
}
void qian(Link head)
{
	if(head!=NULL)
	{
		printf("%d ",head->date);
		qian(head->lift);
		qian(head->right);
	}	
}
void zhong(Link head)
{
	if(head!=NULL)
	{
		zhong(head->lift);
		printf("%d ",head->date);
		zhong(head->right);
	}
}
void hou(Link head)
{
	if(head!=NULL)
	{
		hou(head->lift);
		hou(head->right);
		printf("%d ",head->date);
	}
}