阅读下列说明和c函数代码,将应填入 (n)处的字句写在答题纸的对应栏内。【说明】对二叉树进行遍历是

Question

阅读下列说明和c函数代码，将应填入 (n) 处的字句写在答题纸的对应栏内。

【说明】

对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点，且每个结点仅访问一次的过程。函数InOrder。()借助栈实现二叉树的非递归中序遍历运算。

设二叉树采用二叉链表存储，结点类型定义如下：

typedef struct BtNode{

ElemTypedata； ／*结点的数据域，ElemType的具体定义省略*／

struct BtNode*ichiid，*rchild； ／*结点的左、右弦子指针域*／

)BtNode，*BTree；

在函数InOrder()中，用栈暂存二叉树中各个结点的指针，并将栈表示为不含头结点

的单向链表(简称链栈)，其结点类型定义如下：

typedef struct StNode{ ／*链栈的结点类型*／

BTree elem； ／*栈中的元素是指向二叉链表结点的指针*／

struct StNode*link；

}S％Node；

假设从栈顶到栈底的元素为en、en-1、…、e1，则不含头结点的链栈示意图如图5—5

所示。

【C函数】

int InOrder(BTree root) ／*实现二叉树的非递归中序遍历*／

{

BTree ptr； ／*ptr用于指向二又树中的结点*／

StNode*q； ／*q暂存链栈中新创建或待删除的结点指针+／

StNode*stacktop=NULL； ／*初始化空栈的栈顶指针stacktop*／

ptr=root； ／*ptr指向二叉树的根结点*／

while( (1 ) I I 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*／

Answer 1

正确答案：(1)ptr! =NULL或ptr! =0或ptr(2)q->link=stacktop(3)ptr->lchild(4)stacktop=stacktop->link或stacktop=q->link(5)q->elem->rchild
(1)ptr! =NULL或ptr! =0或ptr(2)q->link=stacktop(3)ptr->lchild(4)stacktop=stacktop->link或stacktop=q->link(5)q->elem->rchild 解析：对非空二叉树进行中序遍历的方法是：先中序遍历根节点的左子树，然后访问根节点，最后中序遍历根节点的右子树。从以上算法的执行过程可知，从树根出发进行遍历时，递归调用InOrderTraversing(root-LeftChild)使得遍历过程沿着左孩子分支一直走向下层节点，直到到达二叉树中最左下方的节点(设为f)的空左子树为止，然后返回节点，再由递归调用InOrder Traversing(root->RightChild)进入f的右子树，并重复以上过程。在递归算法执行过程中，辅助实现递归调用和返回处理的控制栈实际上起着保存从根节点到当前节点的路径信息。用非递归算法实现二叉树的中序遍历时，可以由一个循环语句实现从指定的根节点m发，沿着左孩子分支一直到头(到达一个没有左子树的节点)的处理，从根节点到当前节点的路径信息(节点序列)可以明确构造一个栈来保存。