问答题
在二叉链表表示的二叉树中，增设一个指针域，初值为空，试给出算法在不使用堆栈又不破坏原二叉树的情况下，前序遍历该二叉树。【北京邮电大学2004五、2(15分)】
【正确答案】正确答案：将空指针(下面的pre)域改成指向双亲(或祖先)。核心语句段如下： while(t) ／／t初值是二叉树根结点的指针 {while(t) {coht<data ； ／／访问结点 t一>pre=f； ／／指向双亲，初值f=null f=t；t=t一>lchild； ／／沿左侧向下 } t=f； ／／回退 while(t&&t一>rchild==null) t=t一>pre； ／／回返 if(t&&t一>rchild) {f=t一>pre； ／／避免从右侧返回时，再重复访问左侧 t=t一>rchild； ／／右转 } }
【答案解析】