基于中序有序的二叉搜索树(下)

简介: 基于中序有序的二叉搜索树

kv模型

kv模型其实是一种Key/Value模型,也就是指根据key值去查找value,单这种模型的一个节点中不但要存储key值还需要村粗value。这种模型的使用场景也常见,比如检索一个学生在图书馆借了多少本书(将学号作为key值检索,因为key值和value存储在一起,所以只要搜索到key就可以获取到value)。二叉搜索树不但可以作为key模型,还可以添加一个模板参数作为key/value模型。

namespace KV
{
  template <class K,class V>
  struct BSTreeNode
  {
    BSTreeNode(const K& key,const V& value)
      :_left(nullptr)
      , _right(nullptr)
      , _key(key)
      ,_value(value)
    {}
    BSTreeNode<K,V>* _left;
    BSTreeNode<K,V>* _right;
    K _key;
    V _value;
  };
  template <class K,class V>
  struct BSTree
  {
    typedef BSTreeNode<K,V> Node;
    BSTree()
      :_root(nullptr)
    {}
    //插入节点
    bool Insert(const K& key,const V& value)
    {
      if (_root == nullptr)
      {
        _root = new Node(key,value);//BSTreeNode对象中存放key值 
      }
      else
      {
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
          parent = cur;
          if (cur->_key < key)
          {
            cur = cur->_right;
          }
          else if (cur->_key > key)
          {
            cur = cur->_left;
          }
          else//说明数字重复
            return false;
        }
        cur = new Node(key, value);
        //判断插入节点放在parent节点的左子树还是右子树
        if (parent->_key < key)
        {
          parent->_right = cur;
        }
        else
        {
          parent->_left = cur;
        }
      }
      return true;
    }
    bool InsertR(const K& key,const V& value)
    {
      return _InsertR(_root, key, value);
    }
    //中序遍历
    void InOrder()//因为外部取不到_root,所以这里套了一层调用函数
    {
      _InOrder(_root);
      std::cout << std::endl;
    }
    //查找
    Node* Find(const K& key)
    {
      Node* cur = _root;
      while (cur)
      {
        if (cur->_key < key)
        {
          cur = cur->_right;
        }
        else if (cur->_key > key)
        {
          cur = cur->_left;
        }
        else
          return cur;
      }
      return nullptr;
    }
    Node* FindR(const K& key)
    {
      return _FindR(_root, key);
    }
    bool Erase(const K& key)
    {
      Node* parent = nullptr;
      Node* cur = _root;
      //找到要删除的节点
      while (cur)
      {
        if (cur->_key < key)
        {
          parent = cur;
          cur = cur->_right;
        }
        else if (cur->_key > key)
        {
          parent = cur;
          cur = cur->_left;
        }
        else//说明找到要删除的节点了
        {
          //开始分析三种情况
          if (cur->_left == nullptr)//被删除节点左孩子为空。
          {
            if (cur == _root)//需要判断cur等于根节点的情况,否则else中parent空指针解引用了
            {
              _root = _root->_right;
            }
            else
            {
              if (parent->_left == cur)//确定cur是parent的左还是右,再进行“托孤”
                parent->_left = cur->_right;
              else
                parent->_right = cur->_right;
            }
            delete cur;
          }
          else if (cur->_right == nullptr)//被删除节点左孩子不为空,右孩子为空
          {
            if (cur == _root)
            {
              _root = _root->_left;
            }
            else
            {
              if (parent->_left == cur)
                parent->_left = cur->_left;
              else
                parent->_right = cur->_left;
            }
            delete cur;
          }
          else//被删除节点左右孩子均不为空
          {
            //左右孩子均不为空,就需要左子树的最大值或右子树的最小值选出来当新根
            Node* rightMin = cur->_right;//这里选用右树的最小值进行更换
            Node* rightMinParent = cur;
            while (rightMin->_left != nullptr)
            {
              rightMinParent = rightMin;
              rightMin = rightMin->_left;
            }
            //std::swap(cur->_key, rightMin->key);//用std的交换对自定义类型可能比较慢
            cur->_key = rightMin->_key;//还是用赋值好一点,即使是自定义类型,肯定有写赋值重载
            cur->_value = rightMin->_value;
            if (rightMinParent->_left == rightMin)//两种情况,第一种如图删除8,实际干掉9位置,需要将10的左连至9的右
              rightMinParent->_left = rightMin->_right;
            else if (rightMinParent->_right == rightMin)//第二种如图删除10,实际干掉14,需要将10的右连至14的右
              rightMinParent->_right = rightMin->_right;
            delete rightMin;
          }
          return true;
        }
      }
      return false;
    }
    bool EraseR(const K& key)
    {
      return _EarseR(_root, key);
    }
  private:
    Node* _root;
    void _InOrder(Node* _root)
    {
      if (_root == nullptr)
      {
        return;
      }
      _InOrder(_root->_left);
      std::cout << _root->_key << " "<<_root->_value;
      _InOrder(_root->_right);
    }
    Node* _FindR(Node* root, const K& key)
    {
      if (root == nullptr)
        return nullptr;
      if (root->_key < key)
      {
        return _FindR(root->_right, key);
      }
      else if (root->_key > key)
      {
        return _FindR(root->_left, key);
      }
      else
        return root;
    }
    bool _InsertR(Node*& root, const K& key, const V& value)//形参是root的引用
    {
      if (root == nullptr)
      {
        root = new Node(key,value);//因为root是父节点左/右孩子的别名,直接修改别名,链接关系存在,不用考虑父子节点连接关系
        return true;
      }
      if (root->_key < key)
        return _InsertR(root->_right, key,value);
      else if (root->_key > key)
        return _InsertR(root->_left, key,value);
      else
        return false;
    }
    bool _EarseR(Node*& root, const K& key)
    {
      if (root == nullptr)
      {
        return false;
      }
      if (root->_key < key)
        return _EarseR(root->_right, key);
      else if (root->_key > key)
        return _EarseR(root->_left, key);
      else//说明找到了要删除的节点,无需考虑root的父亲为空
      {
        Node* del = root;
        if (root->_left == nullptr)
          root = root->_right;
        else if (root->_right == nullptr)
          root = root->_left;
        else//root左右子树均不为空
        {
          Node* rightMin = root->_right;
          while (rightMin->_left != nullptr)//找到右树最小节点 
          {
            rightMin = rightMin->_left;
          }
          root->_key = rightMin->_key;
          root->_value = rightMin->_value;
          return _EarseR(root->_right, rightMin->_key);//return表示子树进行删除,结束掉递归
        }
        delete del;
        return true;
      }
    }
  };
}
void testKV1()//中英互译
{
  KV::BSTree<std::string, std::string> dic;
  dic.Insert("data", "数据");
  dic.Insert("algorithm", "算法");
  dic.Insert("map", "地图、映射");
  dic.Insert("Linux", "一款开源免费的操作系统");
  std::string str;
  while (std::cin >> str)
  {
    KV::BSTreeNode<std::string, std::string>* ret = dic.Find(str);
    if (ret != nullptr)
    {
      std::cout << "中文翻译:" << ret->_value << std::endl;
    }
    else
      std::cout << "查找失败!" << std::endl;
  }
}
void testKV2()//用于统计次数
{
  std::string arr[] = { "数学", "语文", "数学", "语文", "数学", 
    "数学", "英语","数学", "英语", "数学", "英语" };
  KV::BSTree<std::string, int> count;
  for (auto& e : arr)
  {
    KV::BSTreeNode<std::string, int>* ret = count.Find(e);
    if (ret != nullptr)
    {
      ret->_value++;
    }
    else
    {
      count.Insert(e,1);
    }
  }
  count.InOrder();
}

当然在现实中如果涉及到大量的数据,我想一般都是通过数据来存储的,毕竟如果不是强制定时将数据刷新到磁盘中的话,程序的数据都是在内存中的,一旦断电,就容易发生数据丢失。

相关文章
|
25天前
|
API 调度
二叉排序树
二叉排序树
11 0
|
6月前
|
数据格式
树结构练习——排序二叉树的中序遍历
树结构练习——排序二叉树的中序遍历
【剑指offer】-二叉搜索树的后序遍历序列-23/67
【剑指offer】-二叉搜索树的后序遍历序列-23/67
|
存储
基于中序有序的二叉搜索树(上)
基于中序有序的二叉搜索树
剑指offer 34. 二叉搜索树的后序遍历序列
剑指offer 34. 二叉搜索树的后序遍历序列
52 0
|
存储
LeetCode——1305. 两棵二叉搜索树中的所有元素
LeetCode——1305. 两棵二叉搜索树中的所有元素
51 0
LeetCode——1305. 两棵二叉搜索树中的所有元素
LeetCode 1305. 两棵二叉搜索树中的所有元素
给你 root1 和 root2 这两棵二叉搜索树。
61 0
|
算法 前端开发 程序员
二叉树的后序遍历序列
二叉树的后序遍历序列
二叉树的后序遍历序列
|
开发工具
15分钟精通二叉树,二叉树的先序,中序,后序,层次遍历顺序
🍀🍀🍀理解,掌握二叉树先序,中序,后序,层次四种遍历顺序
176 0
15分钟精通二叉树,二叉树的先序,中序,后序,层次遍历顺序