数据结构

编写程序以创建具有最小高度的二进制排序树，以用于关键字的有序序列. 并判断一个序列是否是二叉排序树中的合法搜索序列

#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
	int data;
	struct node *lchild,*rchild;
} BSTNode;
int *A;    //全局变量A
BSTNode* CreateBST(int low,int high)  //用关键字序列创建高度最小的二叉排序树,low,high初值为序列中最小数与最大数下标
{                           //这里的关键字序列为int数组，为节省内存使用全局变量
	int mid = (low+high)/2;
	BSTNode *root;
	if(low<=high)
	{
		root = (BSTNode*)malloc(sizeof(BSTNode));
		root->data=A[mid];
		root->lchild=CreateBST(low,mid-1);
		root->rchild=CreateBST(mid+1,high);
		return root;
	}
	else
		return NULL;
}
BSTNode* SearchBST(BSTNode* bt,int k)   //在二叉排序树中查找k
{
	if(bt==NULL || bt->data==k)
		return bt;
	if(k < bt->data)
		return SearchBST(bt->lchild,k);
	else
		return SearchBST(bt->rchild,k);
}
bool SearchSortBST(BSTNode* bt,int *B,int lenth)  //在二叉排序树中查找序列，检测序列是否是合法的查找序列
{
	bool T;
	int i;
	for(i=0;i<lenth;i++)
		if(SearchBST(bt,B[i])==NULL)  //若序列中有一个数不存在
			return 0;                 //则返回假
	return 1;                         //若序列中数都存在，返回真
}
void BubbleSort (int *A,int lenth)  //冒泡排序
{
	int T,i,j,mid;
	for(i=0;i<lenth-1;i++)     //lenth个数字做lenth-1次循环
	{
		for(j=0;j<lenth-i-1;j++)
		{
			T=1;
			if(A[j]>A[j+1])    //大的数放后面,做交换
			{
				T=0;
				mid=A[j];
				A[j]=A[j+1];
				A[j+1]=mid;
			}
		}
		if(T)    //T==1表示数列已为有序序列，无需再进行后面操作
			break;
	}
}
int Input(int *&A)
{
	int count=0;
	printf("请输入一个整数序列：(输入-100结束)\n");
	A=(int*)malloc(sizeof(int));
	do                         //动态数组输入(内存足够则不受数组长度影响)
	{
		printf("第%d个整数：",count);
		scanf("%d",&A[count++]);
		A=(int*)realloc(A,(count+1)*sizeof(int));
	}while(A[count-1]!=-100);
	return count-1;            //count即是int序列长+1，也是数组长,这里返回count-1,即序列长。
}
void disp(BSTNode *b)
{
	if(b!=NULL)
	{
		printf("%d", b->data);
		if(b->lchild!=NULL||b->rchild!=NULL)
		{
			printf("(");
			disp(b->lchild);
			if (b->rchild != NULL) printf(",");
			disp(b->rchild);
			printf(")");
		}
	}
}
int main ()
{
	int lenthA,lenthB,i,*B;
	BSTNode* bt;
	lenthA=Input(A);          //A为int*全局变量
	BubbleSort(A,lenthA);     //将输入的A数组排序
	bt=CreateBST(0,lenthA-1); //由数组(int序列)创建二叉排序树lenth-1为序列中最大数的下标,即序列长-1
	disp(bt);
	printf("\n");printf("请输入待判断序列");
	lenthB=Input(B);          //输入B数组元素
	if(SearchSortBST(bt,B,lenthB))
		printf("该序列在二叉排序树中合法！");
	else
		printf("该序列在二叉排序树中非法！");
}

原始作者: 二进制搜索树

原始地址:

本文是从文章中转载的. 本文仅转载以共享知识. 如果有任何侵权判断 二叉排序树判断 二叉排序树，请联系博客以将其删除.

二叉搜索树气泡排序算法

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-190836-1.html