标志非递归后序遍历二叉树,该如何解决
标志非递归后序遍历二叉树
typedef struct{
BiTNode *ptr;
int tag;//0,1
}SElemType;
typedef struct BiTNode{
TElemType data;
BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
基本栈操作。。。。。。。
void PostOrder(BiTree bt, void (*visit)(TElemType))
/* 使用栈,非递归后序遍历二叉树bt, */
/* 对每个结点的元素域data调用函数visit */
{
SElemType S;
InitStack(S);
SElemType p;
p.ptr=bt;
p.tag=0;
while(p.ptr||!StackEmpty(S))
{
if(p.ptr&&!p.tag)
{
Push(S,p);
p.ptr=p.ptr->lchild;
p.tag=0;
}
else
{
Pop(S,p);
if(p.ptr->rchild&&!p.tag)
{
p.tag=1;
Push(S,p);
p.ptr=p.ptr->rchild;
p.tag=0;
}
else
{
visit(p.ptr->data);
p.ptr=NULL;
}
}
}
}
不知道哪里错了,就是通不过作业测试平台,求教
------解决方案--------------------
不好意思pop() 函数丢了些东西。
typedef struct{
BiTNode *ptr;
int tag;//0,1
}SElemType;
typedef struct BiTNode{
TElemType data;
BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
基本栈操作。。。。。。。
void PostOrder(BiTree bt, void (*visit)(TElemType))
/* 使用栈,非递归后序遍历二叉树bt, */
/* 对每个结点的元素域data调用函数visit */
{
SElemType S;
InitStack(S);
SElemType p;
p.ptr=bt;
p.tag=0;
while(p.ptr||!StackEmpty(S))
{
if(p.ptr&&!p.tag)
{
Push(S,p);
p.ptr=p.ptr->lchild;
p.tag=0;
}
else
{
Pop(S,p);
if(p.ptr->rchild&&!p.tag)
{
p.tag=1;
Push(S,p);
p.ptr=p.ptr->rchild;
p.tag=0;
}
else
{
visit(p.ptr->data);
p.ptr=NULL;
}
}
}
}
不知道哪里错了,就是通不过作业测试平台,求教
------解决方案--------------------
不好意思pop() 函数丢了些东西。
- C/C++ code
int pop(void) { flag[top] = 0; return stack[top--]->data; }
------解决方案--------------------
看看我那个不需要标志的吧。