将一组读入的整数构成一棵二叉排序树，并对任一整数进行查找

将一组读入的整数构成一棵二叉排序树，并对任一整数进行查找

利用C语言编程写出来！数据结构考试要用！唉！

#include <stdio.h>
#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;
};

elemType* findBSTree1(struct BTreeNode* bst,elemType x)
{

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;
}


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;
}
}

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;
}

void createBSTree(struct BTreeNode**bst,elemType a[],int n)
{
int i;
*bst=NULL;
for(i=0;i<n;i++){
insertBSTree1(bst,a[i]);
}
return;
}


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;
}

void clearBTree(struct BTreeNode* *bt)
{
if(*bt != NULL){
clearBTree(&((*bt)->left));
clearBTree(&((*bt)->right));
free(*bt);
*bt = NULL;
}
return;
}

void preOrder(struct BTreeNode *bt)
{
if(bt != NULL){
printf("%d ", bt->data);
preOrder(bt->left);
preOrder(bt->right);
}
return;
}

void inOrder(struct BTreeNode *bt)
{
if(bt != NULL){
inOrder(bt->left);
printf("%d ", bt->data);
inOrder(bt->right);
}
return;
}

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;
}

#include"stdio.h" #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"); }