试题五

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

设二叉树的结点数据类型为：

typedef struct node{

char data;

struct node *left;

struct node *right：

}BTREE;

[函数5.1说明]

函数void SortTreelnsert(BTREE **tree，BTREE*s)采用递归方法，将结点s插入以*tree为根结点指针的二叉排序树(二叉查找树)中。

[函数5.1)

void SortTreelnsert(BTREE **tree，BTREE *S)

{ if(*tree = = NULL) *tree=S;

else if(S->data<(*tree)->data)

SortTreelnsert( (1) ，S);

else if(S->data>(*tree)->data)

SortTreelnsert( (2) ，S);

}

[函数5.2说明]

函数void TraversalTree(BTREE *tree)用非递归方法，对以tree为根结点指针的二叉树进行后序遍历。

[函数5，2]

void TraversalTree(BTREE *tree)

{ BTREE *stack[1000]，*p;

int tag[1000]，top=0;

p=tree;

do {

while(p!=NULL){

stack[++top]=p;

(3) ;

tag[hop]=0; /*标志栈顶结点的左子树已进行过后序遍历*/ ：

}

while(top>0 && (4) ){ /* 栈顶结点的右子树是否被后序遍历过*/

p=stack[top--];

putchar(p->data);

}

if (top>0) { /*对栈顶结点的右子树进行后序遍历*/

(5) ;

tag[top]=1;

}

}while(top>0);

}

答案解析