问题
问答题 案例分析题
阅读以下函数说明和C语言函数,将应填入____处的字句写在答题纸的对应栏内。
已知一棵二叉树用二叉链表存储,t指向根节点,p指向树中任一节点。下列算法为输出从t到p之间路径上的节点。
答案
参考答案:
(1)top++(2)q=q->lchild(3)while(top>0)(4)stackl[top1]=q(5)top1>0
解析:本题本质上是对二叉树的先序遍历进行考核,但不是简单地进行先序遍历,而是仅遍历从根节点到给定的节点p为止。本题采用非递归算法来实现,其主要思想是:①初始化栈;②根节点进栈,栈不空则循环执行以下步骤直到发现节点p;③当前节点不为空且不为P进栈;④栈顶为p,则结束,否则转③;⑤若右子树访问过,则栈顶的右孩子为当前节点,转③。扫描左孩子,当相应的节点不为P时进栈,所以(1)填"top++",(2)填"q=q->lchild"。在栈不为空时则一直在dowhile循环中查找,因此(3)填"while(top>0)"。在进行反向打印准备时,读取stack[top]的信息放到stackl[topl]中,即(4)填"stackl[topl]=q"。打印栈中所有内容,所以(5)填"topl>0"。