一棵n个结点的完全二叉树存放在二叉树的顺序存储结构中，试编写非递归算法对该树进行先序遍历。

一棵n个结点的完全二叉树存放在二叉树的顺序存储结构中，试编写非递归算法对该树进行先序遍历。

按照题目要求，附加一个工作栈以完成对该树的非递归遍历，思路如下： (1)每访问一个结点，将此结点压入栈，查看此结点是否有左子树，若有，访问左子树，转(1)执行； (2)从栈弹出一结点，如果此结点有右子树，访问右子树并转第(1)步执行，否则转第(2)步执行。 void preorder(DataType a[n]，int n) ／／a[i]表示二叉树以顺序存储；n为元素个数 { InitStack(sd)； ／／初始工作栈sd i=1；Push(sd，0)； if(i<=n) { visit(a[i])； ／／访问此结点 Push(sd，i)； j=2*i； ／／取左子树 while(!EmptyStack(sd)) ／／若栈sd非空 { while(j<=n) ／／若2i<=n，则该结点有左子树 { Push(sd，j)； ／／进栈 i=j；j=2*i； ／／取左子树 visit(a[i])； ／／访问此结点 ｝ i=Pop(sd)； ／／出栈 j=2*i+1； ／／取右子树 ｝ ｝ ｝