【算法导论】二叉树的深度优先遍历

二叉树的遍历可以分为深度优先遍历和广度优先遍历。本篇介绍深度优先遍历，下一篇介绍广度优先遍历。

​ 根据二叉树的递归定义可知，二叉树是由根结点(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;
}