摘要:试题五(共15分)阅读下列说明和C函数代码,将应填入(n)处的字句写在答题纸的对应栏内。【说明】对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点,且每个结点仅访问一次的过程。函数InOrder()借助栈实现二叉树的非递归中序遍历运算。设二叉树采用二叉链表存储,结点类型定义如下:
试题五(共 15 分)
阅读下列说明和C 函数代码,将应填入 (n) 处的字句写在答题纸的对应栏内。
【说明】
对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点,且每个结点仅访问一次的过程。函数InOrder()借助栈实现二叉树的非递归中序遍历运算。
设二叉树采用二叉链表存储,结点类型定义如下:
typedef struct BtNode{
ElemType data; /*结点的数据域,ElemType的具体定义省略*/
struct BtNode *lchild,*rchild; /*结点的左、右孩子指针域*/
}BtNode, *BTree;
在函数InOrder()中,用栈暂存二叉树中各个结点的指针,并将栈表示为不含头结点
的单向链表(简称链栈),其结点类型定义如下:
typedef struct StNode{ /*链栈的结点类型*/
BTree elem; /*栈中的元素是指向二叉链表结点的指针*/
struct StNode *link;
}StNode;
假设从栈顶到栈底的元素为 en、en-1、…、e1,则不含头结点的链栈示意图如图5-1所示。
【C函数】
int InOrder(BTree root) /* 实现二叉树的非递归中序遍历 */
{
BTree 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*/
[答案讨论]
软考备考资料免费领取
去领取