软件水平考试

【分析解答题】阅读下列说明和C函数代码，在(n)处填入适当的字句。
[说明]
对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个节点，且每个节点仅访问一次的过程。函数InOrder()借助栈实现二叉树的非递归中序遍历运算。
设二叉树采用二叉链表存储，节点类型定义如下。
typedef structBtNode
ElemTypedata;/*节点的数据域，ElemType的具体定义省略*/
structBtNode *lchild，*rchild;/*节点的左、右孩子指针域*/
BtNode, *BTree；
在函数InOrder()中，用栈暂存二叉树中各个节点的指针，并将栈表示为不含头节点的单向链表(简称链栈)，其节点类型定义如下。
typedef struct StNode/*链栈的节点类型*/
BTree elem;/*栈中的元素是指向二叉链表节点的指针*/
struct StNode *link;
StNode;
假设从栈顶到栈底的元素为e_n，e_e-1，…，e₁，则不含头节点的链栈示意图如图8.12所示。

[C函数]
int InOrderBTree root)/*实现二叉树的非递归中序遍历 */

Brrree ptr;/*ptr用于指向二叉树中的节点 */
StNode *q;/*q暂存链栈中新创建或待删除的节点指针*/
StNode *stacktop=NULL;/*初始化空栈的栈顶指针stacktop*/
ptr=root;/*ptr指向二又树的根节点 */
while ( (1) || stacktop!=NULL)
while (ptr!=NULL)
q= (StNode *)malloc(sizeof (StNode));
if (q==NULL)
return-1;
q-＞elem=ptr;
(2) ；
stacktop=q;/*stacktop指向新的栈顶*/
ptr= (3) ；/*进入左子树*/

q= stacktop;
(4) ；/*栈顶元素出栈*/
visit (q)；/*visit是访问节点的函数，其具体定义省略*/
ptr= (5) ;/*进入右子树*/
free (q)；/*释放原栈顶元素的节点空间*/

return 0：
/*InOrder*/

网考网解析：
试题答案：(1) ptr!=NULL (2) q-＞link=stacktop (3) ptr=ptr-＞lchild (4) stacktop=stacktop-＞link (5) q-＞rchild 答案解析：[要点解析] 本题表面上是求非递归中序遍历，其实大部分是链栈的内容。二叉树中序遍历非递归算法使用一个栈，其基本思想为： 根节点入栈S． While(栈不空) { 读取将栈顶节点信息。 依次将栈顶节点的左子树的根节点入栈。本步为一个循环，直到最左节点入栈时结束。 将栈顶节点出栈，访问之。 如果栈项节点具有右子树，则将右子树的根节点入栈，下一次循环将中序遍历此右子树。 } 其实就是一个劲儿的找当前节点的左子树，直至最左为止，路上的左子树全部入栈。然后访问最左左子树的那个节点，再按照这个方法遍历这个节点的右孩子。 (1)其实可以猜出来，这里对二叉树的遍历，都将依靠ptr来完成，所以是ptr不能为NULL。如果ptr和栈都是空的，就说明遍历完成了。 (2)这里演示链栈的插入，新节点的下一个节点为栈顶节点，所以q-＞link=stacktop。 (3)访问最左节点，自然ptr等于左孩子，即ptr-＞1child。就算不懂算法也没有关系，题目中都提示了“进入左子树”。 (4)这里是链栈的出栈，栈顶指针移动到下一个节点，即stacktop-＞link。 (5)到节点的右子树，其实题目中提示了“进入右子树”，大胆写就行了。 document.getElementById("warp").style.display="none"; document.getElementById("content").style.display="block"; 查看试题解析出处>>