二叉树的深度优先遍历
二叉树的遍历可以分为深度优先遍历和广度优先遍历。本篇介绍深度优先遍历，下一篇介绍广度优先遍历。
根据二叉树的递归定义可知，二叉树是由根结点(D)、左子树(L)和右子树(R)三个基本部分组成。只要能依次遍历这三个基本部分，便可遍历整个二叉树。这三个部分的排列组合为3！=6种，若限定按照先左后右进行遍历，则只有三种遍历方式：DLR(先序)、LDR(中序)、LRD(后序)。
具体实现如下：
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define maxsize 10
typedef int datatype;
typedef struct node
{
datatype data;
struct node *lchild,*rchild;
} bitree;//二叉树的节点结构
bitree* CreatBitree(int* arrayA,int n);//创建二叉树（以顺序存储方式）
void preorder(bitree *p);//先序遍历算法
void midorder(bitree *p);//中序遍历算法
void postorder(bitree *p);//后序遍历算法
void main()
{
int arrayA[9]={0,1,2,3,4,5,6,7,8};//第一个节点没有用于存储数据，是为了方便计算
int n=sizeof(arrayA)/sizeof(int);
bitree *head=NULL;//初始化指向链表的头指针
head=CreatBitree(arrayA,n);//建立链表
printf("前序遍历：");
preorder(head);
printf("\n中序遍历：");
midorder(head);
printf("\n后序遍历：");
postorder(head);
printf("\n");
}
bitree* CreatBitree(int* arrayA,int n)//顺序存储 建立二叉树
{
bitree *root;
bitree *queue[maxsize];//队列用于保存已输入节点的地址
bitree *p;
int front,rear;
front=1;rear=0;//指向队列的头尾
root=NULL;
for(int i=1;i<n;i++)
{
p=(bitree*)malloc(sizeof(bitree));//创立节点并赋值
p->data=arrayA[i];
p->lchild=NULL;
p->rchild=NULL;
rear++;
queue[rear]=p;
if(rear==1)//判断是否为输入的第一个节点
root=p;
else
{
if(i%2==0)//新节点为左孩子
queue[front]->lchild=p;
else//新节点为右孩子
{
queue[front]->rchild=p;
front=front+1;
}
}
}
return root;
}
void preorder(bitree *p)//前序遍历
{
if(p!=NULL)
{
printf("%d ",p->data);
preorder(p->lchild);
preorder(p->rchild);
}
return;
}
void midorder(bitree *p)//中序遍历
{
if(p!=NULL)
{
midorder(p->lchild);
printf("%d ",p->data);
midorder(p->rchild);
}
return;
}
void postorder(bitree *p)//后序遍历
{
if(p!=NULL)
{
postorder(p->lchild);
postorder(p->rchild);
printf("%d ",p->data);
}
return;
}注：如果程序出错，请点击如下链接：
解释说明
