在算法中使用了一个栈s, 在进入子表之前,将根结点指针进栈, 以便括号内的子女链接之用. 在子表处理结束时退栈. 相关的栈操作如下:

　　MakeEmpty(s) 置空栈

　　Push(s,p) 元素p进栈

　　Pop(s) 进栈

　　Top(s) 存取栈顶元素的函数

　　下面给出了建立二叉树的算法, 其中有5个语句缺失. 请阅读此算法并把缺失的语句补上. (每空3分)

　　Void CreateBinTree(BinTreeNode *&BT, char ls){

　　Stacks; MakeEmpty(s);

　　BT=NULL; //置二叉树

　　BinTreeNode *p;

　　int k;

　　istream ins(ls); //把串ls定义为输入字符串流对象ins

　　Char ch;

　　ins>>ch; //从ins顺序读入一个字符

　　While(ch!=”#”){ //逐个字符处理,直到遇到''#''为止

　　Switch(ch){

　　case’(‘: _______(1)_______

　　k=1;

　　break;

　　case’)’: pop(s);

　　break;

　　case’,‘: _______(2)_______

　　break;

　　default: p=new BinTreeNode;

　　_______(3)_______

　　p->leftChild=NULL;

　　p->rightChild=NULL;

　　if(BT==NULL)

　　_______(4)_______

　　else if (k==1) top(s)->leftChild=p;

　　else top(s)->rightChild=p;

　　}

　　_______(5)_______

　　}

　　}

　　七、下面是一个用C编写的快速排序算法. 为了避免最坏情况,取基准记录pivot采用从left,right和mid=[(left+right)/2]中取中间值, 并交换到right位置的办法. 数组a存放待排序的一组记录, 数据类型为Type, left和right是呆排序子区间的最左端点和最右端点.

　　Void quicksort(Type a&#;,int left,int right){

　　Type temp;

　　If(leftType pivot=median3(a,left,right);

　　Int I=left, j=right-1;

　　For( ; ; ){

　　While(iWhile(iif(itemp=a[i]; a[j]=a[i]; a[i]=temp;

　　I++; j--;

　　}

　　else break;

　　}

　　if(a[i]>pivot)

　　{temp=a[i]: a[i]=a[right]; a[right]=temp;}

　　quicksort(a,left,i-1); //递归排序左子区间

　　quicksort(a,i+1,right); //递归排序右子区间

　　}

　　}

　　(1) 用C或Pascal实现三者取中子程序 median3(a,left,right); (5分)

　　(2) 改写 quicksort 算法, 不用栈消去第二个递归调用 quicksort(a,i+1,right); (5分)

　　(3) 继续改写 quicksort 算法, 用栈消去剩下的递归调用. (5分)