将一组读入的整数构成一棵二叉排序树,并对任一整数进行查找
发布网友
发布时间：2023-08-07 13:01
共2个回答
热心网友
时间：2023-09-14 05:59
#include"stdlib.h"
#include "string.h"
#define Max 100 //假设文件长度
typedef struct{ //定义记录类型
int key; //关键字项
}RecType;
typedef RecType SeqList[Max+1]; //SeqList为顺序表，表中第0个元素作为哨兵
int n; //顺序表实际的长度//在排序的过程中，将R[1‥n]看成是一个完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）的记录。即：把待排序文件的关键字存放在数组R[1‥n]子中，将R看成是一棵二叉树，每个结点表示一个记录，源文件的第一个记录R[1]作为二叉树的根，以下各记录R[2‥n]依次逐层从左到右排列，构成一棵完全二叉树，任意结点R[i]的左孩子是R[2i]，右孩子是R[2i+1]，双亲是R[i/2]。对这棵完全二叉树的结点进行调整，使各结点的关键字满足下列条件：
//R[i].key≤R[2i].key并且R[i].key≤R[2i+1].key 称小堆根
//或 R[i].key≥R[2i].key并且R[i].key≥R[2i+1].key 称大堆根
//==========大根堆调整函数=======
void Heapify(SeqList R,int low,int high)
{ // 将R[low..high]调整为大根堆，除R[low]外，其余结点均满足堆性质
int large; //large指向调整结点的左、右孩子结点中关键字较大者
RecType temp=R[low]; //暂存调整结点
for(large=2*low; large<=high;large*=2){ //R[low]是当前调整结点
//若large>high,则表示R[low]是叶子，调整结束；否则先令large指向R[low]的左孩子
if(large<high && R[large].key<R[large+1].key)
large++; //若R[low]的右孩子存在且关键字大于左兄弟，则令large指向它
//现在R[large]是调整结点R[low]的左右孩子结点中关键字较大者
if(temp.key>=R[large].key) //temp始终对应R[low]
break; //当前调整结点不小于其孩子结点的关键字，结束调整
R[low]=R[large]; //相当于交换了R[low]和R[large]
low=large; //令low指向新的调整结点，相当于temp已筛下到large的位置
}
R[low]=temp; //将被调整结点放入最终位置上
}
//==========构造大根堆==========
void BuildHeap(SeqList R)
{ //将初始文件R[1..n]构造为堆
int i;
for(i=n/2;i>0;i--)
Heapify(R,i,n); //将R[i..n]调整为大根堆
}
//==========堆排序===========
void HeapSort(SeqList R)
{ //对R[1..n]进行堆排序，不妨用R[0]做暂存单元
int i;
BuildHeap(R); //将R[1..n]构造为初始大根堆
for(i=n;i>1;i--){ //对当前无序区R[1..i]进行堆排序，共做n-1趟。
R[0]=R[1]; R[1]=R[i];R[i]=R[0]; //将堆顶和堆中最后一个记录交换
Heapify(R,1,i-1); //将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质。
}
}
//==========输入顺序表========
void input_int(SeqList R)
{
int i;
printf("Please input num(int):");
scanf("%d",&n);
printf("Plase input %d integer:",n);
for(i=1;i<=n;i++)
scanf("%d",&R[i].key);
}
//==========输出顺序表========
void output_int(SeqList R)
{
int i;
for(i=1;i<=n;i++)
printf("%4d",R[i].key);
}
//==========主函数======
void main()
{
SeqList R;
input_int(R);
HeapSort(R);
printf("HeapSort reult:");
output_int(R);
printf("\n");
}
热心网友
时间：2023-09-14 05:59
#include <stdlib.h>
#define STACK_MAX_SIZE 30
#define QUEUE_MAX_SIZE 30
#ifndef elemType
typedef int elemType;
#endif struct BTreeNode{
elemType data;
struct BTreeNode *left;
struct BTreeNode *right;
}; /*1.查找*/
/*递归算法*/
elemType* findBSTree1(struct BTreeNode* bst,elemType x)
{
/*树为空则返回NULL*/
if(bst==NULL){
return NULL;
}else{
if(x==bst->data){
return &(bst->data);
}else{
if(x<bst->data){/*向左子树查找并直接返回*/
return findBSTree1(bst->left,x);
}else{/*向右子树查找并直接返回*/
return findBSTree1(bst->right,x);
}
}
}
}
/*非递归算法*/
elemType* findBSTree2(struct BTreeNode*bst,elemType x)
{
while(bst!=NULL){
if(x==bst->data){
return&(bst->data);
}else if(x<bst->data){
bst=bst->left;
}else{
bst=bst->right;
}
}
return NULL;
}
/*2.插入*/
/*递归算法*/
void insertBSTree1(struct BTreeNode**bst,elemType x)
{
/*新建一个根结点*/
if(*bst==NULL){
struct BTreeNode*p=(struct BTreeNode*)malloc(sizeof(struct BTreeNode));
p->data=x;
p->left=p->right=NULL;
*bst=p;
return;
}else if(x<(*bst)->data){/*向左子树完成插入运算*/
insertBSTree1(&((*bst)->left),x);
}else{/*向右子树完成插入运算*/
insertBSTree1(&((*bst)->right),x);
}
}
/*非递归算法*/
void insertBSTree2(struct BTreeNode**bst,elemType x)
{
struct BTreeNode*p;
struct BTreeNode*t=*bst,*parent=NULL;
/*为待插入的元素查找插入位置*/
while(t!=NULL){
parent=t;
if(x<t->data){
t=t->left;
}else{
t=t->right;
}
}
/*建立值为x，左右指针域为空的新结点*/
p=(struct BTreeNode*)malloc(sizeof(struct BTreeNode));
p->data=x;
p->left=p->right=NULL;
/*将新结点链接到指针为空的位置*/
if(parent==NULL){
*bst=p;/*作为根结点插入*/
}else if(x<parent->data){/*链接到左指针域*/
parent->left=p;
}else{
parent->right=p;
}
return;
}
/*3.建立*/
void createBSTree(struct BTreeNode**bst,elemType a[],int n)
{
int i;
*bst=NULL;
for(i=0;i<n;i++){
insertBSTree1(bst,a[i]);
}
return;
}
/*******************************/
/* 6.输出二叉树(前序遍历) */
void printBTree(struct BTreeNode *bt)
{
/* 树为空时结束递归，否则执行如下操作 */
if(bt != NULL){
printf("%d", bt->data);/* 输出根结点的值 */
if(bt->left != NULL || bt->right != NULL){
printf("(");
printBTree(bt->left);
if(bt->right != NULL){
printf(",");
}
printBTree(bt->right);
printf(")");
}
}
return;
}
/* 7.清除二叉树，使之变为一棵空树 */
void clearBTree(struct BTreeNode* *bt)
{
if(*bt != NULL){
clearBTree(&((*bt)->left));
clearBTree(&((*bt)->right));
free(*bt);
*bt = NULL;
}
return;
}
/* 8.前序遍历 */
void preOrder(struct BTreeNode *bt)
{
if(bt != NULL){
printf("%d ", bt->data);/* 访问根结点 */
preOrder(bt->left);/* 前序遍历左子树 */
preOrder(bt->right);/* 前序遍历右子树 */
}
return;
}
/* 9.前序遍历 */
void inOrder(struct BTreeNode *bt)
{
if(bt != NULL){
inOrder(bt->left);/* 中序遍历左子树 */
printf("%d ", bt->data);/* 访问根结点 */
inOrder(bt->right);/* 中序遍历右子树 */
}
return;
}
/* 10.后序遍历 */
void postOrder(struct BTreeNode *bt)
{
if(bt != NULL){
postOrder(bt->left);/* 后序遍历左子树 */
postOrder(bt->right);/* 后序遍历右子树 */
printf("%d ", bt->data);/* 访问根结点 */
}
return;
}
int main(int argc,char*argv[])
{
int x,*px,i=0;
elemType a[10];//={30,50,20,40,25,70,54,23,80,92};
printf("请输入一组整数（空格隔开,-1结束）：");
scanf("%d",&x);
while(x!=-1){
a[i++]=x;
scanf("%d",&x);
}
struct BTreeNode* bst=NULL;
createBSTree(&bst,a,i);
printf("建立的二叉搜索树的广义表形式为： ");
printBTree(bst);
printf(" ");
printf("\n前序遍历： ");
preOrder(bst);
printf(" ");
printf("\n中序遍历： ");
inOrder(bst);
printf(" ");
printf("\n后序遍历： ");
postOrder(bst);
printf(" ");
printf("\n输入待查找元素的值：");
scanf("%d",&x);
if(px=findBSTree1(bst,x)){
printf("\n查找成功！得到的x为：%d ",*px);
}else{
printf("\n查找失败！ ");
}
clearBTree(&bst);
system("pause");
return 0;
}
