postordertraverse.c

二叉树后序遍历的非递归算法

#include<stdio.h>
#include<malloc.h>

#define STACK_INIT_SIZE 10
#define STACKINCREMENT 5

typedef struct BiTNode						//树结点
{
	char data;
	struct BiTNode *pLChild,*pRChild;
}BiTNode,*BiTree;

typedef struct								//堆栈
{
	BiTNode *base;
	BiTNode *top;
	int stacksize;
}*SqStack;

void InitStack(SqStack S)					//初始化
{
	S->base=(BiTNode *)malloc(STACK_INIT_SIZE*sizeof(BiTNode));
	if(!S->base) exit(0);
	S->top=S->base;
	S->stacksize=STACK_INIT_SIZE;
}

int StackEmpty(SqStack S)
{
	if(S->base==S->top) return 1;
	return 0;
}

void push(SqStack S,BiTNode *e)				//压栈
{
	if(S->top-S->base>=S->stacksize)        //空间不足
	{
		S->base=(BiTNode *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(BiTNode));
		S->stacksize+=STACKINCREMENT;
	}
	if(e)									//将数据存入堆栈中
	{
		S->top->data=e->data;
		S->top->pLChild=e->pLChild;
		S->top->pRChild=e->pRChild;
	}
	else									//空指针存入无效数据
	{
		S->top->data='*';
	}
	S->top++;

}

BiTNode *pop(SqStack S)						//弹出节点
{
	BiTNode *t;

	t=(BiTNode *)malloc(sizeof(BiTNode));	//开BiTNode指针用于储存弹出节点

	if(S->top==S->base) exit(0);			//栈空
	--S->top;
	if(S->top->data!='*')					//堆栈存有有效数据
	{
		t->data=S->top->data;				//用t来接收
		t->pLChild=S->top->pLChild;
		t->pRChild=S->top->pRChild;
		return t;
	}
	else									//堆栈存为无效数据
	{
		return S->top;						//弹出无效数据
	}
}

BiTNode *GetTop(SqStack S)					//返回堆栈的第一个节点
{
	if(S->top==S->base) 
	{
		return NULL;	
	}
	return (S->top-1);
}

BiTree CreatBiTree()						//建立二叉树
{
	char ch;
	BiTree T;

	printf("请输入节点数据：\n");
	scanf("%c",&ch);						//读结点数据
	getchar();								//取回车符
			
	if(ch=='*') T=NULL;						//如果为*说明该指针为空
	else
	{
		if(T=(BiTree)malloc(sizeof (BiTNode)))
		{
			T->data=ch;						
			
			T->pLChild=CreatBiTree();		//同理建立左叉树
			T->pRChild=CreatBiTree();
		}
	}
	return T;								//返回树指针
}

void Visit(char e)							//打印数据
{
	printf("%c",e);
}

void PostOrderTraverse(BiTree T)			//后序遍历
{
	SqStack S;
	BiTNode *p,*q;

	S=(SqStack)malloc(sizeof(SqStack));
	p=NULL;

	InitStack(S);
	push(S,T);
	while(!StackEmpty(S))
	{
		p=GetTop(S);
		while(p->data!='*')					//到左下位置
		{
			push(S,p->pLChild);
			p=GetTop(S);
		}
		q=pop(S);							//无效数据出栈
		if(((S->top-1)!=S->base)||((S->top-1)->pRChild))//剩余结点多余一个或者右结点非空
		{
			if((S->top-1)->pRChild)			//右结点存在
			{
				push(S,(S->top-1)->pRChild);//右结点入栈
				if(!(((S->top-1)->pRChild)||((S->top-1)->pLChild)))//入栈结点无左右孩子
				{
					q=pop(S);				//出栈
					Visit(q->data);			
					(S->top-1)->pRChild=NULL;//将其父结点的右孩子置空
				}
			}
			else							//左右节点都不存在
			{
				q=pop(S);				
				Visit(q->data);
				if((S->top-1)->pRChild->data==q->data)//该出栈结点位于树中的右子树
				{
					(S->top-1)->pRChild=NULL;//将其父节点的右孩子置空			
				}
				else
				(S->top-1)->pLChild=NULL;	//否则左孩子置空
			}
		}
		else								//剩下一个节点		 
		{
			q=pop(S);
			Visit(q->data);
		}
	}
}

int main()
{
	BiTree Tree;

	Tree=NULL;

	Tree=CreatBiTree();
	PostOrderTraverse(Tree);
}