CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章C语言二叉排序树的创建,插入和删除由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

1、二叉排序树（二叉查找树）的概念

（1）若左子树非空，则左子树上所有结点的值均小于根节点的值 。

（2）若右子树非空，则右子树上所有结点的值均大于根节点的值 。

（3）左右子树分别也是一棵二叉排序树 。

tip：可以是一棵空树 。

  。

2、二叉排序树的判别

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

  。

3、二叉排序树的创建（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);	}}

  。

4、二叉排序树的插入

//查找指定结点(输出当前结点是否存在)，如果没有就插入 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;	}}

  。

5、二插排序树的删除

//删除某一结点，若不存在则提示//①当该结点是叶子结点时，直接删除//②当该结点有一个左孩子或者一个右孩子时，让其孩子结点代替他的位置//③当左右孩子都存在时找中序遍历的下一个(或上一个)结点代替其位置 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;		 } }

  。

6、完整代码（可以运行）

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

  。

总结

本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注我的更多内容！ 。

原文链接：https://blog.csdn.net/qq_48071481/article/details/120837025 。

最后此篇关于C语言二叉排序树的创建,插入和删除的文章就讲到这里了,如果你想了解更多关于C语言二叉排序树的创建,插入和删除的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。