登录/ 注册
 找回密码
 立即注册
关闭

CSDN热搜

程序园 精品问答 技术交流 资源下载
返回列表 发新帖
首页 › 业界区 › 科技 ›简易BST实现

简易BST实现

昝梓菱 7 天前
BST，即二叉搜索树，该数据结构规定任意若一个结点存在左子树，那么该结点键必须要大于左子树上所有键；若有右子树，那么该结点键必须要小于右子树上所有键
简单的BST是树形查找里的入门级数据结构，不涉及平衡性调节，只需要简单插入删除，即可，其中删除稍复杂，但是也不难，只需要把三种情况分清即可。简单的BST因为不存在平衡调节，所以针对某些特定序列(如已排序序列依次插入)在构造好BST后，事实上退化为链表，这样搜索效率大幅下降到O(n)
今天先贴个简单BST实现，改天再贴个AVL树的实现
  1. typedef struct BSTnode {
  2.     struct BSTnode *left, *right;
  3.     int data;
  4. }BSTnode, *BST;
  6. //simple BST
  7. BST batch_create_BST(int a[], int n);
  8. void destroy_BST(BST &T);
  9. bool insert_BST(BST &T, int e);
  10. bool delete_BST(BST &T, int e);
  11. bool find_BST(BST &T, int e);
  13. BST batch_create_BST(int a[], int n)
  14. {
  15.     BST T = nullptr;
  16.     for (int i = 0; i < n; ++i)
  17.         insert_BST(T, a[i]);
  18.     return T;
  19. }
  21. void destroy_BST(BST &T)
  22. {
  23.     if (!T)
  24.         return;
  25.     destroy_BST(T->left);
  26.     destroy_BST(T->right);
  27.     free(T);
  28.     T = nullptr;
  29. }
  31. bool insert_BST(BST &T, int e)
  32. {
  33.     if (!T)
  34.     {
  35.         T = (BSTnode *)malloc(sizeof(BSTnode));
  36.         T->data = e;
  37.         T->left = T->right = nullptr;
  38.         return true;
  39.     }
  40.     if (e > T->data)
  41.         return insert_BST(T->right, e);
  42.     else if (e < T->data)
  43.         return insert_BST(T->left, e);
  44.     return false;
  45. }
  47. bool delete_BST(BST &T, int e)
  48. {
  49.     if (!T) // 空树删除失败
  50.         return false;
  51.     if (T->data == e) // 特殊处理根节点删除
  52.     {
  53.         if (T->left && T->right) // 根有左右子树
  54.         {
  55.             BSTnode *p = T, *q = T->left;
  56.             while (q->right) // 找到根节点的前驱以及前驱的父结点
  57.             {
  58.                 p = q;
  59.                 q = q->right;
  60.             }
  61.             T->data = q->data; // 覆盖根的元素
  62.             // 以下删除q
  63.             if (p->left == q)
  64.                 p->left = q->left != nullptr ? q->left : q->right; // 这里可以处理叶节点情况
  65.             else
  66.                 p->right = q->left != nullptr ? q->left : q->right; // 同上
  67.             free(q);
  68.             q = nullptr;
  69.         }
  70.         else // 仅有左或右子树以及叶结点情况
  71.         {
  72.             BSTnode *del = T;
  73.             T = T->left != nullptr ? T->left : T->right; // 事实上这里也能处理单节点情况
  74.             free(del);
  75.             del = nullptr;
  76.         }
  77.     }
  78.     else // 删除内部结点
  79.     {
  80.         BSTnode *p = nullptr, *q = T;
  81.         while (q && q->data != e) // 查找待删除结点及其父结点
  82.         {
  83.             p = q;
  84.             q = q->data > e ? q->left : q->right;
  85.         }
  86.         if (!q) // 没有这个结点删除失败
  87.             return false;
  88.         if (q->left && q->right) // 具有左右子树的结点删除
  89.         {
  90.             BSTnode *pre = q, *del = q->left;
  91.             while (del->right) // 寻找待删除结点的中序直接前驱以及这个前驱的父结点
  92.             {
  93.                 pre = del;
  94.                 del = del->right;
  95.             }
  96.             q->data = del->data; // 前驱直接覆盖原本待删除结点
  97.             // 以下删除del
  98.             if (pre->left == del)
  99.                 pre->left = del->left != nullptr ? del->left : del->right; // 可以处理叶结点情况
  100.             else
  101.                 pre->right = del->left != nullptr ? del->left : del->right;
  102.             ; // 同上
  103.             free(del);
  104.             del = nullptr;
  105.         }
  106.         else    // 仅有单子树的结点或叶结点删除
  107.         {
  108.             if (p->left == q)
  109.                 p->left = q->left != nullptr ? q->left : q->right; // 根据这里可以将前面的叶结点删除作优化掉
  110.             else
  111.                 p->right = q->left != nullptr ? q->left : q->right; // 同上
  112.             free(q);
  113.             q = nullptr;
  114.         }
  115.     }
  116.     return true;
  117. }
  119. bool find_BST(BST &T, int e)
  120. {
  121.     BSTnode *p = T;
  122.     while (p)
  123.     {
  124.         if (e > p->data)
  125.             p = p->right;
  126.         else if (e < p->data)
  127.             p = p->left;
  128.         else
  129.             break;
  130.         ;
  131.     }
  132.     if (p)
  133.         return true;
  134.     else
  135.         return false;
  136. }
复制代码
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

使用道具 举报
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
发帖
昝梓菱
7 天前

0

粉丝关注

12

主题发布

板块介绍填写区域，请于后台编辑
微信扫一扫