devbox
weixin_40725706
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

二叉排序树的创建，插入和删除（C++完整代码）_建立一个四层二叉树,有排序插入删除的功能

作者：weixin_40725706 | 2024-06-12 21:17:17

赞

踩

建立一个四层二叉树,有排序插入删除的功能

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

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

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

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

tip：可以是一棵空树

二、二叉排序树的判别

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

三、二叉排序树的创建（creat、insert）

树结点的结构体：

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

  1. //递归创建结点
  2. void Creat(int a,tree* &T){
  3. 	if(T==NULL){
  4. 		T=new tree;
  5. 		T->data=a;
  6. 		T->lchild=NULL;
  7. 		T->rchild=NULL;
  8. 	}
  9. 	else if(a>T->data){
  10. 		Creat(a,T->rchild);
  11. 	}
  12. 	else{
  13. 		Creat(a,T->lchild);
  14. 	}
  15. } 
  16.  
  17. //传入数组，一次性插入 
  18. void Insert(tree* &T,int A[],int len){
  19. 	for(int i=0;i<=len;i++){
  20. 		Creat(A[i],T);
  21. 	}
  22. }

四、二叉排序树的插入

  1. //查找指定结点(输出当前结点是否存在)，如果没有就插入 
  2. void find(tree* &T,int a){
  3. 	tree* K=T;     //T指针指向二叉排序树的根节点，K为工作指针 
  4. 	tree* pre;	   //pre指向当前工作指针的上一个结点，用于插入确定插入位置	 
  5. 	while(K!=NULL&&a!=K->data){
  6. 		if(a>K->data){
  7. 			pre=K;
  8. 			K=K->rchild;
  9. 		}else{
  10. 			pre=K;
  11. 			K=K->lchild;
  12. 		}
  13. 	}
  14. 	if(K==NULL){
  15. 		tree* P;    //工作指针
  16. 		P=new tree;
  17. 		P->data=a;
  18. 		if(P->data>pre->data){
  19. 			pre->rchild=P;
  20. 			P->lchild=NULL;
  21. 			P->rchild=NULL;
  22. 		}
  23. 		else{
  24. 		    pre->lchild=P;
  25. 			P->lchild=NULL;
  26. 			P->rchild=NULL;
  27. 		}
  28. 		cout<<"不存在，已插入 "<<a<<" 这个结点"<<endl;
  29. 	}else{
  30. 		cout<<"存在"<<endl;
  31. 	}
  32. }

五、二插排序树的删除

  1. //删除某一结点，若不存在则提示
  2. //①当该结点是叶子结点时，直接删除
  3. //②当该结点有一个左孩子或者一个右孩子时，让其孩子结点代替他的位置
  4. //③当左右孩子都存在时找中序遍历的下一个(或上一个)结点代替其位置 
  5. void delect(tree* &T,int a){
  6. 	 //首先找到要删除的结点
  7. 	 tree* Pre;
  8. 	 tree* P=T;                      //定义工作指针 
  9. 	 while(P!=NULL&&a!=P->data){     //这两个判定条件不能颠倒 
  10. 	 	if(a>P->data){
  11. 	 		Pre=P;
  12. 	 		P=P->rchild;
  13. 		 }else{
  14. 		 	Pre=P;
  15. 		 	P=P->lchild;
  16.  		} 
  17. } 
  18.   	 if(P==NULL){
  19. 	 	cout<<"要删除的结点不存在"<<endl;
  20. 	 }else{
  21. 	 	// ①当该结点是叶子结点时，直接删除
  22. 	 	if(P->lchild==NULL&&P->rchild==NULL){
  23. 	 		if(P->data>Pre->data){
  24. 	 			Pre->rchild=NULL;
  25. 			 }else{
  26. 			 	Pre->lchild=NULL;
  27. 			 }
  28. 			 cout<<"已删除 "<<a<<endl; 
  29. 		 }
  30. 		 //②当该结点有一个左孩子或者一个右孩子时，让其孩子结点代替他的位置
  31. 		 if((P->lchild!=NULL&&P->rchild==NULL)||(P->rchild!=NULL&&P->lchild==NULL)){
  32. 		 	if(P->data>Pre->data){
  33. 		 		if(P->lchild!=NULL){
  34. 		 			Pre->rchild=P->lchild;
  35. 				 }else{
  36. 				 	Pre->rchild=P->rchild;
  37. 				 }
  38. 			 }
  39. 			 if(P->data<Pre->data){
  40. 			 	if(P->lchild!=NULL){
  41. 			 		Pre->lchild=P->lchild;
  42. 				 }else{
  43. 				 	Pre->lchild=P->rchild;
  44. 				 }
  45. 			 }
  46. 			 cout<<"已删除 "<<a<<endl; 
  47. 		 }
  48. 	 //③当左右孩子都存在时找中序遍历的下一个（或上一个结点）结点代替其位置 ，这里采用中序遍历上一个结点来代替 
  49. 		 if(P->lchild!=NULL&&P->rchild!=NULL){
  50. 		 	tree* Q=P->lchild;      //工作指针
  51. 			tree* Pre2;             //用于记录最终遍历到的结点的前序结点，用于后期连接
  52. 			while(Q->rchild){
  53. 				Pre2=Q;
  54. 				Q=Q->rchild;
  55. 			}
  56. 			P->data=Q->data;
  57. 			if(P!=Pre2){
  58. 				Pre2->rchild=Q->lchild;
  59. 			}else{
  60. 				Pre2->lchild=Q->lchild;
  61. 			}
  62. 			delete(Q); 
  63. 			cout<<"已删除 "<<a<<endl;
  64. 		 }
  65. 	        
  66. 	}
  67. 	 
  68. }

这里对第三种情况作一些补充：

注意：这里采用的是找左子树的最右下结点来代替要删除的结点（对于王道书上的用中序遍历的下一个结点的方法是一样的，后面也会附上代码）

第一步：找到左子树的最右下结点（这里用到了一个工作指针Q）

无非只有下面几种情况：

 

由此我们可以王道书上的版本，这里只给代码，分析和上面类似

  1. if(P->lchild!=NULL&&P->rchild!=NULL){
  2. 	     	tree* Q=P->rchild;
  3. 	     	tree* Pre2;
  4. 	     	while(Q->lchild){
  5. 	     		Pre2=Q;
  6. 	     		Q=Q->lchild;
  7. 			 }
  8. 			 P->data=Q->data;
  9. 			 if(P!=Pre2){
  10. 			 	Pre2->lchild=Q->rchild;
  11. 			 }else{
  12. 			 	Pre2->rchild=Q->rchild;
  13. 			 }
  14. 			 delete(Q);
  15. 		 }

六、完整代码（可以运行，两种方法都有）

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. struct tree{
  5. 	int data;
  6. 	struct tree* lchild;
  7. 	struct tree* rchild;
  8. };
  9.  
  10. //建立创建，传入一个完整的数组 
  11. void Creat(int a,tree* &T){
  12. 	if(T==NULL){
  13. 		T=new tree;
  14. 		T->data=a;
  15. 		T->lchild=NULL;
  16. 		T->rchild=NULL;
  17. 	}
  18. 	else if(a>T->data){
  19. 		Creat(a,T->rchild);
  20. 	}
  21. 	else{
  22. 		Creat(a,T->lchild);
  23. 	}
  24. } 
  25.  
  26. //传入数组，一次性插入 
  27. void Insert(tree* &T,int A[],int len){
  28. 	for(int i=0;i<=len;i++){
  29. 		Creat(A[i],T);
  30. 	}
  31. }
  32.  
  33. //中序遍历 
  34. void midorder(tree* T){
  35. 	if(T!=NULL){
  36. 	    midorder(T->lchild);
  37. 		cout<<T->data<<" ";
  38. 		midorder(T->rchild);
  39. 	}
  40. }
  41.  
  42. //判断是否是二叉排序树
  43. //对树进行中序遍历，然后判断是否有序递增 
  44.  
  45. //查找指定结点(输出当前结点是否存在)，如果没有就插入 
  46. void find(tree* &T,int a){
  47. 	tree* K=T;     //T指针指向二叉排序树的根节点，K为工作指针 
  48. 	tree* pre;	   //pre指向当前工作指针的上一个结点，用于插入确定插入位置	 
  49. 	while(K!=NULL&&a!=K->data){
  50. 		if(a>K->data){
  51. 			pre=K;
  52. 			K=K->rchild;
  53. 		}else{
  54. 			pre=K;
  55. 			K=K->lchild;
  56. 		}
  57. 	}
  58. 	if(K==NULL){
  59. 		tree* P;    //工作指针
  60. 		P=new tree;
  61. 		P->data=a;
  62. 		if(P->data>pre->data){
  63. 			pre->rchild=P;
  64. 			P->lchild=NULL;
  65. 			P->rchild=NULL;
  66. 		}
  67. 		else{
  68. 		    pre->lchild=P;
  69. 			P->lchild=NULL;
  70. 			P->rchild=NULL;
  71. 		}
  72. 		cout<<"不存在，已插入 "<<a<<" 这个结点"<<endl;
  73. 	}else{
  74. 		cout<<"存在"<<endl;
  75. 	}
  76. }
  77.  
  78. //删除某一结点，若不存在则提示
  79. //①当该结点是叶子结点时，直接删除
  80. //②当该结点有一个左孩子或者一个右孩子时，让其孩子结点代替他的位置
  81. //③当左右孩子都存在时找中序遍历的下一个(或上一个)结点代替其位置 
  82. void delect(tree* &T,int a){
  83. 	 //首先找到要删除的结点
  84. 	 tree* Pre;
  85. 	 tree* P=T;                      //定义工作指针 
  86. 	 while(P!=NULL&&a!=P->data){     //这两个判定条件不能颠倒 
  87. 	 	if(a>P->data){
  88. 	 		Pre=P;
  89. 	 		P=P->rchild;
  90. 		 }else{
  91. 		 	Pre=P;
  92. 		 	P=P->lchild;
  93.  		} 
  94. } 
  95.   	 if(P==NULL){
  96. 	 	cout<<"要删除的结点不存在"<<endl;
  97. 	 }else{
  98. 	 	// ①当该结点是叶子结点时，直接删除
  99. 	 	if(P->lchild==NULL&&P->rchild==NULL){
  100. 	 		if(P->data>Pre->data){
  101. 	 			Pre->rchild=NULL;
  102. 			 }else{
  103. 			 	Pre->lchild=NULL;
  104. 			 }
  105. 			 cout<<"已删除 "<<a<<endl; 
  106. 		 }
  107. 		 //②当该结点有一个左孩子或者一个右孩子时，让其孩子结点代替他的位置
  108. 		 if((P->lchild!=NULL&&P->rchild==NULL)||(P->rchild!=NULL&&P->lchild==NULL)){
  109. 		 	if(P->data>Pre->data){
  110. 		 		if(P->lchild!=NULL){
  111. 		 			Pre->rchild=P->lchild;
  112. 				 }else{
  113. 				 	Pre->rchild=P->rchild;
  114. 				 }
  115. 			 }
  116. 			 if(P->data<Pre->data){
  117. 			 	if(P->lchild!=NULL){
  118. 			 		Pre->lchild=P->lchild;
  119. 				 }else{
  120. 				 	Pre->lchild=P->rchild;
  121. 				 }
  122. 			 }
  123. 			 cout<<"已删除 "<<a<<endl; 
  124. 		 }
  125. 	 //③当左右孩子都存在时找中序遍历的下一个（或上一个结点）结点代替其位置 ，这里采用中序遍历上一个结点来代替 
  126. //		 if(P->lchild!=NULL&&P->rchild!=NULL){
  127. //		 	tree* Q=P->lchild;      //工作指针
  128. //			tree* Pre2;             //用于记录最终遍历到的结点的前序结点，用于后期连接
  129. //			while(Q->rchild){
  130. //				Pre2=Q;
  131. //				Q=Q->rchild;
  132. //			}
  133. //			P->data=Q->data;
  134. //			if(P!=Pre2){
  135. //				Pre2->rchild=Q->lchild;
  136. //			}else{
  137. //				Pre2->lchild=Q->lchild;
  138. //			}
  139. //			delete(Q); 
  140. //			cout<<"已删除 "<<a<<endl;
  141. //		 }
  142. 	     if(P->lchild!=NULL&&P->rchild!=NULL){
  143. 	     	tree* Q=P->rchild;
  144. 	     	tree* Pre2;
  145. 	     	while(Q->lchild){
  146. 	     		Pre2=Q;
  147. 	     		Q=Q->lchild;
  148. 			 }
  149. 			 P->data=Q->data;
  150. 			 if(P!=Pre2){
  151. 			 	Pre2->lchild=Q->rchild;
  152. 			 }else{
  153. 			 	Pre2->rchild=Q->rchild;
  154. 			 }
  155. 			 delete(Q);
  156. 			 cout<<"已删除 "<<a<<endl;
  157. 		 }   
  158. 	}
  159. 	 
  160. }
  161.  
  162. int main(){
  163. 	tree* T=NULL;
  164. 	int A[]={23,89,65,12,17,3,9,90,21,63,71};
  165. 	Insert(T,A,10);
  166. 	midorder(T);
  167. 	delect(T,89);
  168. 	midorder(T);
  169. 	find(T,89);
  170. 	midorder(T); 
  171. 	return 0;
  172. }

结语：感谢观看，有什么问题望指正

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

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号