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

二叉排序树详解以及实现_二叉排序树的构造过程

作者：花生_TL007 | 2024-04-28 14:12:14

赞

踩

二叉排序树的构造过程

目录

1.二叉排序树概念

2.二叉排序树的插入

（1）二叉排序树的插入过程

（2）节点插入实现

3.二叉排序树的查找

4.二叉排序树的遍历

5.二叉树排序树节点的删除

（1）删除二叉排序树节点*P

6.完整的流程测试

使用C语言实现二叉树的链式存储

数据结构之折半查找（递归和非递归），插值查找和斐波那契查找

静态树表的查找（最优查找树和次优查找树）

1.二叉排序树概念

二叉排序树（Binary Sort Tree）也称为二叉查找树后者二叉搜索树：

  • 具有的性质：
    • 1.若它的左子树不空，则左子树上的所有节点的值均小于它的根节点的值；
    • 2.若它的右子树不空，则右子树上的所有节点的值均大于它的根节点的值；
    • 3.若左右子树都不为空，左右子树也分别为二叉排序树；

二叉排序树结构的定义：

  1. typedef int ElemType;
  2.  
  3. typedef struct BSTNode{
  4. 	ElemType data;
  5. 	struct BSTNode*lchild,*rchild;
  6. }*BSTree;

2.二叉排序树的插入

（1）二叉排序树的插入过程

假设：现在有查找的关键字序列为{45,24,53,45,12,24,90}，二叉排序树的插入过程如下：

（2）节点插入实现

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<string.h>
  4. #include<queue>
  5. #include<stack>
  6.  
  7.  
  8. void BSTreemenu(){
  9. 	printf("---------------1.插入节点--------------\n");
  10. 	printf("---------------2.查询节点--------------\n");
  11. 	printf("---------------3.删除节点--------------\n");
  12. 	printf("---------------4.输出节点--------------\n");
  13. 	printf("---------------5.退出程序--------------\n");
  14. }
  1. //构造一棵二叉排序树
  2. int BST_Insert(BSTree&T,int key){
  3. 	if(T==NULL){
  4. 		T=(BSTree)malloc(sizeof(BSTNode));
  5. 		T->data=key;
  6. 		T->lchild=NULL;
  7. 		T->rchild=NULL;
  8. 		return 1;
  9. 	}else if(T->data==key){
  10. 		return 0;
  11. 	}else if(T->data>key){
  12. 		BST_Insert(T->lchild,key);
  13. 	}else {
  14. 		BST_Insert(T->rchild,key);
  15. 	}
  16. }

3.二叉排序树的查找

二叉排序树的查找过程类似于次优二叉树，查找步骤：

  • 1.首先将给定值和根节点的值进行比较，若相等，则查找成功，否则进行第二步；
  • 2.若给定的值大于根节点的值，则到根节点的右子树上进行相同的比较；
  • 3.若给定的值小于根节点的值，则到根节点的左子树上进行相同的比较；
  1. //递归查询节点
  2. BSTNode*BST_Search(BSTree T,int key){
  3. 	if(T==NULL)return NULL;
  4. 	if(T->data==key){
  5. 		return T;
  6. 	}else if(T->data>key){
  7. 		BST_Search(T->lchild,key);
  8. 	}else{
  9. 		BST_Search(T->rchild,key);
  10. 	}
  11. } 
  12. //非递归查询
  13. BSTNode*BSTSearch(BSTree T,int key){
  14. 	while(T!=NULL&&T->data!=key){
  15. 		if(T->data>key){
  16. 			T=T->lchild; 
  17. 		}else{
  18. 			T=T->rchild;
  19. 		}
  20. 	}
  21. }

4.二叉排序树的遍历

该遍历和二叉树的遍历过程一样，但是这里有一个技巧，就是判断一棵二叉树是否为二叉排序树：如果中序遍历为有序的序列，则为二叉排序树。

  1. //中序遍历二叉排序树(有序)
  2. void  BST_display(BSTree T){
  3. 	if(T==NULL)return;
  4. 	BST_display(T->lchild);
  5. 	printf("%d  ",T->data);
  6. 	BST_display(T->rchild);
  7. }

5.二叉树排序树节点的删除

（1）删除二叉排序树节点*P

  • 情况一：
    • 如果*P节点为叶子节点，那么其左右子树都是为NULL，也就是删除此节点并不会破坏整棵树的结构，所以直接删除节点*P即可。

 

 

  • 情况二：
    • 如果*P节点只有左子树PL或者右子树PR，那么只需要将PL或者PR为*P双亲*F的左子树或者右子树即可。

 

  • 情况三：
    • 如果左右子树都不为空的话，那么以上方法则不能使用。由于二叉排序树中序遍历时得到是一个从小到大的序列，在删除节点*P之前，首先找到其*P的直接前驱*S（也就是*P的左子树上最大值的节点）或者直接后继*S（也就是*P右子树上最小值的节点），使用直接前驱或者直接后继的值替代*P节点的值。注意：虽然使用直接前驱或者直接后继的值去替代之后，还是不能直接删除直接前驱或者直接后继，因为对于直接前驱节点来说，有可能其左子树不为空；而对于直接后继节点来说，有可能其右子树不为空，对于上面这种情况的话，使用直接前驱或者直接后继替代*P之后，我们需要将*S的左子树或者右子树挂到*S的双亲节点上去。

 

  1. //删除节点操作
  2. //情况一
  3. void DeleteBSTOne(BSTree T,int key){
  4. 	if(!T){
  5. 		printf("不存在删除的节点!\n");
  6. 	}else{
  7. 		if(T->data==key){
  8. 			free(T);
  9. 			printf("删除成功!\n");
  10. 		}else if(T->data>key){
  11. 			DeleteBSTOne(T->lchild,key);
  12. 		}else{
  13. 			DeleteBSTOne(T->rchild,key);
  14. 		}
  15. 	}
  16. } 
  17. //情况二,三 
  18. void  DeleteBSTwoThree(BSTNode*p){
  19. 	//如果*p不存在右子树，那么只需要将左子树挂到双亲上 
  20. 	BSTNode*q=NULL;
  21. 	if(!p->rchild){
  22. 		q=p;
  23. 		p=p->lchild;
  24. 		free(q);
  25. 	}else if(!p->lchild){//否则接右子树 
  26. 		q=p;
  27. 		p=p->rchild;
  28. 		free(q);
  29. 	}else{//左右子树都不空情况 
  30. 		q=p;
  31. 		BSTNode*s=p->lchild;
  32. 		//找到直接前驱，也就是*P左子树的最大值 
  33. 		while(s->rchild){
  34. 			q=s;//q指向节点s的双亲 
  35. 			s=s->rchild;
  36. 		} 
  37. 		p->data=s->data;
  38. 		if(q!=p){
  39. 			q->rchild=s->lchild;
  40. 		}else{
  41. 			q->lchild=s->lchild;
  42. 		}
  43. 		free(s);
  44. 	}
  45. 	printf("删除节点成功!");
  46. 	return ;
  47. }

6.完整的流程测试

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<string.h>
  4. #include<queue>
  5. #include<stack>
  6.  
  7. typedef int ElemType;
  8.  
  9. typedef struct BSTNode{
  10. 	ElemType data;
  11. 	struct BSTNode*lchild,*rchild;
  12. }*BSTree;
  13.  
  14. void BSTreemenu(){
  15. 	printf("---------------1.插入节点--------------\n");
  16. 	printf("---------------2.查询节点--------------\n");
  17. 	printf("---------------3.删除节点--------------\n");
  18. 	printf("---------------4.输出节点--------------\n");
  19. 	printf("---------------5.退出程序--------------\n");
  20. }
  21.  
  22. //构造一棵二叉排序树
  23. int BST_Insert(BSTree&T,int key){
  24. 	if(T==NULL){
  25. 		T=(BSTree)malloc(sizeof(BSTNode));
  26. 		T->data=key;
  27. 		T->lchild=NULL;
  28. 		T->rchild=NULL;
  29. 		return 1;
  30. 	}else if(T->data==key){
  31. 		return 0;
  32. 	}else if(T->data>key){
  33. 		BST_Insert(T->lchild,key);
  34. 	}else {
  35. 		BST_Insert(T->rchild,key);
  36. 	}
  37. } 
  38.  
  39. //销毁操作
  40. void BST_Destroy(BSTree&T){
  41. 	if(T==NULL)return ;
  42. 	BST_Destroy(T->lchild);
  43. 	BST_Destroy(T->rchild);
  44. 	free(T);
  45. } 
  46.  
  47. //递归查询节点
  48. BSTNode*BST_Search(BSTree T,int key){
  49. 	if(T==NULL)return NULL;
  50. 	if(T->data==key){
  51. 		return T;
  52. 	}else if(T->data>key){
  53. 		BST_Search(T->lchild,key);
  54. 	}else{
  55. 		BST_Search(T->rchild,key);
  56. 	}
  57. } 
  58. //非递归查询
  59. BSTNode*BSTSearch(BSTree T,int key){
  60. 	while(T!=NULL&&T->data!=key){
  61. 		if(T->data>key){
  62. 			T=T->lchild; 
  63. 		}else{
  64. 			T=T->rchild;
  65. 		}
  66. 	}
  67. } 
  68.  
  69. //中序遍历二叉排序树(有序)
  70. void  BST_display(BSTree T){
  71. 	if(T==NULL)return;
  72. 	BST_display(T->lchild);
  73. 	printf("%d  ",T->data);
  74. 	BST_display(T->rchild);
  75. }
  76.  
  77. //删除节点操作
  78. //情况一
  79. void DeleteBSTOne(BSTree T,int key){
  80. 	if(!T){
  81. 		printf("不存在删除的节点!\n");
  82. 	}else{
  83. 		if(T->data==key){
  84. 			free(T);
  85. 			printf("删除成功!\n");
  86. 		}else if(T->data>key){
  87. 			DeleteBSTOne(T->lchild,key);
  88. 		}else{
  89. 			DeleteBSTOne(T->rchild,key);
  90. 		}
  91. 	}
  92. } 
  93. //情况二,三 
  94. void  DeleteBSTwoThree(BSTNode*p){
  95. 	//如果*p不存在右子树，那么只需要将左子树挂到双亲上 
  96. 	BSTNode*q=NULL;
  97. 	if(!p->rchild){
  98. 		q=p;
  99. 		p=p->lchild;
  100. 		free(q);
  101. 	}else if(!p->lchild){//否则接右子树 
  102. 		q=p;
  103. 		p=p->rchild;
  104. 		free(q);
  105. 	}else{//左右子树都不空情况 
  106. 		q=p;
  107. 		BSTNode*s=p->lchild;
  108. 		//找到直接前驱，也就是*P左子树的最大值 
  109. 		while(s->rchild){
  110. 			q=s;//q指向节点s的双亲 
  111. 			s=s->rchild;
  112. 		} 
  113. 		p->data=s->data;
  114. 		if(q!=p){
  115. 			q->rchild=s->lchild;
  116. 		}else{
  117. 			q->lchild=s->lchild;
  118. 		}
  119. 		free(s);
  120. 	}
  121. 	printf("删除节点成功!");
  122. 	return ;
  123. }
  124.  
  125. int main(){
  126. 	BSTree T=NULL;
  127. 	int key;
  128. 	BSTNode*p; 
  129. 	int flag;
  130. 	while(1){
  131. 		int opt;
  132. 		BSTreemenu();
  133. 		printf("请输入操作: ");
  134. 		scanf("%d",&opt);
  135. 		switch(opt){
  136. 			case 1:
  137. 				printf("请输入元素(end=-1): ");
  138. 				scanf("%d",&key);
  139. 				while(key!=-1){
  140. 					flag=BST_Insert(T,key);
  141. 					if(flag==0){
  142. 						printf("该元素已经存在\n");
  143. 					}
  144. 					printf("请输入元素(end=-1): ");
  145. 					scanf("%d",&key);
  146. 				}
  147. 				break;
  148. 			case 2:
  149. 				printf("请输入要查找的元素: ");
  150. 				scanf("%d",&key);
  151. 				p=BST_Search(T,key);
  152. 				if(p!=NULL){
  153. 					printf("查找的元素为: %d\n",p->data);
  154. 				}else{
  155. 					printf("查找的元素不存在\n");
  156. 					//不存在该元素，则插入 
  157. 					BST_Insert(T,key);
  158. 				}
  159. 				break;
  160. 			case 3:
  161. 				//这里删除节点只操作了叶子节点，关于有左子树（或者右子树），左右子树都不空情况代码已经实现，读者可以
  162. 				//自己尝试 
  163. 				printf("请输入删除节点的值: ");
  164. 				scanf("%d",&key);
  165. 				DeleteBSTOne(T,key);
  166. 			case 4:
  167. 				BST_display(T);
  168. 				printf("\n");
  169. 				break; 
  170. 			default:
  171. 				flag=5;
  172. 				printf("退出操作:\n");
  173. 				BST_Destroy(T);
  174. 				break;
  175. 		} 
  176. 		if(flag==5)break;
  177. 	}
  178. 	return 0;
  179. }

 

 

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

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

  

闽ICP备14008679号