利用二叉排序树对顺序表排序

Question

只知道二叉链表来排序，顺序表不知道，求大神的代码

 

Answer 1

#include <stdio.h>
#include <stdlib.h>
/*#define EQ(a,b) ((a)==(b)) //对数值型关键字比较
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)>(b))*/
typedef int KeyType;
//块内结构
typedef struct RecType{
    KeyType key;
}RecType;
//索引表结构
typedef struct index{
    KeyType maxkey; //块中最大的关键字
    int startpos; //块的起始位置指针
}Index;
//二叉排序树的结点定义
typedef struct Node{
    KeyType key;
    struct Node *Lchild, *Rchild;
}BSTNode;
//二叉排序树的递归查找
BSTNode *BST_Search(BSTNode *T, KeyType key){
    if(T == NULL){
        printf("查找失败");
         return NULL;
    }
 
 
    if(T->key == key){
 
        return T;
    }
 
    else if(T->key < key)
        return (BST_Search(T->Rchild, key));
    else
        return (BST_Search(T->Lchild, key));
 
}
//非递归
 BSTNode *BST_Search1(BSTNode *T, KeyType key){
   // BSTNode *p; p = T;
    while(T != NULL && T->key != key){
        if(key > T->key)
            T= T->Rchild;
        else
            T = T->Lchild;
    }
    if(T->key == key)
        return T;
    else
        return NULL;
 }
//索引顺序查找（分块查找）
int Block_search(RecType ST[], Index ind[], KeyType key, int n, int b){
    //在分块索引表中查找关键字为key的记录
    //表长为N， 块数为b
 
    int i = 1, j;
    //找块
    while((i <= b) && ind[i].maxkey < key){
        i++;
    }
  //  printf("\n i = %d ", i);
    if(i > b){
        printf("没找见1\n");
        return 0;
    }
    //块内找
    j = ind[i].startpos;
 //   printf("\nj = %d", j);
    while((j <= n) && ST[j].key < ind[i].maxkey){
        if(ST[j].key == key)
            break;
        j++;
    }
    if(j > n||ST[j].key != key){
        j = 0;
        printf("没找见2\n");
    }
    return j;
}
 
//建立ercha排序树
BSTNode *Create_BST(){
    int ch;
    BSTNode *b;
   // printf("先序输入二叉排序树：\n");
    scanf(" %d", &ch);
    if(ch == 0){
        b = NULL;
    }else{
        b = (BSTNode *)malloc(sizeof(BSTNode));
        b->key = ch;
        b->Lchild = Create_BST();
        b->Rchild = Create_BST();
 
    }
    return b;
 
 
}/*
void PerOrderTraverse(BSTNode *bt)
{
    if(bt!=NULL)
   { printf("%d",bt->key);
     PerOrderTraverse(bt->Lchild);
     PerOrderTraverse(bt->Rchild);
   }
}*/
int main()
{
    int b, n, i, m, j;
   /* printf("-----------索引顺序表查找----------\n");
    printf("输入索引表的长度:");
    scanf("%d", &b);
    printf("输入块的大小：");
    scanf("%d", &n);
    RecType ST[n*b];
    Index ind[b];
    printf("建立索引表：\n");
    for(i = 1; i <= b; i++){
        printf("输入索引表的第%d块的最大值：", i);
        scanf("%d", &m);
        ind[i].maxkey = m;
    }
    int a = 1;
    printf("建立块:\n");
    for(i = 1; i <= b; i++){
        ind[i].startpos = a;
        for(j = 0; j < n; j++){
            printf("输入第%d块的第%d个值:", i, j+1);
            scanf("%d", &m);
            ST[a].key = m;
            a++;
        }
    }
    printf("打印索引表：\n");
    for(i = 1; i <= b; i++){
        printf("%d ", ind[i].maxkey);
        printf("%d  \n", ind[i].startpos);
    }
    printf("打印顺序表\n");
    for(i = 1; i <= n*b; i++){
        printf("%d  ", ST[i].key);
    }
    printf("\n");
    printf("输入要查找的值：\n");
    scanf("%d", &m);
    printf("地址为：%d", Block_search(ST, ind, m, n*b, b));*/
    printf("\n\n---------二叉排序树的查找----------\n");
    BSTNode *T;
    BSTNode *p;
    T = Create_BST();
    printf("以%d为根的树创建成功！\n",T->key);
    //PerOrderTraverse(T);
    printf("输入要查找的值：\n");
    scanf("%d", &m);
    printf("递归查找：");
    p = BST_Search(T, m);
    printf("找到了 它的值为%d",p->key);
    if(p->Lchild != NULL)
        printf("左孩子为%d",p->Lchild->key);
    else
        printf("左孩子为空");
    if(p->Rchild != NULL)
        printf("右孩子为%d\n",p->Rchild->key);
    else
        printf("右孩子为空\n");
    // printf("%d \n", p->key);
    printf("非递归查找：");
    p =BST_Search1(T, m);
    printf("找到了 它的值为%d",p->key);
    if(p->Lchild != NULL)
        printf("左孩子为%d",p->Lchild->key);
    else
        printf("左孩子为空");
    if(p->Rchild != NULL)
        printf("右孩子为%d",p->Rchild->key);
    else
        printf("右孩子为空");
 
  return 0;
}

如果对你有帮助，可以点击我这个回答右上方的【采纳】按钮，给我个采纳吗，谢谢