m0_52685494 2021-06-28 10:05 采纳率: 50%

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

• 写回答

#### 1条回答默认 最新

• CSDN专家-黄老师 2021-06-28 10:06
关注
``````#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;
}``````

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

本回答被题主选为最佳回答 , 对您是否有帮助呢?
评论

#### 悬赏问题

• ¥20 C语言字符串不区分大小写字典排序相关问题
• ¥15 关于#python#的问题：我希望通过逆向技术爬取1688搜索页下滑加载的数据
• ¥15 学习C++过程中遇到的问题
• ¥15 关于Linux的终端里，模拟实现一个带口令保护的屏保程序遇到的输入输出的问题！(语言-c语言)
• ¥15 学习C++过程中遇到的问题
• ¥15 请问，这个嵌入式Linux系统怎么分析，crc检验区域在哪
• ¥15 二分类改为多分类问题