二叉树--借助栈的非递归版本实现

前面实现了二叉树，和栈，现在将二者结合，实现二叉树的非递归版本遍历算法

在实现的过程中，主要是 “*，&，->，.” 这几个的区别以及含义：

* ：间接访问，操作符访问其操作数所表示的地址
& ：取地址，操作符产生变量的地址，它是一个指针常量
-> ： 访问结构指针成员，对应于&
. ：访问结构成员，对应于*

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef struct BinNode{
	char data;
	struct BinNode *lchild,*rchild;
}BinNode,*BinTree;


typedef struct SqStack{
	BinTree  *base;
	BinTree *top;
	int stacksize;
}SqStack;

int InitStack(SqStack &S);
int DestroyStack(SqStack &S);
int ClearStack(SqStack &S);
int StackEmpty(SqStack &S);
int StackLength(SqStack S);
int GetTop (SqStack &S,BinTree &e) ;
int Push(SqStack &S,BinTree &e);
int Pop(SqStack &S,BinTree &e);
int StackTraverse(SqStack S);

//'#'表示根节点
void createBinTree(BinTree &T){
	char ch;
	scanf("%c",&ch);
	if(ch == '#'){
		T = NULL;
	}else{
		if(!(T = (BinNode*) malloc(sizeof(BinNode)))){
			exit(0);
		}
		T->data = ch;
		printf("数据%c\n", T->data);
		createBinTree(T->lchild);
		createBinTree(T->rchild);
	}
}

/*递归实现二叉树的遍历方法*/
void preOrderTraverse(BinTree &T){
	if(T){
		printf("%c",T->data);
		preOrderTraverse(T->lchild);
		preOrderTraverse(T->rchild);
	}
}
void InOrderTravese(BinTree &T){
	if(T){
		InOrderTravese(T->lchild);
		printf("%c",T->data);
		InOrderTravese(T->rchild);
	}
}
void BackOrderTraverse(BinTree &T){
	if(T){
		BackOrderTraverse(T->lchild);
		BackOrderTraverse(T->rchild);
		printf("%c",T->data);
	}
}


/*非递归的实现二叉树的遍历，需要借助于栈结构*/
int InOrderTravese_1(BinTree &T){
	SqStack S;
	InitStack(S);
	BinTree p;
	p = T;
	while( p || !StackEmpty(S)){
		if(p){
			Push(S,p);
			p = p->lchild;
		}
		else{
			Pop(S,p);
			printf("%c",p->data);
			p= p->rchild;
		}

	}
	return 1;
}

/*迭代版本，即非递归的先序遍历 */
int preOrderTraverse_1(BinTree &T){
	SqStack S;
	InitStack(S);
	BinTree p = T;
	while(true){
		while(p){
			printf("%c",p->data);
			Push(S,p->rchild);
			p = p->lchild;
		}
		if(StackEmpty(S))
			break;
		Pop(S,p);
	}
}

int preOrderTraverse_2(BinTree &T){
	SqStack S;
	InitStack(S);
	BinTree p= T;
	while(p || !StackEmpty(S)){
		if(p){
			printf("%c",p->data);
			Push(S,p);
			p= p->lchild;
		}else{
			Pop(S,p);
			p = p->rchild;
		}
	}
}

int main(){
	BinTree T;
	createBinTree(T);
	printf("递归版本的先序遍历");
	preOrderTraverse(T);
	printf("\n递归版本的中序遍历");
	InOrderTravese(T);
	printf("\n递归版本的后序遍历");
	BackOrderTraverse(T);
	printf("\n迭代版本的中序遍历");
	InOrderTravese_1(T);
	printf("\n迭代版本的先序遍历");
	preOrderTraverse_1(T);
	printf("\n");
	preOrderTraverse_2(T);
	//printf("\n迭代版本的后序遍历");
	//BackOrderTraverse_1(T);
	return 0;
}


int InitStack(SqStack &S){
	S.base = (BinTree *) malloc (STACK_INIT_SIZE * sizeof(BinTree));
	if(!S.base)
		exit(-1);
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;
	return 1;
}

int GetTop(SqStack &S,BinTree &e){
	if(S.top == S.base)
		return -1;
	e = *(S.top -1); 
	return 1;
}
int Push(SqStack &S,BinTree &e){
	if(S.top - S.base >= S.stacksize){
		S.base = (BinTree * ) realloc(S.base,(S.stacksize + STACKINCREMENT)*sizeof(BinTree));
		if(!S.base)
			exit(-1);
		S.top = S.base + S.stacksize;
		S.stacksize += STACKINCREMENT;
	}
	*S.top++ = e;
	return 1;
}

int Pop(SqStack &S,BinTree &e){
	if(S.top == S.base)
		return -1;
	e = *--S.top;
	return 1;

}
int StackLength(SqStack S){
	return S.top - S.base;
}


int StackEmpty(SqStack &S){
	if(S.top == S.base){
		return 1;
	}
	else 
		return 0;
}

int ClearStack(SqStack &S){
	 S.top = S.base; 
}

int DestroyStack(SqStack &S){
	free(S.base);
	S.base = NULL;
	S.top = NULL;
	S.stacksize = 0;
	return 1;
}