50分求关于数据结构3个题目：1：6、9、3、1、8、9、5、11画出二叉树,写出前中后三序的结果.2：24、15、6、9、72、5、3写出它的快速排序,希尔排序及二分查找的相应算法.3：写出

Question

50分求关于数据结构3个题目：【1】：6、9、3、1、8、9、5、11画出二叉树,写出前中后三序的结果.
【2】：24、15、6、9、72、5、3写出它的快速排序,希尔排序及二分查找的相应算法.
【3】：写出单链表、栈队列的相关指针及判断空满的必要条件.

Answer 1

1】
二叉树：6、9、3、1、8、9、5、11
\x09\x096
\x09 /\x09 \
\x099\x09\x093
/ \ / \
1\x09 8 9 5
/
11
1,前序：6、9,1,11,8,3,9,5
2,中序：11、1,9,8,6,9,3,5
3,后序：11、1,8,9,9,5,3,6
2】,
\x091,快速排序算法：
它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一不部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列.
假设要排序的数组是A[1]……A[N],首先任意选取一个数据（通常选用第一个数据）作为关键数据,然后将所有比它的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一躺快速排序.一躺快速排序的算法是：
1）、设置两个变量I、J,排序开始的时候I：=1,J：=N；
2）以第一个数组元素作为关键数据,赋值给X,即X：=A[1]；
3）、从J开始向前搜索,即由后开始向前搜索（J：=J-1）,找到第一个小于X的值,两者交换；
4）、从I开始向后搜索,即由前开始向后搜索（I：=I+1）,找到第一个大于X的值,两者交换；
5）、重复第3、4步,直到I=J；
算法实现：
int sort_t(int a[],int top,int tall)
{
\x09int temp=a[top];
\x09while(top= temp && top < tall)
\x09\x09\x09--tall;
\x09\x09a[top]=a[tall];
\x09\x09while(a[top]top)
\x09\x09\x09++top;
\x09\x09a[tall]=a[top];
\x09}
\x09a[top]=temp;
\x09return top;
}
void sort(int a[],int top,int tall)
{
\x09if(top>=tall)
\x09\x09return;
\x09int middle=sort_t(a,top,tall);
\x09sort(a,top,middle-1);
\x09sort(a,middle+1,tall);
}
\x092,希尔排序
基本思想：
先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组.所有距离为dl的倍数的记录放在同一个组中.先在各组内进行直接插人排序；然后,取第二个增量d2