您现在的位置是:群英 > 开发技术 > 编程语言
C语言二叉排序树是什么,如何创建和操作?
Admin发表于 2021-12-24 18:02:221002 次浏览

    这篇文章我们来了解C语言二叉排序树的相关内容,下文将介绍二叉排序树(二叉查找树)的概念、二叉排序树的判别、二叉排序树的创建、插入、删除等内容,对大家学习和理解二叉排序树有一定的帮助,有需要的朋友可以参考,接下来就跟随小编来一起学习一下吧!

一、二叉排序树(二叉查找树)的概念

    (1)若左子树非空,则左子树上所有结点的值均小于根节点的值

    (2)若右子树非空,则右子树上所有结点的值均大于根节点的值

    (3)左右子树分别也是一棵二叉排序树

    tip:可以是一棵空树

二、二叉排序树的判别

    (1)因为二叉排序树的中序遍历是一个有序递增序列,可以对已经建立的二叉树进行中序遍历,如果满足则判断是

三、二叉排序树的创建(creat、insert)

    树结点的结构体:

struct tree{
int data;
struct tree* lchild;
struct tree* rchild;
};

//递归创建结点
void Creat(int a,tree* &T){
	if(T==NULL){
		T=new tree;
		T->data=a;
		T->lchild=NULL;
		T->rchild=NULL;
	}
	else if(a>T->data){
		Creat(a,T->rchild);
	}
	else{
		Creat(a,T->lchild);
	}
} 
//传入数组,一次性插入 
void Insert(tree* &T,int A[],int len){
	for(int i=0;i<=len;i++){
		Creat(A[i],T);
	}
}

四、二叉排序树的插入

//查找指定结点(输出当前结点是否存在),如果没有就插入 
void find(tree* &T,int a){
	tree* K=T;     //T指针指向二叉排序树的根节点,K为工作指针 
	tree* pre;	   //pre指向当前工作指针的上一个结点,用于插入确定插入位置	 
	while(K!=NULL&&a!=K->data){
		if(a>K->data){
			pre=K;
			K=K->rchild;
		}else{
			pre=K;
			K=K->lchild;
		}
	}
	if(K==NULL){
		tree* P;    //工作指针
		P=new tree;
		P->data=a;
		if(P->data>pre->data){
			pre->rchild=P;
			P->lchild=NULL;
			P->rchild=NULL;
		}
		else{
		    pre->lchild=P;
			P->lchild=NULL;
			P->rchild=NULL;
		}
		cout<<"不存在,已插入 "<<a<<" 这个结点"<<endl;
	}else{
		cout<<"存在"<<endl;
	}
}

五、二插排序树的删除

//删除某一结点,若不存在则提示
//①当该结点是叶子结点时,直接删除
//②当该结点有一个左孩子或者一个右孩子时,让其孩子结点代替他的位置
//③当左右孩子都存在时找中序遍历的下一个(或上一个)结点代替其位置 
void delect(tree* &T,int a){
	 //首先找到要删除的结点
	 tree* Pre;
	 tree* P=T;                      //定义工作指针 
	 while(P!=NULL&&a!=P->data){     //这两个判定条件不能颠倒 
	 	if(a>P->data){
	 		Pre=P;
	 		P=P->rchild;
		 }else{
		 	Pre=P;
		 	P=P->lchild;
 		} 
} 
  	 if(P==NULL){
	 	cout<<"要删除的结点不存在"<<endl;
	 }else{
	 	// ①当该结点是叶子结点时,直接删除
	 	if(P->lchild==NULL&&P->rchild==NULL){
	 		if(P->data>Pre->data){
	 			Pre->rchild=NULL;
			 }else{
			 	Pre->lchild=NULL;
			 }
			 cout<<"已删除 "<<a<<endl; 
		 }
		 //②当该结点有一个左孩子或者一个右孩子时,让其孩子结点代替他的位置
		 if((P->lchild!=NULL&&P->rchild==NULL)||(P->rchild!=NULL&&P->lchild==NULL)){
		 	if(P->data>Pre->data){
		 		if(P->lchild!=NULL){
		 			Pre->rchild=P->lchild;
				 }else{
				 	Pre->rchild=P->rchild;
				 }
			 }
			 if(P->data<Pre->data){
			 	if(P->lchild!=NULL){
			 		Pre->lchild=P->lchild;
				 }else{
				 	Pre->lchild=P->rchild;
				 }
			 }
			 cout<<"已删除 "<<a<<endl; 
		 }
		 //③当左右孩子都存在时找中序遍历的下一个(或上一个结点)结点代替其位置 (讨巧一点用前驱的最后一个结点)
		 if(P->lchild!=NULL&&P->rchild!=NULL){
	        tree* q;
	        tree* s;
            q=P;
            s=P->lchild; 
		    while(s->rchild)        //在结点p的左子树中继续查找其前驱结点,即最右下结点 
		    {
	           q=s;
			   s=s->rchild;       //向右到尽头 
		    }
		 	P->data=s->data;      //结点s中的数据顶替被删结点p中的 
		    if(q!=P)              //重新连接结点q的右子树 
			q->rchild=s->lchild;
			else                    //重新连接结点q的左子树 
			q->lchild=s->lchild;
			delete(s);              //释放s 
			  }
	        cout<<"已删除 "<<a<<endl;
		 } 
}

六、完整代码(可以运行)

#include<iostream>
using namespace std;
struct tree{
	int data;
	struct tree* lchild;
	struct tree* rchild;
};
//建立创建,传入一个完整的数组 
void Creat(int a,tree* &T){
	if(T==NULL){
		T=new tree;
		T->data=a;
		T->lchild=NULL;
		T->rchild=NULL;
	}
	else if(a>T->data){
		Creat(a,T->rchild);
	}
	else{
		Creat(a,T->lchild);
	}
} 
//传入数组,一次性插入 
void Insert(tree* &T,int A[],int len){
	for(int i=0;i<=len;i++){
		Creat(A[i],T);
	}
}
//中序遍历 
void midorder(tree* T){
	if(T!=NULL){
	    midorder(T->lchild);
		cout<<T->data<<" ";
		midorder(T->rchild);
	}
}
//查找指定结点(输出当前结点是否存在),如果没有就插入 
void find(tree* &T,int a){
	tree* K=T;     //T指针指向二叉排序树的根节点,K为工作指针 
	tree* pre;	   //pre指向当前工作指针的上一个结点,用于插入确定插入位置	 
	while(K!=NULL&&a!=K->data){
		if(a>K->data){
			pre=K;
			K=K->rchild;
		}else{
			pre=K;
			K=K->lchild;
		}
	}
	if(K==NULL){
		tree* P;    //工作指针
		P=new tree;
		P->data=a;
		if(P->data>pre->data){
			pre->rchild=P;
			P->lchild=NULL;
			P->rchild=NULL;
		}
		else{
		    pre->lchild=P;
			P->lchild=NULL;
			P->rchild=NULL;
		}
		cout<<"不存在,已插入 "<<a<<" 这个结点"<<endl;
	}else{
		cout<<"存在"<<endl;
	}
}
//删除某一结点,若不存在则提示
//①当该结点是叶子结点时,直接删除
//②当该结点有一个左孩子或者一个右孩子时,让其孩子结点代替他的位置
//③当左右孩子都存在时找中序遍历的下一个(或上一个)结点代替其位置 
void delect(tree* &T,int a){
	 //首先找到要删除的结点
	 tree* Pre;
	 tree* P=T;                      //定义工作指针 
	 while(P!=NULL&&a!=P->data){     //这两个判定条件不能颠倒 
	 	if(a>P->data){
	 		Pre=P;
	 		P=P->rchild;
		 }else{
		 	Pre=P;
		 	P=P->lchild;
 		} 
} 
  	 if(P==NULL){
	 	cout<<"要删除的结点不存在"<<endl;
	 }else{
	 	// ①当该结点是叶子结点时,直接删除
	 	if(P->lchild==NULL&&P->rchild==NULL){
	 		if(P->data>Pre->data){
	 			Pre->rchild=NULL;
			 }else{
			 	Pre->lchild=NULL;
			 }
			 cout<<"已删除 "<<a<<endl; 
		 }
		 //②当该结点有一个左孩子或者一个右孩子时,让其孩子结点代替他的位置
		 if((P->lchild!=NULL&&P->rchild==NULL)||(P->rchild!=NULL&&P->lchild==NULL)){
		 	if(P->data>Pre->data){
		 		if(P->lchild!=NULL){
		 			Pre->rchild=P->lchild;
				 }else{
				 	Pre->rchild=P->rchild;
				 }
			 }
			 if(P->data<Pre->data){
			 	if(P->lchild!=NULL){
			 		Pre->lchild=P->lchild;
				 }else{
				 	Pre->lchild=P->rchild;
				 }
			 }
			 cout<<"已删除 "<<a<<endl; 
		 }
		 //③当左右孩子都存在时找中序遍历的下一个(或上一个结点)结点代替其位置 (讨巧一点用前驱的最后一个结点)
		 if(P->lchild!=NULL&&P->rchild!=NULL){
	        tree* q;
	        tree* s;
            q=P;
            s=P->lchild; 
		    while(s->rchild)        //在结点p的左子树中继续查找其前驱结点,即最右下结点 
		    {
	           q=s;
			   s=s->rchild;       //向右到尽头 
		    }
		 	P->data=s->data;      //结点s中的数据顶替被删结点p中的 
		    if(q!=P)              //重新连接结点q的右子树 
			q->rchild=s->lchild;
			else                    //重新连接结点q的左子树 
			q->lchild=s->lchild;
			delete(s);              //释放s 
			  }
	        cout<<"已删除 "<<a<<endl;
		 } 
}
int main(){
	tree* T=NULL;
	int A[]={23,89,65,12,17,3,9,90,21,63,71};
	Insert(T,A,10);
	midorder(T);
	delect(T,89);
	midorder(T);
	find(T,89);
	midorder(T); 
	return 0;
}

总结

    关于c语言二叉排序树创建及一些操作方法就介绍到这,上述示例具有一定的借鉴价值,感兴趣的朋友可以参考,希望能对大家和理解c语言二叉排序树有帮助,想要了解更多c语言的内容,大家可以关注其它的相关文章。

文本转载自脚本之家

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:mmqy2019@163.com进行举报,并提供相关证据,查实之后,将立刻删除涉嫌侵权内容。

相关信息推荐
2022-12-09 17:50:20 
摘要:在php中,关联数组是值以字符串或字符串、数字混合为键名的数组;如果一个数组中有一个键名不是数字,那么这个数组就是关联数组。关联数组的键名可以是任何一个整数或字符串;如果键名是一个字符串,则要给这个键名加上一个定界修饰符:单引号“''”或双引号“""”。
2022-05-28 17:06:55 
摘要:java中文乱码的转换方法:首先用编辑器编写java源文件;然后使用【javac.exe】编译java文件,并使用JDK将编译好的且保存在内存中信息写入class文件中;最后运行编译类。
2022-05-20 17:27:54 
摘要:下面由go语言​教程栏目给大家介绍关于go 闭包的学习使用,希望对需要的朋友有所帮助!
云活动
推荐内容
热门关键词
热门信息
群英网络助力开启安全的云计算之旅
立即注册,领取新人大礼包
  • 联系我们
  • 24小时售后:4006784567
  • 24小时TEL :0668-2555666
  • 售前咨询TEL:400-678-4567

  • 官方微信

    官方微信
Copyright  ©  QY  Network  Company  Ltd. All  Rights  Reserved. 2003-2019  群英网络  版权所有   茂名市群英网络有限公司
增值电信经营许可证 : B1.B2-20140078   粤ICP备09006778号
免费拨打  400-678-4567
免费拨打  400-678-4567 免费拨打 400-678-4567 或 0668-2555555
微信公众号
返回顶部
返回顶部 返回顶部