问答题
下面是一个二叉树的前序遍历的递归算法。
void PreOrder(BiTNode
*
t){
if(t!=NULL){ //递归结束条件
cout＜＜t-＞data; //访问(输出)根结点
Preorder(t-＞lchild); //前序遍历根的左子树
Preorder(t-＞rchild); //前序遍历根的右子树
}
}
问答题
改写PreOrder算法，消去第二个递归调用PreOrder(t-＞rchild)；
【正确答案】
【答案解析】消去第二个递归语句时，视第一个递归语句为一般语句，按尾递归处理。
void preOrder(BiTNode
*
t) {
while(t!=NULL){ //按尾递归改为循环
cout＜＜t-＞data;
PreOrder(t-＞lchild);
t=t-＞rchild; //向右子树循环
}
}
问答题
利用栈改写PreOrder算法，消去两个递归调用。
【正确答案】
【答案解析】定义一个栈，在访问某一个结点时保存其右、左子女结点的地址。下一步将先从栈中退出右子女结点，对其进行遍历，然后从栈中退出左子女结点，对其进行遍历。
void PreOrder(BiTNode
*
t){
BiTNode
*
p;
Stack S;initStack(S);push(S,t);
while (!IsEmpty(s)){
pop (S,p);
cout＜＜p-＞data;
if(p-＞rchild!=NULL)push(S,p-＞rchild);
if(p-＞lchild!=NULL)push(S,p-＞ichild);
}
}