[关闭]
@quinn 2015-04-12T03:29:02.000000Z 字数 3136 阅读 1725

二叉搜索树的Insert、Find、FindMin、FindMax、Delete、MakeEmpty

数据结构


searchTree.h 功能实现

  1. /*==============================================
  2. 二叉查找树(BSTree)的Insert、Find、FindMin、FindMax、Delete、MakeEmpty
  3. 编译环境:Visual Studio 2012
  4. Date: 2015/01/17
  5. ==============================================*/
  6. #include <stdlib.h>
  7. #include <string>
  8. #include <iostream>
  9. using namespace std;
  10. typedef int elemType;
  11. typedef struct node BSTreeNode;
  12. typedef struct node BSTree;
  13. struct node
  14. {
  15. elemType elem;
  16. BSTreeNode* left;
  17. BSTreeNode* right;
  18. };
  19. void fatalError(const std::string str)
  20. {
  21. cout << "ERROR: "<< str <<endl;
  22. system("pause");
  23. exit(-1);
  24. }
  25. BSTreeNode* makeBSTreeEmpty(BSTree* bstree)
  26. {
  27. if (bstree != NULL)
  28. {
  29. makeBSTreeEmpty(bstree->left);
  30. makeBSTreeEmpty(bstree->right);
  31. free(bstree);
  32. }
  33. return bstree;
  34. }
  35. BSTreeNode* insertBStree(BSTree* bstree, elemType x)
  36. {
  37. if (bstree == NULL)
  38. {
  39. bstree = (BSTree *)malloc(sizeof(*bstree));
  40. if(bstree == NULL)
  41. fatalError("分配BSTree节点异常");
  42. bstree->elem = x;
  43. bstree->left = NULL;
  44. bstree->right = NULL;
  45. }
  46. else
  47. {
  48. if (x < bstree->elem)
  49. {
  50. bstree->left = insertBStree(bstree->left, x);
  51. }
  52. else if (x > bstree->elem)
  53. {
  54. bstree->right = insertBStree(bstree->right, x);
  55. }
  56. }
  57. return bstree;
  58. }
  59. BSTreeNode* findElem(BSTree* bstree, elemType x)
  60. {
  61. if(bstree == NULL)
  62. {
  63. cout << "没有找到元素:" << x <<endl;
  64. return NULL;
  65. }
  66. else if (x < bstree->elem)
  67. {
  68. findElem(bstree->left, x);
  69. }
  70. else if(x > bstree->elem)
  71. {
  72. findElem(bstree->right, x);
  73. }
  74. else
  75. {
  76. return bstree;
  77. }
  78. }
  79. BSTreeNode* findMinElem(BSTree* bstree)
  80. {
  81. if (bstree == NULL)
  82. {
  83. fatalError("findMinElem:树为空");
  84. }
  85. else if (bstree->left == NULL)
  86. {
  87. return bstree;
  88. }
  89. else
  90. {
  91. findMinElem(bstree->left);
  92. }
  93. }
  94. BSTreeNode* findMaxElem(BSTree* bstree) //递归实现
  95. {
  96. if (bstree == NULL)
  97. {
  98. fatalError("findMaxElem:树为空");
  99. }
  100. else if (bstree->right == NULL)
  101. {
  102. return bstree;
  103. }
  104. else
  105. {
  106. findMaxElem(bstree->right);
  107. }
  108. }
  109. BSTreeNode* findMaxElem2(BSTree* bstree) //非递归实现
  110. {
  111. if (bstree == NULL)
  112. {
  113. fatalError("findMaxElem:树为空");
  114. }
  115. while(bstree->right != NULL)
  116. {
  117. bstree = bstree->right;
  118. }
  119. return bstree;
  120. }
  121. BSTreeNode *deleteElem(BSTree* bstree, elemType x)
  122. {
  123. BSTreeNode* tempNode = NULL;
  124. //删除节点不能通过findElem()函数查找x 元素地址后实现,因为无法获得x 前一结点的地址(可另写一个函数findPrevElem()实现)
  125. if (bstree == NULL)
  126. {
  127. cout << "该BSTree 不含有元素: " << x <<endl;
  128. }
  129. else if (x < bstree->elem) // x在左子树中,向左递归
  130. {
  131. bstree->left = deleteElem(bstree->left, x);
  132. }
  133. else if (x > bstree->elem)
  134. {
  135. bstree->right = deleteElem(bstree->right, x);
  136. }
  137. else //找到元素x的位置:x == bstree->elem,进行删除
  138. {
  139. //=== 1或0个child ======
  140. tempNode = bstree;
  141. if (bstree->left == NULL)
  142. {
  143. bstree = bstree->right;
  144. }
  145. else if (bstree->right == NULL)
  146. {
  147. bstree = bstree->left;
  148. free(tempNode);
  149. }
  150. //=== 2个child ======
  151. else
  152. {
  153. tempNode = findMinElem(bstree->right); //选右子树的最小值代替被删除节点的元素值(或者:选左子树中的最大值)
  154. bstree->elem = tempNode->elem;
  155. bstree->right = deleteElem(bstree->right, tempNode->elem); //删除右子树中的最小值(min没有左子树)
  156. }
  157. //free(tempNode); //free()如果在此处会导致free两次
  158. }
  159. return bstree;
  160. }

searchTree.cpp 测试函数

  1. #include "searchTree.h"
  2. int main()
  3. {
  4. BSTree* T = NULL;
  5. elemType a[] = {30,50,20,40,25,70,54,23,80,92};
  6. for (int i = 0; i < sizeof(a)/sizeof(a[0]); i++)
  7. {
  8. T = insertBStree(T, a[i]);
  9. }
  10. findElem(T, 10);
  11. for (int i = 0; i < sizeof(a)/sizeof(a[0]); i++)
  12. {
  13. cout << a[i] << " 0x" << findElem(T, a[i]) << endl;
  14. }
  15. cout << endl;
  16. cout << "Min: addr--0x" << findMinElem(T) <<endl;
  17. cout << "1-Max: addr--0x" << findMaxElem(T) <<endl;
  18. cout << "2-Max: addr--0x" << findMaxElem2(T) <<endl;
  19. deleteElem(T, 10);
  20. deleteElem(T, 50);
  21. for (int i = 0; i < sizeof(a)/sizeof(a[0]); i++)
  22. {
  23. cout << a[i] << " 0x" << findElem(T, a[i]) << endl;
  24. }
  25. cout << endl;
  26. makeBSTreeEmpty(T);
  27. system("pause");
  28. return 0;
  29. }

参考资料:《数据结构与算法分析——C语言描述》 P73

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注