【正确答案】(1)初步框架
   抽象类型及基本运算：用BNode表示结点的抽象类型，用BTree表示二叉树的抽象类型。
   二叉树的基本运算有3种。
   ·BNode leflChild(BNode p)
   返回p结点的左子女结点，当指定结点没有左子女时，返回一个特殊结点NULL。
   ·BNode rightChild(BNode p)
   返回p结点的右子女结点，当指定结点没有右子女时，返回一个特殊结点NULL。
   ·BNode parent(BNode p)
   返回p结点的父结点，当指定结点没有父结点时，返回一个特殊结点NULL。
   1)递归算法
   void PreOrder(BNode p){    /*先根周游以p为根的二叉树*/
       if(p==NULL) return;
       visit(p);
       preOrder(leftChild(p));
       preOrder(rightChild(p));
   }
   2)思路
   利用栈将上述递归算法转换为一个等价的非递归算法。
   3)非递归算法
   void nPreOrder(BNode p){    /*先根周游以p为根的二叉树*/
       Stack s;    /*栈元素的类型是BNode*/
       BNode c;
       if(p==NULL)return;
       s=createEmptyStack();
       push(s,p);
       while(!isEmptyStack(s)){    /*每当栈不空*/
           c=top(s);
           pop(s);    /*取栈顶,出栈*/
           if(c!=NULL){
               visit(c);    /*访问*/
               push(s,rightChild(c));  /*右子女(右子树的根结点)进栈*/
               push(s.leftChild(c));    /*左子女(左子树的根结点)进栈*/
           }
       }
   }
   (2)具体算法
   1)数据结构
   采用二叉树的链接表示，同时采用栈的顺序表示。
   typedefPBinTreeNode DataType;  /*栈元素的类型是PBinTreeNode*/
   struct SeqStack{
       DataType s[MAXNUM];
       intt;
   };
   typedef struct SeqStack*PSeqStack;
   2)算法
   将上述算法框架具体化，得到如下算法。
   void npreOrder btree(BinTree btree){    /*先根周游二叉树btree*/
       PSeqStack s:    /*栈元素的类型是PBinTreeNode*/
       PBinTreeNode c;
       if(btree==NULL)return;
       s=createEmpty Stack_seq();
       push_seq(s,btree);
       while(!isEmptyStack_seq(s)){    /*每当栈不空*/
           c=top_seq(s);
           pop_seq(s);    /*取栈顶,出栈*/
           if(c!=NULL){
               visit(c);    /*访问*/
               push_seq(s.c-＞rlink);    /*右子女(右子树的根结点)进栈*/
               push_seq(s.c-＞llink);    /*左子女(左子树的根结点)进栈*/
           }
       }
   }
   3)代价分析
   该算法对每个结点访问1次，时间代价为O(n)，空间代价为O(h)。