经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置：技术经验 » 程序设计 » 编程经验 » 查看文章
二叉搜索树的实现与常见用法
来源：cnblogs　　作者：GodBMW　　时间：2018/10/24 9:09:19　　对本文有异议

作者按：因为教程所示图片使用的是 github 仓库图片，网速过慢的朋友请移步《二叉搜索树的实现与常见用法》原文地址。更欢迎来我的小站看更多原创内容：godbmw.com，进行“姿势”交流 ?(^?^*)

1. 为什么需要二叉搜索树？

选择数据结构的核心在于解决问题，而不是为了使用而使用。

由于二叉搜索树的定义和特性，它可以高效解决以下问题：

  • 查找问题：二分查找
  • 高级结构：字典结构实现
  • 数据变动：节点的插入、删除
  • 遍历问题：前序、中序、后序和层次遍历
  • 数值运算：ceil、floor、找到第 n 大的元素、找到指定元素在排序好的数组的位置 等等

值得一提的是，除了遍历算法，上述各种问题的算法时间复杂度都是 : \(O(\log_2 n)\)

2. 二叉搜索树的定义和性质

二叉搜索树是一颗空树，或者具有以下性质的二叉树：

  • 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值
  • 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值
  • 任意节点的左、右子树也分别为二叉查找树
  • 没有键值相等的节点

需要注意的是，二叉搜索树不一定是一颗完全二叉树，因此，二叉搜索树不能用数组来存储。

3. 二叉搜索树的实现

第 3 部分实现的测试代码地址：https://gist.github.com/dongyuanxin/d0803a8821c6797e9ce8522a676cf44b。

这是 Github 的 GIST，请自备梯子。

3.1 树结构实现

借助struct和指针模拟树的结构，并且将其封装到BST这个类之中：

  1. // BST.h
  2. // Created by godbmw.com on 2018/9/27.
  3. //
  5. #ifndef BINARYSEARCH_BST_H
  6. #define BINARYSEARCH_BST_H
  8. #include <iostream>
  9. #include <queue>
  11. using namespace std;
  13. template <typename Key, typename Value>
  14. class BST {
  15. private:
  16.     struct Node {
  17.         Key key;
  18.         Value value;
  19.         Node  *left;
  20.         Node *right;
  22.         Node(Key key, Value value) {
  23.             this->key = key;
  24.             this->value = value;
  25.             this->left = NULL;
  26.             this->right = NULL;
  27.         }
  29.         Node(Node* node) {
  30.             this->key = node->key;
  31.             this->value = node->value;
  32.             this->left = node->left;
  33.             this->right = node->right;
  34.         }
  35.     };
  37.     Node *root;
  38.     int count;
  40. public:
  41.     BST() {
  42.         this->root = NULL;
  43.         this->count = 0;
  44.     }
  45.     ~BST() {
  46.         this->destroy(this->root);
  47.     }
  48.     int size() {
  49.         return this->count;
  50.     }
  51.     bool isEmpty() {
  52.         return this->root == NULL;
  53.     }
  54. };
  56. #endif //BINARYSEARCH_BST_H

3.2 实现节点插入

插入采取递归的写法，思路如下：

  1. 递归到底层情况：新建节点，并且返回
  2. 非底层情况：如果当前键等于插入键，则更新当前节点的值；小于，进入当前节点的左子树；大于，进入当前节点的右子树。
  1. private:
  2.     Node* insert(Node* node, Key key, Value value) {
  3.         if(node == NULL) {
  4.             count++;
  5.             return new Node(key, value);
  6.         }
  8.         if(key == node->key) {
  9.             node->value = value;
  10.         } else if( key < node->key) {
  11.             node->left = insert(node->left, key, value);
  12.         } else {
  13.             node->right = insert(node->right, key, value);
  14.         }
  15.         return node;
  16.     }
  18. public:
  19.     void insert(Key key, Value value) {
  20.         this->root = this->insert(this->root, key, value);
  21.     }

3.3 实现节点的查找

查找包含 2 个函数：contain和search。前者返回布尔型，表示树中是否有这个节点；后者返回指针类型，表示树中节点对应的值。

search为什么返回值的指针类型呢：

  • 如果要查找的节点不存在，指针可以直接返回NULL。
  • 如果返回Node*，就破坏了类的封装性。原则上，内部数据结构不对外展示。
  • 如果查找的节点存在，返回去键对应的值，用户可以修改，并不影响树结构。
  1. private:
  2.     bool contain(Node* node, Key key) {
  3.         if(node == NULL) {
  4.             return false;
  5.         }
  6.         if(key == node->key) {
  7.             return true;
  8.         } else if(key < node->key) {
  9.             return contain(node->left, key);
  10.         } else {
  11.             return contain(node->right, key);
  12.         }
  13.     }
  15.     Value* search(Node* node, Key key) {
  16.         if(node == NULL) {
  17.             return NULL;
  18.         }
  19.         if(key == node->key) {
  20.             return &(node->value);
  21.         } else if (key < node->key) {
  22.             return search(node->left, key);
  23.         } else {
  24.             return search(node->right, key);
  25.         }
  26.     }
  27. public:
  28.     bool contain(Key key) {
  29.         return this->contain(this->root, key);
  30.     }
  32. //    注意返回值类型
  33.     Value* search(Key key) {
  34.         return this->search(this->root, key);
  35.     }

3.4 遍历实现

前序、中序和后序遍历的思路很简单，根据定义，直接递归调用即可。

对于层次遍历，需要借助队列queue这种数据结构。思路如下：

  1. 首先，将根节点放入队列
  2. 如果队列不空，进入循环
  3. 取出队列头部元素，输出信息。并将这个元素出队
  4. 将这个元素非空的左右节点依次放入队列
  5. 检测队列是否为空，不空的进入第 3 步；空的话，跳出循环。
  1. private:
  2.     void pre_order(Node* node) {
  3.         if(node != NULL) {
  4.             cout<<node->key<<endl;
  5.             pre_order(node->left);
  6.             pre_order(node->right);
  7.         }
  8.     }
  10.     void in_order(Node* node) {
  11.         if(node != NULL) {
  12.             in_order(node->left);
  13.             cout<<node->key<<endl;
  14.             in_order(node->right);
  15.         }
  16.     }
  18.     void post_order(Node *node) {
  19.         if(node != NULL) {
  20.             post_order(node->left);
  21.             post_order(node->right);
  22.             cout<<node->key<<endl;
  23.         }
  24.     }
  26.     void level_order(Node* node) {
  27.         if(node == NULL) {
  28.             return;
  29.         }
  30.         queue<Node*> q;
  31.         q.push(node);
  32.         while(!q.empty()) {
  33.             Node* node = q.front();
  34.             q.pop();
  35.             cout<< node->key <<endl;
  36.             if(node->left) {
  37.                 q.push(node->left);
  38.             }
  39.             if(node->right) {
  40.                 q.push(node->right);
  41.             }
  42.         }
  43.     }
  45. public:
  46.     void pre_order() {
  47.         this->pre_order(this->root);
  48.     }
  50.     void in_order() {
  51.         this->in_order(this->root);
  52.     }
  54.     void post_order() {
  55.         this->post_order(this->root);
  56.     }
  58.     void level_order() {
  59.         this->level_order(this->root);
  60.     }

3.5 实现节点删除

为了方便实现，首先封装了获取最小键值和最大键值的两个方法：minimum和maximum。

删除节点的原理很简单（忘了什么名字，是一个计算机科学家提出的），思路如下：

  1. 如果左节点为空，删除本节点，返回右节点。
  2. 如果右节点为空，删除本节点，返回左节点。
  3. 如果左右节点都为空，是 1 或者 2 的子情况。
  4. 如果左右节点都不为空，找到当前节点的右子树的最小节点，并用这个最小节点替换本节点。

为什么第 4 步这样可以继续保持二叉搜索树的性质呢？

显然，右子树的最小节点，能满足小于右子树的所有节点，并且大于左子树的全部节点。

如下图所示，要删除58这个节点，就应该用59这个节点替换：

  1. private:
  2. //    寻找最小键值
  3.     Node* minimum(Node* node) {
  4.         if(node->left == NULL) {
  5.             return node;
  6.         }
  7.         return minimum(node->left);
  8.     }
  9. //    寻找最大键值
  10.     Node* maximum(Node* node) {
  11.         if(node->right == NULL) {
  12.             return node;
  13.         }
  14.         return maximum(node->right);
  15.     }
  16.     Node* remove_min(Node* node) {
  17.         if(node->left == NULL) {
  18.             Node* right = node->right;
  19.             delete node;
  20.             count--;
  21.             return right;
  22.         }
  23.         node->left = remove_min(node->left);
  24.         return node;
  25.     }
  27.     Node* remove_max(Node* node) {
  28.         if(node->right == NULL) {
  29.             Node* left = node->left;
  30.             delete node;
  31.             count--;
  32.             return left;
  33.         }
  34.         node->right = remove_max(node->right);
  35.         return node;
  36.     }
  37. //    删除掉以node为根的二分搜索树中键值为key的节点
  38. //    返回删除节点后新的二分搜索树的根
  39.     Node* remove(Node* node, Key key) {
  40.         if(node == NULL) {
  41.             return NULL;
  42.         }
  43.         if(key < node->key) {
  44.             node->left = remove(node->left, key);
  45.         } else if(key > node->key){
  46.             node->right = remove(node->right, key);
  47.         } else {
  48. //            key == node->key
  49.             if(node->left == NULL) {
  50.                 Node* right = node->right;
  51.                 delete node;
  52.                 count--;
  53.                 return right;
  54.             }
  55.             if(node->right == NULL) {
  56.                 Node *left = node->left;
  57.                 delete node;
  58.                 count--;
  59.                 return left;
  60.             }
  61. //            node->right != NULL && node->left != NULL
  62.             Node* successor = new Node(minimum(node->right));
  63.             count++;
  64. //            "count --" in "function remove_min(node->right)"
  65.             successor->right = remove_min(node->right);
  66.             successor->left = node->left;
  67.             delete node;
  68.             count--;
  69.             return successor;
  70.         }
  71.         return node;
  72.     }
  73. public:
  74. //    寻找最小键值
  75.     Key* minimum() {
  76.         if(this->count == 0) return NULL;
  77.         Node* min_node = this->minimum(this->root);
  78.         return &(min_node->key);
  79.     }
  81. //    寻找最大键值
  82.     Key* maximum() {
  83.         if(this->count == 0) return NULL;
  84.         Node* max_node = this->maximum(this->root);
  85.         return &(max_node->key);
  86.     }
  87.     void remove_min() {
  88.         if(this->root == NULL) {
  89.             return;
  90.         }
  91.         this->root = this->remove_min(this->root);
  92.     }
  94.     void remove_max() {
  95.         if(this->root == NULL) {
  96.             return;
  97.         }
  98.         this->root = this->remove_max(this->root);
  99.     }
  100.     void remove(Key key) {
  101.         this->root = remove(this->root, key);
  102.     }

3.6 数值运算：floor和ceil

floor和ceil分别是地板和天花板的意思。在一个数组中，对于指定元素n，如果数组中存在n，那么n的两个值就是它本身；如果不存在，那么分别是距离最近的小于指定元素的值 和 距离最近的大于指定元素的值。

  1. private:
  2.     Node* floor(Node* node, Key key) {
  3.         if(node == NULL) {
  4.             return NULL;
  5.         }
  7. //        key等于node->key：floor的结果就是node本身
  8.         if(node->key == key) {
  9.             return node;
  10.         }
  12. //        key小于node—>key：floor的结果肯定在node节点的左子树
  13.         if(node->key > key) {
  14.             return floor(node->left, key);
  15.         }
  17. //        key大于node->key：右子树可能存在比node->key大，但是比key小的节点
  18. //        如果存在上述情况，返回这个被选出来的节点
  19. //        否则，函数最后返回node本身
  20.         Node* tmp = floor(node->right, key);
  21.         if(tmp != NULL) {
  22.             return tmp;
  23.         }
  25.         return node;
  26.     }
  28.     Node* ceil(Node* node, Key key) {
  29.         if(node == NULL) {
  30.             return NULL;
  31.         }
  32.         if(node->key == key) {
  33.             return node;
  34.         }
  36.         if(node->key < key) {
  37.             return ceil(node->right, key);
  38.         }
  40.         Node* tmp = ceil(node->left, key);
  41.         if(tmp != NULL) {
  42.             return tmp;
  43.         }
  45.         return node;
  46.     }
  47. public:
  48.     Key* floor(Key key) {
  49.         Key* min_key = this->minimum();
  50.         if(this->isEmpty() || key < *min_key) {
  51.             return NULL;
  52.         }
  53. //        floor node
  54.         Node *node = floor(this->root, key);
  55.         return &(node->key);
  56.     }
  58.     Key* ceil(Key key) {
  59.         Key* max_key = this->maximum();
  60.         if(this->isEmpty() || key > *max_key) {
  61.             return NULL;
  62.         }
  63. //        ceil node
  64.         Node* node = ceil(this->root, key);
  65.         return &(node->key);
  66.     }

4. 代码测试

第 3 部分实现的测试代码地址：https://gist.github.com/dongyuanxin/759d16e1ce87913ad2f359d49d5f5016。

这是 Github 的 GIST，请自备梯子。

5. 拓展延伸

考虑一种数据类型，如果是基本有序的一组数据，一次insert进入二叉搜索树，那么，二叉搜索树就退化为了链表。此时，上述所有操作的时间复杂度都会退化为 \(O(log_2 N)\)。

为了避免这种情况，就有了红黑树等数据结构，来保证树的平衡性：左右子树的高度差小于等于 1。

6. 致谢

本篇博客是总结于慕课网的《学习算法思想 修炼编程内功》的笔记，强推强推强推。

二分搜索树的删除节点操作

 友情链接：直通硅谷 　点职佳 　北美留学生论坛

编程经验热门文章

  • Prometheus监控之SNMP Exporter介绍和数据展现
  • Intel 82599网卡异常挂死原因
  • 腾讯防水墙的分析识别与破解
  • 桌面应用自动化WinAppDriver入门
  • 文档在线预览（三）使用js前端实现word、excel、pdf、ppt 在线预览
  • 「教程」如何下载AcFun网站上的视频、A站视频下载工具
  • 基于Hi3559AV100的SVP(NNIE)开发整体流程
  • GBDT(梯度提升树)scikit-klearn中的参数说明及简汇
  • antd之RangePicker设置默认值方式
  • 决胜经典算法之插入排序

    • 编程经验推荐文章

  • wifi基础(一)：无线电波与WIFI信号干扰、衰减
  • 甲方扔给两个存在包名与类名均相同的Jar包，要在工程中同时使用怎么办？
  • 《花100块做个摸鱼小网站! 》第三篇—热搜表结构设计和热搜数据存储
  • Fluent Editor：一个基于 Quill 2.0 的富文本编辑器，功能强大、开箱即用！
  • 方法的三种调用形式
  • 《花100块做个摸鱼小网站! 》第二篇—后端应用搭建和完成第一个爬虫
  • 《熬夜整理》保姆级系列教程-玩转Wireshark抓包神器教程(4)-再识Wireshark - 北京-宏哥
  • 《软件性能测试分析与调优实践之路》(第2版) 读书笔记（二）总体介绍（下）-真正从性能分析与调优来看性能测试
  • 架构知识点（三）
  • 《花100块做个摸鱼小网站! 》第一篇—买云服务器和初始化环境

    • 本站QQ群：前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

    W3xue 的所有内容仅供测试，对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
    关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接（目前9元/月）请联系QQ：27243702 沸活量
    皖ICP备17017327号-2　皖公网安备34020702000426号