2. 计算机
  3. 阅读下列函数说明和C代码，将应填入(n) 处的字句写在对应栏内。 【说明】 函数print(BinTreeNode*t; DateType &x)的功能是在二叉树中查找值为x的结点，并打印该结点所有祖先结点。在此算法中，假设值为x的结点不多于一个。此

阅读下列函数说明和C代码，将应填入(n) 处的字句写在对应栏内。 【说明】 函数print(BinTreeNode*t; DateType &x)的功能是在二叉树中查找值为x的结点，并打印该结点所有祖先结点。在此算法中，假设值为x的结点不多于一个。此

admin2009-02-15  74
问题 阅读下列函数说明和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，则输入出栈里存放的数据，这些数据就是该结点所有祖先结点；然后判断栈顶元素的右子树是否已经被后序遍历过，如果是，或者右子树为空，将栈顶元素退栈，该子树已经全部后序遍历过；如果不是，则对栈顶结点的右子树进行后序遍历，此时应把栈顶结点的右子树的相结点放入栈中。再重复上述过程，直至遍历过树中所有结点。
   (1)、(2)空年在循环就是扫描根结点的所有左结点并入栈，根据程序中的栈的定义，栈空时top=0，因此在入栈时，先将栈顶指针加1，因此(1)空处应填写“top++”或其等价形式，(2)空是取当前结点的左子树的根结点，因此应填写“t=t-＞leftChild”。
   (3)空所在循环是处理找到值为x的结点，那么该结点的所有祖先结点都存放在栈中，栈中的栈底是二叉树的根，而栈顶元素是该结点的父结点，因此，(3)空处应填写“i=top”。
   (4)空所在循环是判断栈顶元素的右子树是否已经被后序遍历过，如果是，或者右子树为空，将栈顶元素退栈，这里要填写判断条件。 tag=0表示左子树，tag=1表示右子树，因此，(4)空处应填写“top＞ 0&&ST [top].tag=1”。
   (5)空所在语句块是处理栈顶元素的右子树没有被后序遍历情况，则将右子树入栈，因此(5)空处应填写“t=ST[top].ptr-＞rightChild”。
转载请注明原文地址:https://kaotiyun.com/show/NbjZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

相关试题推荐
随机试题
最新回复(0)