习题－34.c

本人收集的一些数据结构经典算法实现

//本程序只给出了算法思想
//读者可以自己完善本程序
typedef struct {
	BTNode* ptr;
	enum {0,1,2} mark;
} PMType; //有mark域的结点指针类型 
void PostOrder_Stack(BiTree T)//后续遍历二叉树的非递归算法,用栈
{
	PMType a;
	InitStack(S); //S的元素为PMType类型
	Push (S,{T,0}); //根结点入栈
	while(!StackEmpty(S))
	{
		Pop(S,a);
		switch(a.mark)
		{
		case 0:
			Push(S,{a.ptr,1}); //修改mark域
			if(a.ptr->lchild) 
				Push(S,{a.ptr->lchild,0}); //访问左子树
			break;
		case 1:
			Push(S,{a.ptr,2}); //修改mark域
			if(a.ptr->rchild) 
				Push(S,{a.ptr->rchild,0}); //访问右子树
			break;
		case 2:
			visit(a.ptr); //访问结点,返回
		}
	}//while
}//PostOrder_Stack