二叉树先序遍历非递归算法问题

Question

访问了一个结点，而后他的左孩子，右孩子，然后怎么回到这个结点的双亲结点呢。。。

Answer 1

#define maxsize 100
typedef struct
{
Bitree Elem[maxsize];
int top;
}SqStack;

void PreOrderUnrec(Bitree t)
{
SqStack s;
StackInit(s);
p=t;

while (p!=null || !StackEmpty(s))
{
while (p!=null) //遍历左子树
{
visite(p->data);
push(s,p);
p=p->lchild;
}//endwhile

if (!StackEmpty(s)) //通过下一次循环中的内嵌while实现右子树遍历
{
p=pop(s);
p=p->rchild;
}//endif

}//endwhile

}//PreOrderUnrec追问

假如说访问完根结点的左子树的所有结点，接下来要怎么回到根结点，然后再去右子树呢。。。递归算法的话有个回溯，非递归要怎么回去？即使用的是三叉链表，也没有调用指向双亲指针的操作啊。。。

追答

每次都将遇到的节点压入栈，当左子树遍历完毕后才从栈中弹出最后一个访问的节点，访问其右子树.然后这样一直回到第一次压入栈的根节点,然后在按照先序的算法访问根节点右边的子树.

Answer 2

在结点中添加一个指向父亲的指针追问

那样就是三叉链表了。。。用二叉链表的情况呢

追答

没标记的话回不去啊。。。

追问

那二叉链表还有神马存在的必要。。。

而且在算法里没有指向双亲指针的操作？

追答

查找快。。。
遍历的时候用二叉的话够呛。。。

追问

查找不也需要遍历吗。。。
而且在先序遍历中，访问结点——压栈其地址——访问左孩子——回到这个结点并出栈其地址——访问右孩子。访问完右孩子后没有再次读取其地址，即使是三叉链表又怎么能返回双亲。。。

追答

用堆栈模拟的时候，访问完右孩子后遍历就结束了啊，不用再返回双亲了。。。
如果用三叉链表的话，从右孩子本身就能找到他的父亲结点了