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

●试题二

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

【说明】

函数print(BinTreeNode*t；DateType ＆x)的功能是在二叉树中查找值为x的结点，并打印该结点所有祖先结点。在此算法中，假设值为x的结点不多于一个。此算法采用后序的非递归遍历形式。因为退栈时需要区分右子树。函数中使用栈ST保存结点指针ptr以及标志tag，Top是栈顶指针。

【函数】

void print(BinTreeNode*t；DateType ＆x){

stack ST；int i，top；top=0；∥置空栈

while(t!=NULL ＆＆t->data!=x‖top!=0)

{while(t!=NULL ＆＆ t->data!=x)

{

∥寻找值为x的结点

(1) ；

ST［top］．ptr=t；

ST［top］．tag=0；

(2) ；

}

if(t!=Null ＆＆ t->data==x){∥找到值为x的结点

for(i=1； (3) ；i＋＋)

printf("％d"，ST［top］．ptr->data)；}

else{

while( (4) )

top--；

if(top>0)

{

ST［top］．tag=1；

(5) ；

}

}

}

正确答案：

●试题二【答案】(1)top＋＋(2)t=t->leftChild(3)i=top(4)top>0 ＆＆ ST［top］．tag=1(5)t=ST［top］．ptr->rightChild【解析】这个程序是一个典型二叉树后序遍历非递归算法的应用。算法的实现思路是：先扫描根结点的所有左结点并入栈；当找到一个结点的值为x，则输入出栈里存放的数据，这些数据就是该结点所有祖先结点；然后判断栈顶元素的右子树是否已经被后序遍历过，如果是，或者右子树为空，将栈顶元素退栈，该子树已经全部后序遍历过；如果