习题－35.c

来自「本人收集的一些数据结构经典算法实现」· C语言 代码 · 共 30 行

//本程序只给出了算法思想
//读者可以自己完善本程序
typedef struct {
	int data;
	EBTNode *lchild;
	EBTNode *rchild;
	EBTNode *parent;
	enum {0,1,2} mark;
} EBTNode,EBitree; //有mark域和双亲指针域的二叉树结点类型 
void PostOrder_Nonrecursive(EBitree T)//后序遍历二叉树的非递归算法,不用栈
{
	p=T;
	while(p)
		switch(p->mark)
	{
case 0:
	p->mark=1;
	if(p->lchild) p=p->lchild; //访问左子树
	break;
case 1:
	p->mark=2;
	if(p->rchild) p=p->rchild; //访问右子树
	break;
case 2:
	visit(p);
	p->mark=0; //恢复mark值
	p=p->parent; //返回双亲结点
	}
}//PostOrder_Nonrecursive