bitree.h

数据结构中的二叉树的遍历（前序、中序、后序）算法

#include "..\\header\\status.h"

#define TElemType char
typedef enum {L,R} tagtype;

//二叉树节点的定义
typedef struct BiNode {
	TElemType data;
	struct BiNode *lchild, *rchild;		//左右孩子指针

	tagtype tag;						//for PostOrderTraverse

}BiTNode, *BiTree;

#define STACK_INIT_SIZE 100        //存储空间初始分配量
#define STACKINCREMENT  10         //存储空间分配增量

typedef struct {
	BiTNode* base;            //在栈构造之前和销毁后，该指针为NULL
	BiTNode* top;             //栈顶指针
	int stacksize;            //当前已经分配的存储空间，以元素为单位
}SqStack; 

//单链队列
typedef struct QNode {
	BiTNode* data;
	struct QNode* next;
}QNode, *QueuePtr;

typedef struct {
	QueuePtr	front;		//队首指针
	QueuePtr	rear;		//队尾指针
}LinkQueue;

//非递归遍历时用到的栈
Status InitStack(SqStack &S);
Status DestroyStack(SqStack &S);
Status ClearStack(SqStack &S);
Status IsStackEmpty(SqStack S);
int StackLength(SqStack S);
Status GetTop(SqStack& S, BiTNode* e);
BiTNode* GetTop(SqStack& S);
Status Push(SqStack &S,BiTNode* e);
BiTNode* Pop(SqStack& S);
Status Pop(SqStack &S, BiTNode* e);

//层次遍历时用到的队列
bool   IsQueueEmpty(LinkQueue Q);
Status InitQueue(LinkQueue& Q);
Status DestroyQueue(LinkQueue& Q);
Status EnQueue(LinkQueue& Q, BiTNode* e);
Status DeQueue(LinkQueue& Q, BiTNode* e);

//按先序次序输入二叉树中结点的值(一个字符)，空格字符表示空树，
//构造二叉链表表示的二叉树T
Status CreateBiTree(BiTree& T);
Status DestroyBiTree(BiTree& T);

//采用二叉链表存储结构，Visit是对结点操作的应用函数，一旦Visit()失败，则操作失败。
//访问二叉树的节点
Status Visit(TElemType e);

//先序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。
Status PreOrderTraverseR(BiTree T, Status(*Visit)(TElemType e));	//递归
Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e));		//非递归

//中序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。
Status InOrderTraverseR(BiTree T, Status(*Visit)(TElemType e));		//递归
Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e));	//非递归

//后序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。
Status PostOrderTraverseR(BiTree T, Status(*Visit)(TElemType e));	//递归
Status PostOrderTraverse(BiTree T, Status(*Visit)(TElemType e));	//非递归

//层序遍历二叉树，对每个结点调用函数Visit一次且仅一次。
Status LevelOrderTraverse(BiTree T, Status(*Visit)(TElemType e));