请写出利用栈对二叉树进行对称次序周游的非递归算法。

正确答案：(1)初步框架 抽象类型及基本运算：用BNode表示结点的抽象类型用BTree表示二叉树的抽象类型。 二叉树的基本运算有3种。 ·BNode leftChild(BNode P) 返回p结点的左子女结点当指定结点没有左子女时返回一个特殊结点NULL。 ·BNode rightChild(BNode P) 返回p结点的右子女结点当指定结点没有右子女时返回一个特殊结点NULL。 ·BNode parent(BNode P) 返回p结点的父结点当指定结点没有父结点时返回一个特殊结点NULL。 1)思路 从二叉树的根结点开始令变量c为根结点。若c不为空时则令c沿其左子女结点前进在前进过程中把所经历的结点逐个压入栈中；当c为空时弹出栈顶元素送给c并访问该结点再令c为当前结点的右子女结点。重复上述过程当c为空并且栈也为空时周游结束。 2)非递归算法 void nInOrder(BNode P){ ／*对称序周游以p为根的二叉树*／ Stack s： ／*栈元素的类型是BNode*／ BNode c： if(p==NULL)return； s=createEmptyStack()； c=p； do{ while(c！=NULL){ push(sc)； c=leftChild(c)； } c=top(s)； pop(s)； visit(c)； c=rightChild(c)； }while(c!=NULL‖!isEmptyStack(s))； } (2)具体算法 1)数据结构 2)算法 将上述算法框架具体化得到如下算法。 void nlnOrder_btree(BinTree btree){ ／*对称次序周游二叉树btree*＼ PSeqStack s； ／*栈元素的类型是PBinTreeNode*／ PBinTreeNode c； if(btree==NULL)return； s=createEmptyStack_seq()； c=btree； do{ while(c!=NULL){ push_seq(sc)； c=c-＞llink； } C=top_seq(s)； pop_seq(s)； visit(c)； c=c-＞rlink； }while(c!=NULL‖！isEmptyStack_seq(s))； } 3)代价分析 该算法对每个结点访问1次时间代价为O(n)空间代价为O(h)。
(1)初步框架抽象类型及基本运算：用BNode表示结点的抽象类型,用BTree表示二叉树的抽象类型。二叉树的基本运算有3种。·BNodeleftChild(BNodeP)返回p结点的左子女结点,当指定结点没有左子女时,返回一个特殊结点NULL。·BNoderightChild(BNodeP)返回p结点的右子女结点,当指定结点没有右子女时,返回一个特殊结点NULL。·BNodeparent(BNodeP)返回p结点的父结点,当指定结点没有父结点时,返回一个特殊结点NULL。1)思路从二叉树的根结点开始,令变量c为根结点。若c不为空时,则令c沿其左子女结点前进,在前进过程中,把所经历的结点逐个压入栈中；当c为空时,弹出栈顶元素送给c,并访问该结点,再令c为当前结点的右子女结点。重复上述过程,当c为空并且栈也为空时,周游结束。2)非递归算法voidnInOrder(BNodeP){／*对称序周游以p为根的二叉树*／Stacks：／*栈元素的类型是BNode*／BNodec：if(p==NULL)return；s=createEmptyStack()；c=p；do{while(c！=NULL){push(s,c)；c=leftChild(c)；}c=top(s)；pop(s)；visit(c)；c=rightChild(c)；}while(c!=NULL‖!isEmptyStack(s))；}(2)具体算法1)数据结构2)算法将上述算法框架具体化,得到如下算法。voidnlnOrder_btree(BinTreebtree){／*对称次序周游二叉树btree*＼PSeqStacks；／*栈元素的类型是PBinTreeNode*／PBinTreeNodec；if(btree==NULL)return；s=createEmptyStack_seq()；c=btree；do{while(c!=NULL){push_seq(s,c)；c=c-＞llink；}C=top_seq(s)；pop_seq(s)；visit(c)；c=c-＞rlink；}while(c!=NULL‖！isEmptyStack_seq(s))；}3)代价分析该算法对每个结点访问1次,时间代价为O(n),空间代价为O(h)。