• 【c++】搜索二叉树的模拟实现

    搜索二叉树的模拟实现

    k模型完整代码

    1. #pragma once
    2. namespace hqj1
    3. {
    4.  template<class K>
    5.  struct SBTreeNode
    6.  {
    7.  public:
    8.   //这里直接用匿名对象作为缺省参数
    9.   SBTreeNode(const K& key = K())
    10.    :_key(key)
    11.    , _cleft(nullptr)
    12.    , _cright(nullptr)
    13.   {}
    14.  public:
    15.   K _key;
    16.   SBTreeNode* _cleft;
    17.   SBTreeNode* _cright;
    18.  };
    19.  
    20.  template<class K>
    21.  class SBTree
    22.  {
    23.   typedef SBTreeNode<K> Node;
    24.  public:
    25.   SBTree()
    26.    :_root(nullptr)
    27.   {}
    28.  
    29.   bool Insert(const K& key)
    30.   {
    31.    if (_root == nullptr)
    32.     _root = new Node(key);
    33.    else
    34.    {
    35.     Node* cur = _root;
    36.     Node* parent = nullptr;
    37.     //找到要插入的位置
    38.     while (cur)
    39.     {
    40.      parent = cur;
    41.      if (cur->_key < key)
    42.       cur = cur->_cright;
    43.      else if (cur->_key > key)
    44.       cur = cur->_cleft;
    45.      else
    46.       return false;
    47.     }
    48.  
    49.     //连接
    50.     cur = new Node(key);
    51.     if (parent->_key < key)
    52.      parent->_cright = cur;
    53.     else
    54.      parent->_cleft = cur;
    55.    }
    56.    return true;
    57.   }
    58.  
    59.   Node* Find(const K& key)
    60.   {
    61.    Node* cur = _root;
    62.    while (cur)
    63.    {
    64.     if (key > cur->_key)
    65.      cur = cur->_cright;
    66.     else if (key < cur->_key)
    67.      cur = cur->_cleft;
    68.     else
    69.      break;
    70.    }
    71.    return cur;
    72.   }
    73.  
    74.   bool Erase(const K& key)
    75.   {
    76.    if (_root == nullptr)
    77.     return false;
    78.    else
    79.    {
    80.     //找出要删除元素的位置,复用查找函数也行
    81.     Node* cur = _root;
    82.     Node* parent = nullptr;
    83.     while (cur)
    84.     {
    85.      if (cur->_key == key)
    86.       break;
    87.  
    88.      parent = cur;
    89.      if (key > cur->_key)
    90.       cur = cur->_cright;
    91.      else if (key < cur->_key)
    92.       cur = cur->_cleft;
    93.     }
    94.  
    95.     //对根进行特判
    96.     if (parent == nullptr)
    97.     {
    98.      if (cur->_cleft == nullptr && cur->_cright == nullptr)
    99.      {
    100.       delete _root;
    101.       _root = nullptr;
    102.      }
    103.      else if (cur->_cleft == nullptr)
    104.       _root = _root->_cright;
    105.      else
    106.       _root = _root->_cleft;
    107.  
    108.      return true;
    109.     }
    110.  
    111.     //对不同情况进行处理
    112.     //第一种是要删除的元素不在树内
    113.     if (cur == nullptr)
    114.      return false;
    115.     else if (cur->_cleft == nullptr && cur->_cleft == cur->_cright)
    116.     {
    117.      //要删除的元素是叶子节点，直接删
    118.      if (cur == parent->_cleft)
    119.       parent->_cleft = nullptr;
    120.      else
    121.       parent->_cright = nullptr;
    122.  
    123.      delete cur;
    124.     }
    125.     else if (cur->_cleft == nullptr)
    126.     {
    127.      //有右子树但没有左子树
    128.      if (cur == parent->_cleft)
    129.       parent->_cleft = cur->_cright;
    130.      else
    131.       parent->_cright = cur->_cright;
    132.  
    133.      delete cur;
    134.     }
    135.     else if (cur->_cright == nullptr)
    136.     {
    137.      //有左子树但没有右子树
    138.      if (cur == parent->_cleft)
    139.      {
    140.       parent->_cleft = cur->_cleft;
    141.      }
    142.      else
    143.      {
    144.       parent->_cright = cur->_cleft;
    145.      }
    146.      delete cur;
    147.     }
    148.     else
    149.     {
    150.      //既有左子树又有右子树
    151.      //找左子树的最右，或者找右子树的最左节点来替换掉当前要删除的节点
    152.      Node* curRL = cur->_cright;
    153.      Node* parentRL = cur;
    154.      while (curRL->_cleft)
    155.      {
    156.       parentRL = curRL;
    157.       curRL = curRL->_cleft;
    158.      }
    159.      //交换要删除的值和要删除节点的右树最左节点的值
    160.      swap(cur->_key, curRL->_key);
    161.      //判断要删除的节点在其父节点的位置
    162.      //操控父节点指针
    163.      //有一个性质：右子树中的最左节点一定没有左子树，我们让父节点连接要删除节点的右子树就行
    164.      if (curRL == parentRL->_cleft)
    165.       parentRL->_cleft = curRL->_cright;
    166.      else
    167.       parentRL->_cright = curRL->_cright;
    168.      delete curRL;
    169.      curRL = nullptr;
    170.     }
    171.     return true;
    172.    }
    173.   }
    174.  
    175.   void InOrder()
    176.   {
    177.    _InOrder(_root);
    178.   }
    179.  private:
    180.   void _InOrder(const Node* root)
    181.   {
    182.    if (root == nullptr)
    183.     return;
    184.  
    185.    _InOrder(root->_cleft);
    186.    cout << root->_key << ' ';
    187.    _InOrder(root->_cright);
    188.   }
    189.   Node* _root;
    190.  };
    191. }

    k模型节点的定义

    • 这是一个模板类，模板类型为K，代表着关键词

    • 成员为：关键词、左子树指针、右子树指针

    • 构造函数的参数为K类型的对象，缺省参数为匿名对象（K（）），使我们代码的通用性增强

    1. template<class K>
    2.  struct SBTreeNode
    3.  {
    4.  public:
    5.   //这里直接用匿名对象作为缺省参数
    6.   SBTreeNode(const K& key = K())
    7.    :_key(key)
    8.    , _cleft(nullptr)
    9.    , _cright(nullptr)
    10.   {}
    11.  public:
    12.   K _key;
    13.   SBTreeNode* _cleft;
    14.   SBTreeNode* _cright;
    15.  };

    k模型二叉搜索树类的实现

    • 首先将节点类类型重定义为Node方便我们后续的使用

    • 成员函数为插入、删除、查找、中序遍历

    • 私有成员为节点指针_root

    1. template<class K>
    2.  class SBTree
    3.  {
    4.   typedef SBTreeNode<K> Node;
    5.  public:
    6.   SBTree()
    7.    :_root(nullptr)
    8.   {}
    9.  
    10.   bool Insert(const K& key)
    11.   {
    12.    if (_root == nullptr)
    13.     _root = new Node(key);
    14.    else
    15.    {
    16.     Node* cur = _root;
    17.     Node* parent = nullptr;
    18.     //找到要插入的位置
    19.     while (cur)
    20.     {
    21.      parent = cur;
    22.      if (cur->_key < key)
    23.       cur = cur->_cright;
    24.      else if (cur->_key > key)
    25.       cur = cur->_cleft;
    26.      else
    27.       return false;
    28.     }
    29.  
    30.     //连接
    31.     cur = new Node(key);
    32.     if (parent->_key < key)
    33.      parent->_cright = cur;
    34.     else
    35.      parent->_cleft = cur;
    36.    }
    37.    return true;
    38.   }
    39.  
    40.   Node* Find(const K& key)
    41.   {
    42.    Node* cur = _root;
    43.    while (cur)
    44.    {
    45.     if (key > cur->_key)
    46.      cur = cur->_cright;
    47.     else if (key < cur->_key)
    48.      cur = cur->_cleft;
    49.     else
    50.      break;
    51.    }
    52.    return cur;
    53.   }
    54.  
    55.   bool Erase(const K& key)
    56.   {
    57.    if (_root == nullptr)
    58.     return false;
    59.    else
    60.    {
    61.     //找出要删除元素的位置,复用查找函数也行
    62.     Node* cur = _root;
    63.     Node* parent = nullptr;
    64.     while (cur)
    65.     {
    66.      if (cur->_key == key)
    67.       break;
    68.  
    69.      parent = cur;
    70.      if (key > cur->_key)
    71.       cur = cur->_cright;
    72.      else if (key < cur->_key)
    73.       cur = cur->_cleft;
    74.     }
    75.  
    76.     //对根进行特判
    77.     if (parent == nullptr)
    78.     {
    79.      if (cur->_cleft == nullptr && cur->_cright == nullptr)
    80.      {
    81.       delete _root;
    82.       _root = nullptr;
    83.      }
    84.      else if (cur->_cleft == nullptr)
    85.       _root = _root->_cright;
    86.      else
    87.       _root = _root->_cleft;
    88.  
    89.      return true;
    90.     }
    91.  
    92.     //对不同情况进行处理
    93.     //第一种是要删除的元素不在树内
    94.     if (cur == nullptr)
    95.      return false;
    96.     else if (cur->_cleft == nullptr && cur->_cleft == cur->_cright)
    97.     {
    98.      //要删除的元素是叶子节点，直接删
    99.      if (cur == parent->_cleft)
    100.       parent->_cleft = nullptr;
    101.      else
    102.       parent->_cright = nullptr;
    103.  
    104.      delete cur;
    105.     }
    106.     else if (cur->_cleft == nullptr)
    107.     {
    108.      //有右子树但没有左子树
    109.      if (cur == parent->_cleft)
    110.       parent->_cleft = cur->_cright;
    111.      else
    112.       parent->_cright = cur->_cright;
    113.  
    114.      delete cur;
    115.     }
    116.     else if (cur->_cright == nullptr)
    117.     {
    118.      //有左子树但没有右子树
    119.      if (cur == parent->_cleft)
    120.      {
    121.       parent->_cleft = cur->_cleft;
    122.      }
    123.      else
    124.      {
    125.       parent->_cright = cur->_cleft;
    126.      }
    127.      delete cur;
    128.     }
    129.     else
    130.     {
    131.      //既有左子树又有右子树
    132.      //找左子树的最右，或者找右子树的最左节点来替换掉当前要删除的节点
    133.      Node* curRL = cur->_cright;
    134.      Node* parentRL = cur;
    135.      while (curRL->_cleft)
    136.      {
    137.       parentRL = curRL;
    138.       curRL = curRL->_cleft;
    139.      }
    140.      //交换要删除的值和要删除节点的右树最左节点的值
    141.      swap(cur->_key, curRL->_key);
    142.      //判断要删除的节点在其父节点的位置
    143.      //操控父节点指针
    144.      //有一个性质：右子树中的最左节点一定没有左子树，我们让父节点连接要删除节点的右子树就行
    145.      if (curRL == parentRL->_cleft)
    146.       parentRL->_cleft = curRL->_cright;
    147.      else
    148.       parentRL->_cright = curRL->_cright;
    149.      delete curRL;
    150.      curRL = nullptr;
    151.     }
    152.     return true;
    153.    }
    154.   }
    155.  
    156.   void InOrder()
    157.   {
    158.    _InOrder(_root);
    159.   }
    160.  private:
    161.   void _InOrder(const Node* root)
    162.   {
    163.    if (root == nullptr)
    164.     return;
    165.  
    166.    _InOrder(root->_cleft);
    167.    cout << root->_key << ' ';
    168.    _InOrder(root->_cright);
    169.   }
    170.   Node* _root;
    171.  };

    构造函数

    • 将_root指针初始化为空指针即可

    1. SBTree()
    2.    :_root(nullptr)
    3.   {}

    Insert函数

    • Insert函数的参数为要插入的关键字

    • 首先进行判空，如果_root为空，说明此时还没有节点，我们直接给_root赋值就行

    • 如果不为空，那么就需要先找到要插入的位置，我们定义cur和parent两个节点指针，cur负责寻找要插入的位置，parent负责记录cur的父亲节点，由于搜索二叉树的特性，当key值大于cur所指向节点的_key值说明要插入的位置再cur节点的右子树中，反之则在cur的左子树中，通过循环来达到目的，更新cur的同时要更新parent

    • 如果遇到cur的_key和key相等的情况说明插入失败，其余情况皆为插入成功

    1. bool Insert(const K& key)
    2.   {
    3.    if (_root == nullptr)
    4.     _root = new Node(key);
    5.    else
    6.    {
    7.     Node* cur = _root;
    8.     Node* parent = nullptr;
    9.     //找到要插入的位置
    10.     while (cur)
    11.     {
    12.      if (cur->_key == key)
    13.       return false;
    14.  
    15.      parent = cur;
    16.      if (cur->_key < key)
    17.       cur = cur->_cright;
    18.      else if (cur->_key > key)
    19.       cur = cur->_cleft;
    20.     }
    21.  
    22.     //连接
    23.     cur = new Node(key);
    24.     if (parent->_key < key)
    25.      parent->_cright = cur;
    26.     else
    27.      parent->_cleft = cur;
    28.    }
    29.    return true;
    30.   }

    Find函数

    • Find的参数为要查找的关键字

    • 我们定义cur指针来找到目标节点位置，当key > cur->_key时cur要往其右子树寻找，反之则去其左子树寻找，当相等时或者cur指向空（意味着没找到）结束循环，返回cur

    1.   Node* Find(const K& key)
    2.   {
    3.    Node* cur = _root;
    4.    while (cur)
    5.    {
    6.     if (key > cur->_key)
    7.      cur = cur->_cright;
    8.     else if (key < cur->_key)
    9.      cur = cur->_cleft;
    10.     else
    11.      break;
    12.    }
    13.    return cur;
    14.   }
    15.  
    16.

    Erase函数

    • 该函数的参数为要删除的关键字

    • 当要操作的树为空树时，直接返回失败

    • 不是空树则首先找出要删除节点的位置，同样是定义cur和parent节点指针，cur负责找出要删除节点的位置，parent负责记录cur节点的父节点。利用循环结构实现，循环的结束条件为cur为空指针或者找到对应位置，若为空则说明要删除节点不在树内，直接返回失败

    • 找到之后首先判断是否要操作_root指针，当parent为空时说明要操作根节点，对于根节点的不同类型进行对应的操作1. 如果整棵树只有一个节点，直接删除根节点，并将根节点置为空。2. 如果根节点没有左子树，则用右子树的根节点作为新的整棵树的根节点。3. 如果根节点没有右子树，则用左子树的根节点作为新的整棵树的根节点。4. 如果根节点既有左子树又有右子树，则当作普通节点处理（见下一点的第4小点）

    • 处理完根节点问题后就改判断要删除的节点是哪种类型：1. 删除节点是叶子结点，那么我们直接删除该节点并更新其父亲节点的指针（判断要删除节点是其父情节点的左子树还是右子树，操作对应的指针）2. 有右子树但没有左子树，让其父亲的对应指针指向其右子树，并删除当前节点。3. 有左子树但没有右子树，让其父亲的对应指针指向其左子树，并删除该节点4. 既有左子树又有右子树，定义curRL负责寻找其右子树的最左节点（也就是右子树的最小节点）或者定义curLR左子树的最右节点（也就是左子树的最大节点），定义parentRL记录其父亲节点，与当前节点（cur）的值进行交换，交换完后令parentRL的对应指针指向curRL的右子树，并删除curRL所指向的节点。

    • 所有过程走完后返回状态（成功或者失败）

    1. bool Erase(const K& key)
    2.   {
    3.    if (_root == nullptr)
    4.     return false;
    5.    else
    6.    {
    7.     //找出要删除元素的位置,复用查找函数也行
    8.     Node* cur = _root;
    9.     Node* parent = nullptr;
    10.     while (cur)
    11.     {
    12.      if (cur->_key == key)
    13.       break;
    14.  
    15.      parent = cur;
    16.      if (key > cur->_key)
    17.       cur = cur->_cright;
    18.      else if (key < cur->_key)
    19.       cur = cur->_cleft;
    20.     }
    21.  
    22.     //对根进行特判
    23.     if (parent == nullptr)
    24.     {
    25.      if (cur->_cleft == nullptr && cur->_cright == nullptr)
    26.      {
    27.       delete _root;
    28.       _root = nullptr;
    29.      }
    30.      else if (cur->_cleft == nullptr)
    31.       _root = _root->_cright;
    32.      else
    33.       _root = _root->_cleft;
    34.  
    35.      return true;
    36.     }
    37.  
    38.     //对不同情况进行处理
    39.     //第一种是要删除的元素不在树内
    40.     if (cur == nullptr)
    41.      return false;
    42.     else if (cur->_cleft == nullptr && cur->_cleft == cur->_cright)
    43.     {
    44.      //要删除的元素是叶子节点，直接删
    45.      if (cur == parent->_cleft)
    46.       parent->_cleft = nullptr;
    47.      else
    48.       parent->_cright = nullptr;
    49.  
    50.      delete cur;
    51.     }
    52.     else if (cur->_cleft == nullptr)
    53.     {
    54.      //有右子树但没有左子树
    55.      if (cur == parent->_cleft)
    56.       parent->_cleft = cur->_cright;
    57.      else
    58.       parent->_cright = cur->_cright;
    59.  
    60.      delete cur;
    61.     }
    62.     else if (cur->_cright == nullptr)
    63.     {
    64.      //有左子树但没有右子树
    65.      if (cur == parent->_cleft)
    66.      {
    67.       parent->_cleft = cur->_cleft;
    68.      }
    69.      else
    70.      {
    71.       parent->_cright = cur->_cleft;
    72.      }
    73.      delete cur;
    74.     }
    75.     else
    76.     {
    77.      //既有左子树又有右子树
    78.      //找左子树的最右，或者找右子树的最左节点来替换掉当前要删除的节点
    79.      Node* curRL = cur->_cright;
    80.      Node* parentRL = cur;
    81.      while (curRL->_cleft)
    82.      {
    83.       parentRL = curRL;
    84.       curRL = curRL->_cleft;
    85.      }
    86.      //交换要删除的值和要删除节点的右树最左节点的值
    87.      swap(cur->_key, curRL->_key);
    88.      //判断要删除的节点在其父节点的位置
    89.      //操控父节点指针
    90.      //有一个性质：右子树中的最左节点一定没有左子树，我们让父节点连接要删除节点的右子树就行
    91.      if (curRL == parentRL->_cleft)
    92.       parentRL->_cleft = curRL->_cright;
    93.      else
    94.       parentRL->_cright = curRL->_cright;
    95.      delete curRL;
    96.      curRL = nullptr;
    97.     }
    98.     return true;
    99.    }
    100.   }

    kv模型完整代码

    1. #pragma once
    2. namespace hqj2
    3. {
    4.  template<class K, class V>
    5.  struct SBTreeNode
    6.  {
    7.  public:
    8.   SBTreeNode(const K& key = K(), const V& value = V())
    9.    :_cleft(nullptr), _cright(nullptr)
    10.    , _key(key)
    11.    , _value(value)
    12.   {}
    13.  public:
    14.   SBTreeNode* _cleft;
    15.   SBTreeNode* _cright;
    16.   K _key;
    17.   V _value;
    18.  };
    19.  
    20.  template<class K, class V>
    21.  class SBTree
    22.  {
    23.   typedef SBTreeNode<K, V> Node;
    24.  public:
    25.   SBTree()
    26.    :_root(nullptr)
    27.   {}
    28.  public:
    29.   bool Insert(const K& key, const V& value)
    30.   {
    31.    if (_root == nullptr)
    32.     _root = new Node(key, value);
    33.    else
    34.    {
    35.     Node* cur = _root;
    36.     Node* parent = nullptr;
    37.  
    38.     while (cur)
    39.     {
    40.      if (cur->_key == key)
    41.       return false;
    42.      parent = cur;
    43.      if (key > cur->_key)
    44.       cur = cur->_cright;
    45.      else if (key < cur->_key)
    46.       cur = cur->_cleft;
    47.     }
    48.  
    49.     cur = new Node(key, value);
    50.     if (cur == parent->_cleft)
    51.      parent->_cleft = cur;
    52.     else
    53.      parent->_cright = cur;
    54.    }
    55.    return true;
    56.   }
    57.  
    58.   void InOrder()
    59.   {
    60.    _Inorder(_root);
    61.   }
    62.  
    63.   Node*& Find(const K& key)
    64.   {
    65.    Node* cur = _root;
    66.  
    67.    while (cur)
    68.    {
    69.     if (key > cur->_key)
    70.      cur = cur->_cright;
    71.     else if (key < cur->_key)
    72.      cur = cur->_cleft;
    73.     else
    74.      break;
    75.    }
    76.  
    77.    return cur;
    78.   }
    79.  
    80.   bool Erase(const K& key)
    81.   {
    82.    if (_root == nullptr)
    83.     return false;
    84.  
    85.    Node* cur = _root;
    86.    Node* parent = nullptr;
    87.  
    88.    while (cur)
    89.    {
    90.     if (cur->_key == key)
    91.      break;
    92.  
    93.     parent = cur;
    94.     if (key > cur->_key)
    95.      cur = cur->_cright;
    96.     else if (key < cur->_key)
    97.      cur = cur->_cleft;
    98.    }
    99.  
    100.    if (parent == nullptr)
    101.    {
    102.     if (cur->_cleft == nullptr && cur->_cright == nullptr)
    103.     {
    104.      delete _root;
    105.      _root = nullptr;
    106.     }
    107.     else if (cur->_cleft == nullptr)
    108.      _root = _root->_cright;
    109.     else
    110.      _root = _root->_cleft;
    111.     return true;
    112.    }
    113.  
    114.    if (cur->_cleft == nullptr && cur->_cright == nullptr)
    115.    {
    116.     if (cur == parent->_cleft)
    117.      parent->_cleft = nullptr;
    118.     else
    119.      parent->_cright = nullptr;
    120.  
    121.     delete cur;
    122.    }
    123.    else if (cur->_cleft == nullptr)
    124.    {
    125.     if (cur == parent->_cleft)
    126.      parent->_cleft = cur->_cright;
    127.     else
    128.      parent->_cright = cur->_cright;
    129.  
    130.     delete cur;
    131.    }
    132.    else if (cur->_cright == nullptr)
    133.    {
    134.     if (cur == parent->_cleft)
    135.      parent->_cleft = cur->_cleft;
    136.     else
    137.      parent->_cright = cur->_cleft;
    138.    }
    139.    else
    140.    {
    141.     Node* parntRL = nullptr;
    142.     Node* curRL = cur->_cright;
    143.  
    144.     while (curRL->_cleft != nullptr)
    145.     {
    146.      parntRL = curRL;
    147.      curRL = curRL->_cleft;
    148.     }
    149.  
    150.     swap(curRL->_key, cur->_key);
    151.  
    152.     if (curRL == parntRL->_cleft)
    153.      parntRL->_cleft = curRL->_cright;
    154.     else
    155.      parntRL->_cright = curRL->_cright;
    156.     delete curRL;
    157.    }
    158.    return true;
    159.   }
    160.  private:
    161.   void _Inorder(const Node* root)
    162.   {
    163.    if (root == nullptr)
    164.     return;
    165.    _Inorder(root->_cleft);
    166.    cout << root->_key << ' ' << root->_value << ' ' << endl;
    167.    _Inorder(root->_cright);
    168.   }
    169.  
    170.   Node* _root;
    171.  };
    172. }

    kv模型搜索二叉树的定义

    • 是模板类，模板参数是K和V

    • 成员函数和k模型一模一样

    1. template<class K, class V>
    2.  class SBTree
    3.  {
    4.   typedef SBTreeNode<K, V> Node;
    5.  public:
    6.   SBTree()
    7.    :_root(nullptr)
    8.   {}
    9.  public:
    10.   bool Insert(const K& key, const V& value)
    11.   {
    12.    if (_root == nullptr)
    13.     _root = new Node(key, value);
    14.    else
    15.    {
    16.     Node* cur = _root;
    17.     Node* parent = nullptr;
    18.  
    19.     while (cur)
    20.     {
    21.      if (cur->_key == key)
    22.       return false;
    23.      parent = cur;
    24.      if (key > cur->_key)
    25.       cur = cur->_cright;
    26.      else if (key < cur->_key)
    27.       cur = cur->_cleft;
    28.     }
    29.  
    30.     cur = new Node(key, value);
    31.     if (cur == parent->_cleft)
    32.      parent->_cleft = cur;
    33.     else
    34.      parent->_cright = cur;
    35.    }
    36.    return true;
    37.   }
    38.  
    39.   void InOrder()
    40.   {
    41.    _Inorder(_root);
    42.   }
    43.  
    44.   Node*& Find(const K& key)
    45.   {
    46.    Node* cur = _root;
    47.  
    48.    while (cur)
    49.    {
    50.     if (key > cur->_key)
    51.      cur = cur->_cright;
    52.     else if (key < cur->_key)
    53.      cur = cur->_cleft;
    54.     else
    55.      break;
    56.    }
    57.  
    58.    return cur;
    59.   }
    60.  
    61.   bool Erase(const K& key)
    62.   {
    63.    if (_root == nullptr)
    64.     return false;
    65.  
    66.    Node* cur = _root;
    67.    Node* parent = nullptr;
    68.  
    69.    while (cur)
    70.    {
    71.     if (cur->_key == key)
    72.      break;
    73.  
    74.     parent = cur;
    75.     if (key > cur->_key)
    76.      cur = cur->_cright;
    77.     else if (key < cur->_key)
    78.      cur = cur->_cleft;
    79.    }
    80.  
    81.    if (parent == nullptr)
    82.    {
    83.     if (cur->_cleft == nullptr && cur->_cright == nullptr)
    84.     {
    85.      delete _root;
    86.      _root = nullptr;
    87.     }
    88.     else if (cur->_cleft == nullptr)
    89.      _root = _root->_cright;
    90.     else
    91.      _root = _root->_cleft;
    92.     return true;
    93.    }
    94.  
    95.    if (cur->_cleft == nullptr && cur->_cright == nullptr)
    96.    {
    97.     if (cur == parent->_cleft)
    98.      parent->_cleft = nullptr;
    99.     else
    100.      parent->_cright = nullptr;
    101.  
    102.     delete cur;
    103.    }
    104.    else if (cur->_cleft == nullptr)
    105.    {
    106.     if (cur == parent->_cleft)
    107.      parent->_cleft = cur->_cright;
    108.     else
    109.      parent->_cright = cur->_cright;
    110.  
    111.     delete cur;
    112.    }
    113.    else if (cur->_cright == nullptr)
    114.    {
    115.     if (cur == parent->_cleft)
    116.      parent->_cleft = cur->_cleft;
    117.     else
    118.      parent->_cright = cur->_cleft;
    119.    }
    120.    else
    121.    {
    122.     Node* parntRL = nullptr;
    123.     Node* curRL = cur->_cright;
    124.  
    125.     while (curRL->_cleft != nullptr)
    126.     {
    127.      parntRL = curRL;
    128.      curRL = curRL->_cleft;
    129.     }
    130.  
    131.     swap(curRL->_key, cur->_key);
    132.  
    133.     if (curRL == parntRL->_cleft)
    134.      parntRL->_cleft = curRL->_cright;
    135.     else
    136.      parntRL->_cright = curRL->_cright;
    137.     delete curRL;
    138.    }
    139.    return true;
    140.   }
    141.  private:
    142.   void _Inorder(const Node* root)
    143.   {
    144.    if (root == nullptr)
    145.     return;
    146.    _Inorder(root->_cleft);
    147.    cout << root->_key << ' ' << root->_value << ' ' << endl;
    148.    _Inorder(root->_cright);
    149.   }
    150.  
    151.   Node* _root;
    152.  };

    kv模型节点的定义

    • 节点是模板类，模板参数为K和V

    • 成员为左子树指针、右子树指针、关键字、所对应的值

    • 依然以匿名对象作为缺省参数，使得我们程序更加通用

    1. template<class K, class V>
    2.  struct SBTreeNode
    3.  {
    4.  public:
    5.   SBTreeNode(const K& key = K(), const V& value = V())
    6.    :_cleft(nullptr), _cright(nullptr)
    7.    , _key(key)
    8.    , _value(value)
    9.   {}
    10.  public:
    11.   SBTreeNode* _cleft;
    12.   SBTreeNode* _cright;
    13.   K _key;
    14.   V _value;
    15.  };

    Insert函数

    • 该函数参数为关键字、值

    • 首先判断该树有无节点，无节点则直接给_root赋值，有节点则先找要插入的位置，插入的同时改变其父亲节点所对应的指针

    • 返回值为插入状态

    1. bool Insert(const K& key, const V& value)
    2.   {
    3.    if (_root == nullptr)
    4.     _root = new Node(key, value);
    5.    else
    6.    {
    7.     Node* cur = _root;
    8.     Node* parent = nullptr;
    9.  
    10.     while (cur)
    11.     {
    12.      if (cur->_key == key)
    13.       return false;
    14.      parent = cur;
    15.      if (key > cur->_key)
    16.       cur = cur->_cright;
    17.      else if (key < cur->_key)
    18.       cur = cur->_cleft;
    19.     }
    20.  
    21.     cur = new Node(key, value);
    22.     if (cur == parent->_cleft)
    23.      parent->_cleft = cur;
    24.     else
    25.      parent->_cright = cur;
    26.    }
    27.    return true;
    28.   }

    Find函数

    • 和k模型的一模一样，不做赘述

    1. Node*& Find(const K& key)
    2.   {
    3.    Node* cur = _root;
    4.  
    5.    while (cur)
    6.    {
    7.     if (key > cur->_key)
    8.      cur = cur->_cright;
    9.     else if (key < cur->_key)
    10.      cur = cur->_cleft;
    11.     else
    12.      break;
    13.    }
    14.  
    15.    return cur;
    16.   }

    Erase函数

    • 和k模型的一模一样，不做赘述

    1.  bool Erase(const K& key)
    2.   {
    3.    if (_root == nullptr)
    4.     return false;
    5.  
    6.    Node* cur = _root;
    7.    Node* parent = nullptr;
    8.  
    9.    while (cur)
    10.    {
    11.     if (cur->_key == key)
    12.      break;
    13.  
    14.     parent = cur;
    15.     if (key > cur->_key)
    16.      cur = cur->_cright;
    17.     else if (key < cur->_key)
    18.      cur = cur->_cleft;
    19.    }
    20.  
    21.    if (parent == nullptr)
    22.    {
    23.     if (cur->_cleft == nullptr && cur->_cright == nullptr)
    24.     {
    25.      delete _root;
    26.      _root = nullptr;
    27.     }
    28.     else if (cur->_cleft == nullptr)
    29.      _root = _root->_cright;
    30.     else
    31.      _root = _root->_cleft;
    32.     return true;
    33.    }
    34.  
    35.    if (cur->_cleft == nullptr && cur->_cright == nullptr)
    36.    {
    37.     if (cur == parent->_cleft)
    38.      parent->_cleft = nullptr;
    39.     else
    40.      parent->_cright = nullptr;
    41.  
    42.     delete cur;
    43.    }
    44.    else if (cur->_cleft == nullptr)
    45.    {
    46.     if (cur == parent->_cleft)
    47.      parent->_cleft = cur->_cright;
    48.     else
    49.      parent->_cright = cur->_cright;
    50.  
    51.     delete cur;
    52.    }
    53.    else if (cur->_cright == nullptr)
    54.    {
    55.     if (cur == parent->_cleft)
    56.      parent->_cleft = cur->_cleft;
    57.     else
    58.      parent->_cright = cur->_cleft;
    59.    }
    60.    else
    61.    {
    62.     Node* parntRL = nullptr;
    63.     Node* curRL = cur->_cright;
    64.  
    65.     while (curRL->_cleft != nullptr)
    66.     {
    67.      parntRL = curRL;
    68.      curRL = curRL->_cleft;
    69.     }
    70.  
    71.     swap(curRL->_key, cur->_key);
    72.  
    73.     if (curRL == parntRL->_cleft)
    74.      parntRL->_cleft = curRL->_cright;
    75.     else
    76.      parntRL->_cright = curRL->_cright;
    77.     delete curRL;
    78.    }
    79.    return true;
    80.   }
  • 相关阅读:
    Pytorch编程基础
    公司实战 ElasticSearch+Kafka+Redis+MySQL
    systemverilog学习 --- 随机化（1）
    15-JavaSE基础巩固练习：多态、接口、抽象类的综合练习
    vscode使用ssh连接远程Ubuntu服务器（记录）
    辅助知识-第2 章 项目合同管理
    基于springboot停车位管理系统【附源码】开源项目
    【含2023java面试题】深入解析JVM调优：解决OutOfMemoryError、内存泄露、线程死锁、锁争用和高CPU消耗问题
    解决win11更新后，文件夹打不开的bug
    Spring Boot集成Minio插件快速入门
  • 原文地址：https://blog.csdn.net/ZHENGZJM/article/details/134278789