非递归遍历链式二叉树

非定遍历链式二叉树（先序、中序、后序）

栈只能提供第一次访问和第二次访问的时候输出的选择，就是说只能实现先序遍历和中序遍历，要实现后序遍历，那就要更麻烦一点。

我这里栈的元素的数据类型是BiTree *,即里面存储的是指向BiTree的指针。

#include 
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100
typedef int Status;
typedef char TElemType;
using namespace std;
typedef struct BiTNode {
    TElemType data;//数据域
    BiTNode * lchild,*rchild;//新建两个指针指向左孩子和右孩子
}BiTNode, * BiTree;

//定义一个栈
typedef BiTree SElemType;//定义顺序栈的元素为BiTNode的结点
typedef struct {
	SElemType* base;
	SElemType* top;
	int stacksize;
}SqStack;
//栈的初始化
Status Init(SqStack& S) {
	//分配空间
	//S.base = (SElemType*)malloc(sizeof(SElemType)*MAXSIZE);
	S.base = new SElemType[MAXSIZE];
	if (!S.base) return ERROR;
	S.top = S.base;
	S.stacksize = MAXSIZE;
	return OK;
}
//判断栈是否为空
Status StackEmpty(SqStack S) {
	if (S.top==S.base)
	{
		return TRUE;
	}
	return FALSE;
}
//入栈
Status StackPush(SqStack& S, SElemType e) {
	if (S.top - S.base == S.stacksize) {
		//栈满了
		return ERROR;
	}
	*S.top = e;//*代表取S.top指针的空间进行运算
	S.top++;//即*S.top++=e;
	return OK;
}
//出栈
Status StackPop(SqStack& S, SElemType &e) {
	if (S.top == S.base) {
		return ERROR;
	}
	S.top--;
	e = *S.top;//相当于e=*--S.top
	return OK;
}

//创建二叉树
//先序递归创建二叉树
void create(BiTree& T) {
	T= new BiTNode;
	char ch;
	cin >> ch;
	if (ch == '#') {
		T = NULL;
	}
	else {
		T->data = ch;
		create(T->lchild);
		create(T->rchild);
	}
}

//中序遍历二叉树
void inTraverse(BiTree &T) {
	//创建一个指向当前T的结点p，并且创建一个q指向当前结点的右结点
	BiTNode* p;
	p = T;
	//创建一个栈，并初始化这个栈
	SqStack S;
	Init(S);
	while (p||!StackEmpty(S))
	{
		if (p) {
			StackPush(S,p);//将当前结点入栈
			p = p->lchild;
		}
		else
		{
			BiTNode* q=new BiTNode;
			StackPop(S, q);
			cout << q->data << " ";
			p = q->rchild;
			/*StackPush(S, p);*/
		}
	}

}
//先序遍历二叉树
void preTraverse(BiTree& T) {
	//创建一个指向当前T的结点p，并且创建一个q指向当前结点的右结点
	BiTNode* p;
	p = T;
	//创建一个栈，并初始化这个栈
	SqStack S;
	Init(S);
	while (p || !StackEmpty(S))
	{
		if (p) {
			cout << p->data << " ";
			StackPush(S, p);//将当前结点入栈
			p = p->lchild;
		}
		else
		{
			BiTNode* q = new BiTNode;
			StackPop(S, q);
			
			p = q->rchild;
			/*StackPush(S, p);*/
		}
	}

}
//后序遍历二叉树
//简单来说就是在每次输出结点的时候用一个指针指向上次输出的结点
//如果上次输出的结点是当前d出的结点的右子结点，那么说明这个结点也该输出了，否则还不需要输出，还需要遍历右子树
void afterTraverse(BiTree& T) {
	//创建一个指向当前T的结点p，并且创建一个q指向当前结点的右结点
	BiTNode* p;
	p = T;
	//创建一个栈，并初始化这个栈
	SqStack S;
	Init(S);
	StackPush(S, p);//根结点入栈
	p = p->lchild;
	BiTNode* pre = new BiTNode;
	while (!StackEmpty(S))
	{
		while (p) {
			StackPush(S, p);
			p = p->lchild;
		}
		StackPop(S, p);
		if (p->rchild == NULL) {//右子树是空的，说明该输出了
			cout << p->data << " ";
			pre = p;
			//p = p->rchild;
			p = NULL;
			//continue;
		}
		else if (p->rchild==pre)//右子树是前面一个已经被遍历说，所以应该要输出
		{
			cout << p->data << " ";
			pre = p;
			p = NULL;
			//continue;
		}
		else//说明该结点的右子树还没有被遍历，需要重新入栈
		{
			StackPush(S, p);
			p = p->rchild;
		}
	}

}
int main() {
	BiTree T;
	create(T);
	printf("\n先序遍历结果如下：");
	preTraverse(T);
	printf("\n中序遍历结果如下：");
	inTraverse(T);
	printf("\n后序遍历结果如下：");
	afterTraverse(T);
	return 0;
}

要是对指针不理解的话，debug调试一下就很明显知道是啥类型啦，层次结构就很明显啦：