• 数据结构-二叉排序树（建立、查找、修改）

    二叉排序树概念

    二叉排序树是动态查找表的一种，也是常用的表示方法。

    其中，它具有如下性质：

    1.若它的左子树非空，则其左子树的所有节点的关键值都小于根节点的关键值。

    2.若它的右子树非空，则其右子树的所有节点的关键值都大于根结点的关键值。

    3.它的左右子树也分别都是二叉排序树。

    PS：对二叉排序树进行中序遍历，得到的序列，总会是一个升序的数列。

    二叉排序树的建立

    我们使用C语言来建立。

    其中我们对二叉排序树的结构体定义如下：

    1. typedef int ElemType;
    2. typedef struct BTNode{
    3.     ElemType key;
    4.     struct BTNode *lchild,*rchild;
    5. }BTNode,*BSTree;

    建立二叉排序树的代码如下：

    1. BSTree InsertBST(BSTree bst,BSTree s)		//遍历二叉排序树,找到合适的位置 
    2. {
    3. 	if(bst==NULL)
    4. 		bst = s;
    5. 	else{
    6. 		if(s->key < bst->key)
    7. 			bst->lchild = InsertBST(bst->lchild,s);
    8. 		if(s->key > bst->key){
    9. 			bst->rchild = InsertBST(bst->rchild,s);
    10. 		}
    11. 	}
    12. 	return bst;
    13. }
    14.  
    15. BSTree CreateBST()		//建立二叉排序树 
    16. {
    17. 	BSTree bst,s;
    18. 	int key;
    19. 	bst = NULL;
    20. 	printf("请输入关键字值,输入-1结束.\n");
    21. 	while(1){
    22. 		scanf("%d",&key);
    23. 		if(key!=-1){
    24. 			s = (BSTree)malloc(sizeof(BTNode));
    25. 			s->key = key;
    26. 			s->lchild = NULL;
    27. 			s->rchild = NULL;
    28. 			bst = InsertBST(bst,s);
    29. 			printf("成功.\n");
    30. 		}
    31. 		else
    32. 			break;
    33. 	}
    34. 	return bst;
    35. }

    二叉排序树的插入

    1. BSTree InsertBST(BSTree bst,BSTree s)		//遍历二叉排序树,找到合适的位置 
    2. {
    3. 	if(bst==NULL)
    4. 		bst = s;
    5. 	else{
    6. 		if(s->key < bst->key)
    7. 			bst->lchild = InsertBST(bst->lchild,s);
    8. 		if(s->key > bst->key){
    9. 			bst->rchild = InsertBST(bst->rchild,s);
    10. 		}
    11. 	}
    12. 	return bst;
    13. }
    14.  
    15. BSTree SearchBST(BSTree bst,int key)		//查找关键值key的节点,并且返回这个节点 
    16. {
    17. 	if(bst == NULL)
    18. 		return NULL;
    19. 	else if(key == bst->key)
    20. 		return bst;
    21. 	else if(key > bst->key)
    22. 		return SearchBST(bst->rchild,key);
    23. 	else
    24. 		return SearchBST(bst->lchild,key);
    25. }
    26.  
    27. BSTree InsertBST_key(BSTree bst,int key)		//搜寻一个关键值,如果没有就插入 
    28. {
    29. 	BSTree s;
    30. 	s = SearchBST(bst,key);
    31. 	if(s)
    32. 		printf("该节点已经存在.");
    33. 	else{
    34. 		s = (BSTree)malloc(sizeof(BTNode));
    35. 		s->key = key;
    36. 		s->lchild = NULL;
    37. 		s->rchild = NULL;
    38. 		s = InsertBST(bst,s);
    39. 	}
    40. 	return s;
    41. }

    查找二叉排序树指定节点的双亲

    1. BSTree SearchBST_F(BSTree bst,int key,BSTree *F)		//F存储key关键值节点的双亲节点,函数返回key关键值节点. 
    2. {
    3. 	if(bst == NULL)
    4. 		return NULL;
    5. 	if(key == bst->key)
    6. 		return bst;
    7. 	else{
    8. 		*F = bst;
    9. 		if(key < bst->key)
    10. 			return SearchBST_F(bst->lchild,key,F);
    11. 		else
    12. 			return SearchBST_F(bst->rchild,key,F);
    13. 	}
    14. }

     删除二叉排序树中某个节点：

    对于删除二叉排序树的节点，我们有必要花大功夫来讨论一下。

    对于删除二叉排序树的某个节点，大致有以下四种情况：

    假设我们要删除的节点指定为P。

    1.P节点的左右子树都为空

    此时删除P节点，只需要P节点的父节点的左/右子树赋值NULL，并且free掉P节点即可。

    值得注意的是，还有一种特殊情况，那就是P节点本身就是根节点，也就是这个树只有P节点一个

    节点。

    那么此时，我们只需要返回NULL，并且free掉P节点即可。

    2.P节点的左子树为空

    在这种情况下，我们注意到P的右子树不是空的，如下图所示：

    此时我们只需要令P节点的父节点C的右子树/左子树为P的右子树即可。

    不过值得注意的是，此时仍有可能P是根节点，此时我们需要令根节点 = p的右子树，并且free掉p

    节点即可。

    3.P节点的右子树为空

    此时我们注意到，这种情况根情况2（P节点的左子树为空）非常相似。

    此时我们只需要令P的父节点C的左/右子树等于P的左子树即可。

    不过此时P节点仍有可能作为根节点出现，此时我们只需要令根节点等于P的左子树即可。

    4.P节点的左右子树都不为空

    这种情况无疑是最复杂的一种情况，因为此时我们要牵扯一个大小的排序。

    因此，我们可以令P节点的Key值等于P节点的直接前驱(直接后驱)的Key值，之后删掉直接前驱(直

    接后驱)即可。

    注意到此时的P节点的直接前驱是G（即P节点的左子树的最右侧的一个节点）。

    那么此时我们可以令P节点的Key值等于G节点的Key值，同时free掉G节点即可完成操作。

    不过，比较重要的一点是，G节点的左子树不一定为空，此时我们仍需要让G节点的父节点的右子

    树等于G节点的左子树。

    注意到，当P节点作为根结点的时候并不会出现特殊的情况，但是当P节点的前驱节点就是P的左子

    树，我们需要另外的讨论，如下图所示：

    注意到此时P的直接前驱节点就是D，但是如果我们直接删除D，那么D的左子树此时应该给P的左

    子树。

    注意到P也是D的一个父节点，P同时还是D的一个直接后继节点，此时就是一种特殊情况，需要让

    P的左子树等于D的左子树，而不是D的父节点的右子树等于D的左子树！！！

    代码实现：

    1. BSTree SearchBST_F(BSTree bst,int key,BSTree *F)	//查找Key值节点的父节点,*F存储父节点,函数返回Key节点 
    2. {
    3. 	if(bst == NULL)
    4. 		return NULL;
    5. 	if(bst->key == key)
    6. 		return bst;
    7. 	else{
    8. 		*F = bst;
    9. 		if(bst->key > key)
    10. 			return SearchBST_F(bst->lchild,key,F);
    11. 		else
    12. 			return SearchBST_F(bst->rchild,key,F);
    13. 	}
    14. }
    15.  
    16. BSTree DeleteBST(BSTree bst,BSTree p,BSTree f)
    17. {
    18. 	BSTree par,s;
    19. 	int kind;
    20. 	if(!p->lchild && !p->rchild)	//左右子树全为空 
    21. 		kind = 1;
    22. 	else if(!p->lchild)			//左子树为空 
    23. 		kind = 2;
    24. 	else if(!p->rchild)			//右子树为空 
    25. 		kind = 3;
    26. 	else			//左右子树都不为空 
    27. 		kind = 4;
    28. 	switch(kind){
    29. 		case 1:
    30. 			if(!f)			//没有父节点，p是根节点, 
    31. 				return NULL;
    32. 			else{
    33. 				if(f->lchild == p)
    34. 					f->lchild = NULL;
    35. 				else
    36. 					f->rchild = NULL;
    37. 				free(p);
    38. 			}
    39. 			break;
    40. 		case 2:
    41. 			if(!f)			//p是根节点
    42. 				bst = bst->rchild;
    43. 			else{
    44. 				if(p == f->lchild)
    45. 					f->lchild = p->rchild;
    46. 				else
    47. 					f->rchild = p->rchild;
    48. 				free(p);
    49. 			}
    50. 			break;
    51. 		case 3:
    52. 			if(!f)			//p是根节点 
    53. 				bst = bst->lchild;
    54. 			else{
    55. 				if(p == f->lchild)
    56. 					f->lchild = bst->lchild;
    57. 				else
    58. 					f->rchild = bst->lchild;
    59. 			}
    60. 			free(p);
    61. 			break;
    62. 		case 4:
    63. 			par = p;		//p节点前驱指针par 
    64. 			s = p->lchild;		//用来遍历p的直接前驱节点(左子树的最右侧) 
    65. 			while(s->rchild != NULL){		//结束条件是s的右子树为空,此时s就是p的直接前驱节点 
    66. 				par = s;
    67. 				s = s->rchild;
    68. 			}
    69. 			p->key = s->key;		//令p节点的值为s节点的值 
    70. 			if(par == p)		//特殊情况,s节点刚好是p的左子树 
    71. 				par->lchild = s->lchild;
    72. 			else
    73. 				par->rchild = s->lchild;		//par的右子树需要等于s节点的左子树 
    74. 			free(s);		//释放p节点的直接前驱s 
    75. 			break;
    76. 	}	
    77. 	return bst;
    78. }
    79.  
    80. BSTree SearchDeleteBST(BSTree bst,int key)
    81. {
    82. 	BSTree f = NULL,p;
    83. 	p = SearchBST_F(bst,key,&f);
    84. 	if(p){
    85. 		bst = DeleteBST(bst,p,f);
    86. 	}
    87. 	else
    88. 		printf("该节点不存在.\n");
    89. 	return bst;
    90. }

    二叉排序树的所有代码汇总： 

    1. #include
    2. #include
    3. typedef int ElemType;
    4. typedef struct BSNode{
    5. 	ElemType key;
    6. 	struct BSNode *lchild,*rchild;
    7. }BSNode,*BSTree;
    8.  
    9. BSTree SearchBST(BSTree bst,BSTree s)
    10. {
    11. 	if(bst == NULL)
    12. 		bst = s;
    13. 	else{
    14. 		if(bst->key > s->key)
    15. 			bst->lchild = SearchBST(bst->lchild,s);
    16. 		if(bst->key < s->key)
    17. 			bst->rchild = SearchBST(bst->rchild,s);
    18. 	}
    19. 	return bst;
    20. }
    21.  
    22. BSTree CreateBSTree()
    23. {
    24. 	int key;
    25. 	BSTree bst = NULL;
    26. 	printf("请输入节点关键值,输入-1结束.\n");
    27. 	while(1){
    28. 		scanf("%d",&key);
    29. 		if(key != -1){
    30. 			BSTree s = (BSTree)malloc(sizeof(BSNode));
    31. 			s->key = key;
    32. 			s->lchild = NULL;
    33. 			s->rchild = NULL;
    34. 			bst = SearchBST(bst,s);
    35. 			printf("创建节点成功.\n");
    36. 		}
    37. 		else
    38. 			break;
    39. 		
    40. 	}
    41. 	return bst;
    42. }
    43.  
    44. void PostTraverse(BSTree bst)
    45. {
    46. 	if(bst){
    47. 		PostTraverse(bst->lchild);
    48. 		printf("%d ",bst->key);
    49. 		PostTraverse(bst->rchild);
    50. 	}
    51. }
    52.  
    53. BSTree SearchBST_F(BSTree bst,int key,BSTree *F)	//查找Key值节点的父节点,*F存储父节点,函数返回Key节点 
    54. {
    55. 	if(bst == NULL)
    56. 		return NULL;
    57. 	if(bst->key == key)
    58. 		return bst;
    59. 	else{
    60. 		*F = bst;
    61. 		if(bst->key > key)
    62. 			return SearchBST_F(bst->lchild,key,F);
    63. 		else
    64. 			return SearchBST_F(bst->rchild,key,F);
    65. 	}
    66. }
    67.  
    68. BSTree DeleteBST(BSTree bst,BSTree p,BSTree f)
    69. {
    70. 	BSTree par,s;
    71. 	int kind;
    72. 	if(!p->lchild && !p->rchild)	//左右子树全为空 
    73. 		kind = 1;
    74. 	else if(!p->lchild)			//左子树为空 
    75. 		kind = 2;
    76. 	else if(!p->rchild)			//右子树为空 
    77. 		kind = 3;
    78. 	else			//左右子树都不为空 
    79. 		kind = 4;
    80. 	switch(kind){
    81. 		case 1:
    82. 			if(!f)			//没有父节点，p是根节点, 
    83. 				return NULL;
    84. 			else{
    85. 				if(f->lchild == p)
    86. 					f->lchild = NULL;
    87. 				else
    88. 					f->rchild = NULL;
    89. 				free(p);
    90. 			}
    91. 			break;
    92. 		case 2:
    93. 			if(!f)			//p是根节点
    94. 				bst = bst->rchild;
    95. 			else{
    96. 				if(p == f->lchild)
    97. 					f->lchild = p->rchild;
    98. 				else
    99. 					f->rchild = p->rchild;
    100. 				free(p);
    101. 			}
    102. 			break;
    103. 		case 3:
    104. 			if(!f)			//p是根节点 
    105. 				bst = bst->lchild;
    106. 			else{
    107. 				if(p == f->lchild)
    108. 					f->lchild = bst->lchild;
    109. 				else
    110. 					f->rchild = bst->lchild;
    111. 			}
    112. 			free(p);
    113. 			break;
    114. 		case 4:
    115. 			par = p;		//p节点前驱指针par 
    116. 			s = p->lchild;		//用来遍历p的直接前驱节点(左子树的最右侧) 
    117. 			while(s->rchild != NULL){		//结束条件是s的右子树为空,此时s就是p的直接前驱节点 
    118. 				par = s;
    119. 				s = s->rchild;
    120. 			}
    121. 			p->key = s->key;		//令p节点的值为s节点的值 
    122. 			if(par == p)		//特殊情况,s节点刚好是p的左子树 
    123. 				par->lchild = s->lchild;
    124. 			else
    125. 				par->rchild = s->lchild;		//par的右子树需要等于s节点的左子树 
    126. 			free(s);		//释放p节点的直接前驱s 
    127. 			break;
    128. 	}	
    129. 	return bst;
    130. }
    131.  
    132. BSTree SearchDeleteBST(BSTree bst,int key)
    133. {
    134. 	BSTree f = NULL,p;
    135. 	p = SearchBST_F(bst,key,&f);
    136. 	if(p){
    137. 		bst = DeleteBST(bst,p,f);
    138. 	}
    139. 	else
    140. 		printf("该节点不存在.\n");
    141. 	return bst;
    142. } 
    143.  
    144. int main()
    145. {
    146. 	BSTree bst;
    147. 	bst = CreateBSTree();
    148. 	SearchDeleteBST(bst,5);
    149. 	PostTraverse(bst);
    150. 	return 0;
    151. }
  • 相关阅读:
    NFS从入门到精通再到放弃
    批量重命名与翻译文件技巧大揭秘
    Android学习笔记 63. 添加一个ScrollView
    JavaWeb项目（三）
    Python Opencv实践 - FAST关键点检测
    一个案例搞懂工厂模式和单例模式
    Java还是要系统学习，阿里面试失败的经验总结，最终获字节offer
    【C++】-- STL之unordered_map/unordered_set详解
    基于单片机的太阳能热水器控制系统设计
    day34（arguments 原型对象prototype apply和call 以及 柯里化函数）
  • 原文地址：https://blog.csdn.net/zheshiyangyang/article/details/134383064