C语言实现数据结构-----树的遍历

树的先序，中序，后序，递归遍历，中序非递归遍历

树的遍历

• 先序
  （先根再左再右）
  -中序
  （先左再根再右）
  -后序
  （先左再右再根）
  
  代码实现：

```c
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
#define STACK_INIT_SIZE 10//储存空间初始量 
#define STACKINCREMENT 2
#define OK 1
#define ERROR 0
#define MAX_TREE_SIZE 100

typedef char TElemType;
typedef int Status;
typedef TElemType SqBiTree[MAX_TREE_SIZE];

typedef struct BiTNode {
	TElemType data;
	struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;

typedef BiTree SElemType;
struct SqStack {
	SElemType *base;// zhandi
	SElemType *top;//zhanding
	int stacksize;//已分配的储存空间
};
Status InitStack(SqStack &S) {
	//构造一个空栈
	if(!(S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType))))exit(OVERFLOW);
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
	return OK;

}
Status StackEmpty(SqStack S) {
	//若栈为空则TRUE
	if(S.top==S.base)return TRUE;
	else return FALSE;

}
Status Push(SqStack &S,SElemType e) {
	//插入元素e为新的栈顶元素
	if(S.top-S.base>=S.stacksize) {
		//栈满，加空间
		S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
		if(!S.base)exit(OVERFLOW);//储存分配失败
		S.top=S.base+S.stacksize;
		S.stacksize+=STACKINCREMENT;
	}
	*(S.top)++=e;
	return OK;
}

Status Pop(SqStack &S,SElemType &e) {
	//若栈不空，则删除s的栈顶元素，用e返回其值和OK
	if(S.top==S.base) return ERROR;
	e=*--S.top;
	return OK;
}
//abc##de#g##f###
//Status InitBiTree(BiTree &T) {//节点初始化
//	T = (BiTNode*)malloc(sizeof(BiTNode));//malloc()的返回值可以强制类型转换
//	T -> lchild = NULL;
//	T -> rchild = NULL;
//	printf("请以先序的方式键入二叉树节点信息。\n");
//}

Status CreatBiTree(BiTree &T) {
	TElemType ch;
	scanf("%c",&ch);
	if('#'==ch) {
		T=NULL;
	} else {
		if(!(T=(BiTree)malloc(sizeof(BiTNode))))exit(OVERFLOW);
		T->data=ch;
		CreatBiTree(T->lchild);
		CreatBiTree(T->rchild);
	}
	return OK;

}
Status PreOrderTraverse(BiTree T,Status(* Visit)(TElemType e)) {
//采用二叉链表存储结构，Visit是对数据元素操作的应用函数
	if(T) {
		if(Visit(T->data))
			if(PreOrderTraverse(T->lchild,Visit))
				if(PreOrderTraverse(T->rchild,Visit))
					return OK;
		return ERROR;
	} else {
		return OK;
	}
}//递归先序

Status InOrderTraverse(BiTree T,Status(* Visit)(TElemType e)) {
//采用二叉链表存储结构，Visit是对数据元素操作的应用函数
	if(T) {

		if(InOrderTraverse(T->lchild,Visit))
			if(Visit(T->data))
				if(InOrderTraverse(T->rchild,Visit))
					return OK;
		return ERROR;
	} else {
		return OK;
	}
}//递归中序

Status PosOrderTraverse(BiTree T,Status(* Visit)(TElemType e)) {
//采用二叉链表存储结构，Visit是对数据元素操作的应用函数

	if(T) {
		if(PosOrderTraverse(T->lchild,Visit))
			if(PosOrderTraverse(T->rchild,Visit))

				if(Visit(T->data))
					return OK;
		return ERROR;
	} else {
		return OK;
	}
}//递归后序

Status InOrderTraverse2(BiTree T,Status(* Visit)(TElemType e)) {
	SqStack S;
	InitStack(S);
	BiTree p=T;
	while(p||!StackEmpty(S)) {
		if(p) {
			Push(S,p);
			p=p->lchild;
		} else {
			Pop(S,p);
			if(!Visit(p->data))
				return ERROR;
			p=p->rchild;
		}
	}
	return OK;
}//中序非递归

Status PrintElement(TElemType e) {
	printf("%c",e);
	return OK;
}
void Test(BiTree &T) {
	printf("先序键入二叉树结点信息，（# 表示空）:");
	CreatBiTree(T);
	printf("\n先序递归实现：");
	PreOrderTraverse(T,PrintElement);
	printf("\n中序递归实现：");
	InOrderTraverse(T,PrintElement);
	printf("\n后序递归实现：");
	PosOrderTraverse(T,PrintElement);
	printf("\n中序非递归实现：");
	InOrderTraverse2(T,PrintElement);
}
int main() {
	BiTree T;
	Test(T);
	getchar();

}

结果：