列表

详情

阅读下列说明和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*/

参考答案:

（1）ptr !=NULL，或ptr !=0，或ptr
（2）q->link=stacktop
（3）ptr->lchild
（4）stacktop=stacktop->link，或stacktop =q->link
（5）q->elem->rchild

详细解析:

    本题考查基本数据结构和C语言程序设计能力。
    对非空二叉树进行中序遍历的方法是：先中序遍根节点的左子树，然后访问根节点，最后中序遍历根节点的右子树。用递归方式描述的算法如下：
  void  In_Order_Traversing(BiTree root)
   {   //root 是指向二叉树根节点的指针
       if(root !=NULL) {
            in_Order_Traversing(root->Leftchild);
            visit(root);
            In_Order_Traversing(root->Rightchild);
          }
       }

    从以上算法的执行过程中可知，从树根出发进行遍历时，递归调用In_Order_Traversing(root->LeftChild）使得遍历过程沿着左孩子分支直走向下层节点，直到到达二叉树中最左下方的节点（设为f）的空左子树为止，然后返回f节点，再由递归调用In_Order_Traversing(root->RightChild)进入f 的右子树，并重复以上过程。在递归算法执行过程中，辅助实现递归调用和返回处理的控制栈实际上起着保存从根节点到当前节点的路径信息。
    用非递归算法实现二叉树的中序遍历时，可以由一个循环语句实现从指定的根节点出发，沿着左孩子分支一直到头（到达一个没有左子树的节点）的处理，从根节点到当前节点的路径信息（节点序列）可以明确构造一个栈来保存。
    本题目的难点在于将栈的实现和使用混合在一起来处理，而且栈采用单链表存储结构。下面分析题中给出的代码。
    空（1）是遍历的条件之一，由于另外个条件stacktop!= NULL初始时是不成立的，因此空（1）所表示的条件必须满足，由于是对非空二叉树进行遍历，显然该条件代表二叉树非空，即ptr!= NULL或其等价表示形式。
    临时指针ptr初始时指向整个二叉树的根节点，此后用以下代码表示一直沿左孩子指针链向下走的处理，临时指针q用于在链栈中加入新元素时使用。处理思路是：若当前节点有左子树，则将当前节点的指针存入栈中，然后进入当前节点的左子树。入栈时，先申请元素在链栈中的节点空间，然后设置节点数据域的值（即当前节点的指针），最后将新申请的节点加入链栈首部。
while(ptr!=Null){
     q=(StNode *)malloc(sizeof(StNode));          /*为新入栈的元素创建节点*/
     if (q==Null)                       /*若创建新节点失败，则退出*/
       return -1；
      q->elem=ptr;                     /*在栈顶保存指向当前节点的指针*/
      q->link=stacktop;                 /*新节点加入栈顶*/
stacktop=q;                             /*更新栈顶指针，即stacktop指向新的栈顶*/
ptr=ptr->lchild;                       /*进入当前节点的左子树*/
}
    当上述过程进入一棵空的子树时（ptr为空指针），循环结束。此后，应该从空的子树返回其父节点并进行访问。由于进入空的左子树前已将其父节点指针压入栈中，因此，栈顶元素即为该父节点，对应的处理就是弹栈。相应地，在链栈中要删除表头节点并释放节点空间：
    q=stacktop;                       /*q指向链栈中需要删除的节点，即栈顶元素*/
    stack=stacktop->link;        /*栈顶元素出栈*/
    visit(q);                             /*访问节点*
    free(q);                             /*释放节点空间*/
    由于还需要通过q指针进入被删除节点的右子树，因此，释放节点空间的操作free(q)操作之前，使ptr抬向q所指节点的右子树指针，以得到被删除节点的数据域信息，即空（5）所在语句ptr= q->elem->rchild。
指针是C语言中灵活且非常强大的工具，是否热练掌握C语言的判断条件之一就是对指针的理解和使用。软件设计师需要熟练掌握这些内容。
 

上一题

© 2025 educity.cn