结构推理 二叉树以二叉链表存储,写出对二叉树进行先序遍历的非递归算法。
   解题思路:二叉树的先序遍历非递归算法利用栈结构,从二又树的根结点开始,输出结点信息,同时将结点指针入栈,然后顺着左子树,依次将其左子树各个结点值输出,同时结点指针入栈,直到左子树为空;然后让栈顶指针出栈,接着处理右子树。
【正确答案】算法如下:
   #define MAXSIZE 100
   #define NULL 0
   void preorder1(BTLINK*bt)
   {  BTLINK*S[HAXSIZE],*p;
       int top;
       top=0;    /*初始化空栈*/
       p=bt;
       do
       {  while(p!=NULL)
           {printf("/%4c",p->data);
               top++;
               if(top>MAXSIZE)    /*判断栈满*/
                   printf("Stack is full.");
               else
               {  s[top]=p;
                   p=p->lchild;    /*处理p的左子树*/
               }
           }
           if(top!=0)
           {  p=s[top];
               top=top-1;
               p=p->rchild;    /*处理p的右子树*/
           }
       }
       while((top!=0)||(P!=NULL));
   }
   main()
   {  BTLINK*bt;
       bt=createbt();    /*调用6.3节中建立二叉树的函数*/
       preorderl(bt);
   }
【答案解析】