当前位置:   article > 正文

C语言实现二叉排序树_c语言建立二叉排序树

c语言建立二叉排序树

1.二叉排序树的定义

二叉排序树,又称二叉查找数树,一颗二叉树或者是空二叉树,或者是具有如下性质的二叉树:
a.左子树上所有结点的关键字均小于根结点的关键字;
b.右子树上所有结点的关键字竣大雨根结点的关键字。
c.左子树和右子树又各是一颗二叉排序树。
——>左子树结点值<根结点值<右子树结点值
进行中序遍历,可以得到一个递增的有序遍历
代码如下:

//二叉排序树结点
typedef struct BSTNode{
	int key;
	struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;
//在二叉排序树中查找值为key的结点
BSTNode *BST_Search(BSTree T, int key){
	while(T!=NULL&&key!=T->key){	//若树空或等于根结点值,则结束循环
		if(key<T->key) T=T->lchild;	//小于,则在左子树上查找
		else T=T->rchild;			//大于,则在右子树上查找
	}
	return T;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

2.二叉排序树的查找

若树非空,目标值与跟结点比较:
a.若相等,则查找成功
b.若小于跟结点,则在左子树上查找,否则在右子树上查找。
c.查找成功,返回结点指针:查找失败返回NULL
代码如下:

//二叉排序树结点
typedef struct BSTNode{
		int key;
		struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;
//在二叉排序树中序寻找值为key的结点(非递归)
BSTNode *BST_Search(BSTree T, int key){
	while(T!=NULL&&key!=T->key){		//若树空或等于根结点值,则结束循环
		if(key<T->key) T=T->lchild;		//小于,则在左子树上查找
		else T=T->rchild;				//大于,则在右子树上查找
	}
	return T;
}
//在二叉排序树中查找值为key的结点(递归)
BSTNode *BSTSearch(BSTree T, int key){
	if(T==NULL)
		return NULL;
	if(key==T->key)
		return T;
	else if(key<T->key)
		return BSTSearch(T->lchild, key);	//在左子树中找
	else 	
		return BSTsearch(T->rchild, key); 	//在右子树中找
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

3.二叉排序树的插入

若二叉排序树为空,则直接插入结点;否则,若关键字k小雨根结点值,则插入到左子树,若关键字k大于根结点值,则插入到右子树
代码如下:

//在二叉排序树插入关键字为k的新结点(递归实现)最坏空间复杂度为O(h)
int BST_Insert(BSTree &T, int k){
	If(T==NULL){
		T=(BSTree)malloc(sizeof(BSTNode));
		T->key=k;
		T->lchild=T->rchild=NULL;
		return 1;			//返回1,插入成功
	}
	else if(k==T->key)		//树中存在相同关键字的结点,插入失败
		return 0;
	else if(k<T->key)		//插入到T的左子树
		return BST_Insert(T->lchild, k);
	else 					//插入到T的右子树
		return BST_insert(T->rcild, k);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

4.二叉排序树的构造

//按照str[]中的关键字序列建立二叉排序树
void Creat_BST(BSTree &T, int str[], int n){
	T=NULL;					//初始时T为空树
	int i=0;
	while(i<n){				//依此将每个关键字插入到二叉排序树中
		BST_Insert(T,str[i];
		i++;
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

结论:
不同的关键字序列可能得到同款二叉排序树,也可能得到不同款二叉排序树

5.二叉排序树的删除

先搜索目标结点:
a.若被删除结点z是叶结点,则直接删除,不会破坏二叉排序树的性质
b.若结点z只有一个左子树或右子树,则让z的子树成为z父结点的子树,替代z的位置
c.若结点z有左、右两棵子树,则令z的直接后继(或直接前驱)替代z,然后从二叉排序树中删去这个直接后继(或直接前驱),这样就转换成了第一或第二种情况。
z的后继:z的右子树最左下结点(该结点一定没有左子树)
z的前驱:z的左子树最右下结点(该结点一定没有右子树)

6.查找 效率分析

查找长度—-在查找运算中,需要对比关键字的次数称为查找长度,反映了查找操作时间复杂度。
平衡二叉树:树上任一结点的左子树和右子树的深度之差不超过1。
n个结点的二叉树最小高度为⌊log2 n⌋+1(完全二叉树)而平衡二叉树高度与完全二叉树同等数量级。
总结:查找效率取决于树的高度,最好O(log2n),最坏O(n),查找失败的情况(需补充失败结点)

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/IT小白/article/detail/709602
推荐阅读
相关标签
  

闽ICP备14008679号