数据结构实训作业(IV)
于2020年11月2日2020年11月2日由Sukuna发布
二叉搜索树和排序的一些问题
第一题:判断是不是二叉排序树?
代码语言：javascript复制status JudgeBiTree(BiTree T)
//判断二叉树T是否为二叉排序树
{
// 请在这里补充代码，完成本关任务
/********** Begin *********/
struct BiTNode * St[100], *p;
int top = 0; //置空栈
if(T){
St[top ] = T;
while(top){
p = St[--top];
if(p->rchild != NULL){
St[top ] = p->rchild;
if(p->data.key>p->rchild->data.key) return NO;
}
if(p->lchild != NULL){
St[top ] = p->lchild;
if(p->data.key<p->lchild->data.key) return NO;
}
}
}
return YES;
/********** End **********/
}前序遍历的非递归实现,每一次访问结点的时候就判断一下是不是满足二叉搜索树的条件,如果能成功安全退出,那就是搜索树了
第二题:线性时间复杂度的排序
想到了计数排序,开个新数组存就完事了
代码语言：javascript复制void sort(int a[],int n,int k)
//将a中元素递增排序
{
// 请在这里补充代码，完成本关任务
/********** Begin *********/
int c[100]={0};
int ranked[100]={0};
for (int i = 0; i < n ; i ){
c[a[i]] ;
}
for (int i = 1; i < k 1; i)
c[i] = c[i-1];
for (int i = n-1; i >= 0; --i)
ranked[--c[a[i]]] = a[i];
for (int i = 0; i < n; i ){
a[i]=ranked[i];
}
/********** End **********/
}第二题:查找中位数
快速排序
代码语言：javascript复制void swap (int *a,int *b){
int temp;
temp=*a;
*a=*b;
*b=temp;
}
int partition(int L[],int low,int high)
{
int i,num=low;
for(i=low 1;i<=high;i )
{
if(L[i]<L[low])
{
swap(&L[i],&L[num 1]);
num ;
}
}
swap(&L[low],&L[num]);
return num;
}
int MidValue(int a[],int n)
//求a的中位数
{
// 请在这里补充代码，完成本关任务
/********** Begin *********/
int low=0,high=n-1,pos;
int mid=n/2;
while(1){
pos=partition(a,low,high);
if(pos==mid)
break;
else if(pos>mid)
high=pos-1;
else low=pos 1;
}
if(n%2) return a[mid];
else return (a[mid] a[mid-1])/2;
/********** End **********/
}如果是偶数,怎么样怎么样,如果是奇数,怎么样怎么样……
