一棵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; //取右子树 } } }