从C语言到C++_24(二叉搜索树)概念+完整代码实现+笔试题（下）-阿里云开发者社区

从C语言到C++_24(二叉搜索树)概念+完整代码实现+笔试题（中）：https://developer.aliyun.com/article/1521942

3. 搜索二叉树的应用

3.1 K 模型

K模型，即只有 key 作为关键码，我们上面写的就是K模型，

结构中只需存储 key 即可，关键码就是需要搜索到的值。

举个例子：对于单词 word，我们需要判断该单词是否拼写正确

以单词集合中的每个单词作为 key，构建一个搜索二叉树。

在二叉树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

3.2 KV 模型

KV模型，每一个关键码 key，都有与之对应的值 Value，即 <Key, Value> 的键值对。

这就像 Python 中的 dict 字典类型一样，key 和 value 对应。

这在生活中也是非常常见的，比如英汉词典就是英文与中文的对应关系，通过英文可以快读检索到对应的中文，英文单词也可以与其对应的中文构建出一种键值对：

<string, string> 即 <word, chinese>

再比如统计水果次数，就构建出了一种键值对：

<string, int> 即 <水果, count>

直接放用于测试的代码：

//二叉搜索树的KV结构
namespace KeyValue
{
  //定义两个类模板参数K、V
  template<class K, class V>
  class BSTreeNode
  {
  public:
    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; //存放了两个类型的数据，相比较与K模型
    V _value;
  };
 
  //同样的，定义两个类模板参数K、V
  //搜索二叉树依旧是按照K的数据进行排序，和V无关
  template<class K, class V>
  class BSTree
  {
    typedef BSTreeNode<K, V> Node;
  public:
    bool Insert(const K& key, const V& value)
    {
      if (_root == nullptr)
      {
        _root = new Node(key, value);
        return true;
      }
 
      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
        {
          return false;
        }
      }
 
      cur = new Node(key, value);
      if (parent->_key < key)
      {
        parent->_right = cur;
      }
      else
      {
        parent->_left = cur;
      }
 
      return true;
    }
 
    //查找只和数据_key有关，与数据_value无关
    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;
    }
 
    //删除只和数据_key有关，与数据_value无关
    bool Erase(const K& key)
    {
      //... 和K模型一样
      return true;
    }
 
    void InOrder()
    {
      _InOrder(_root);
      cout << endl;
    }
  protected:
    void _InOrder(Node* root)
    {
      if (root == nullptr)
      {
        return;
      }
 
      _InOrder(root->_left);
      cout << root->_key << ":" << root->_value << endl;
      _InOrder(root->_right);
    }
 
    Node* _root = nullptr;
  };
 
  void TestBSTree1()
  {
    BSTree<string, string> dict; // 字典树，如果所有单词都在里面就能很准确查找
    dict.Insert("sort", "排序");
    dict.Insert("left", "左边");
    dict.Insert("right", "右边");
    dict.Insert("string", "字符串");
    dict.Insert("insert", "插入");
    string str;
    while (cin >> str) // Crtl+z+换行结束，或者Crtl+c结束
    {
      BSTreeNode<string, string>* ret = dict.Find(str);
      if (ret)
      {
        cout << "对应的中文:" << ret->_value << endl;
      }
      else
      {
        cout << "对应的中文->无此单词" << endl;
      }
    }
  }
 
  void TestBSTree2() // 统计水果出现的次数
  {
    string arr[] = { "香蕉", "苹果", "香蕉", "草莓", "香蕉", "苹果", "苹果", "苹果" };
 
    BSTree<string, int> countTree;
    for (auto& str : arr)
    {
      //BSTreeNode<string, int>* ret = countTree.Find(str);
      auto ret = countTree.Find(str);
      if (ret)
      {
        ret->_value++;
      }
      else
      {
        countTree.Insert(str, 1);
      }
    }
 
    countTree.InOrder();
  }
}

4. 笔试选择题

1. 关于二叉搜索树特性说法错误的是（）

A.二叉搜索树最左侧的节点一定是最小的

B.二叉搜索树最右侧的节点一定是最大的

C.对二叉搜索树进行中序遍历，一定能够得到一个有序序列

D.二叉搜索树的查找效率为O(log_2N)

2. 下面的哪个序列可能是二叉搜索树中序遍历的结果? （）

A.73 8 2 9 4 11

B. 2 3 4 7 8 9 11

C.11 2 9 3 8 4 7

D.以上均可

3. 将整数序列（7-2-4-6-3-1-5）按所示顺序构建一棵二叉排序树a（亦称二叉搜索树），之后将整数8按照二叉排序树规则插入树a中，请问插入之后的树a中序遍历结果是（）

A.1-2-3-4-5-6-7-8

B.7-2-1-4-3-6-5-8

C.1-3-5-2-4-6-7-8

D.1-3-5-6-4-2-8-7

E.7-2-8-1-4-3-6-5

F.5-6-3-4-1-2-7-8

4. 下面关于二叉搜索树正确的说法是（）

A.待删除节点有左子树和右子树时，只能使用左子树的最大值节点替换待删除节点

B.给定一棵二叉搜索树的前序和中序遍率历结果，无法确定这棵二叉搜索树

C.给定一棵二叉搜索树，根据节点值大小排序所需时间复杂度是线性的

D.给定一棵二叉搜索树，可以在线性时间复杂度内转化为平衡二叉搜索树

答案：

1. D

二叉搜索树的概念：

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：

1. 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

2. 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

3. 它的左右子树也分别为二叉搜索树

从概念中可以得出以下性质：

1. 二叉搜索树中最左侧节点一定是最小的，最右侧节点一定是最大的

2. 对二叉搜索树进行中序遍历，可以得到一个有序的序列

A ,B,C：正确

D：错误，二叉搜索树最差情况下会退化为单支树，因此：其查找的效率为O(N)

2. B

二叉搜索树的特性：如果对二叉搜索树进行中序遍历，可以得到有序的序列

3. A

插入之后的树仍旧是二叉搜索树，因此只要是有序的结果则正确，而有序的结果只有A

4. C

A：错误，当待删除节点的左右子树均存在时，既可以在左子树中找一个最大的节点作为替代节点，也可以在右子树中找一个最小的节点作为替代节点，左右子树中都可以找替代节点

B：错误，根据前序遍历和中序遍历，是可以确定一棵树的结构，使用两个遍历结果确定树的结构，其中有一个遍历结果必须要是中序遍历结果。

C：正确，二叉搜索树遍历一遍，就可以得到一个有序序列，因此，时间复杂度为O(N)

D：错误，这里面还需要牵扯到旋转等其他操作，时间复杂度不是线性的

5. 完整代码：

#pragma once
 
#include <iostream>
#include <algorithm>
using namespace std;
 
template<class K>
class BSTreeNode
{
public:
  BSTreeNode(const K& key)
    :_left(nullptr)
    , _right(nullptr)
    , _key(key)
  {}
 
  BSTreeNode<K>* _left;
  BSTreeNode<K>* _right;
  K _key;
};
 
template<class K>
class BSTree
{
  typedef BSTreeNode<K> Node;
 
public:
  bool Insert(const K& key)
  {
    if (_root == nullptr)
    {
      _root = new Node(key);
      return true;
    }
 
    Node* prev = nullptr;
    Node* cur = _root;
    while (cur != nullptr) // 找到要插入的位置
    {
      if (key < cur->_key) // 要插入的值比当前值小
      {
        prev = cur; // 记录cur，等下cur更新就是cur的父亲
        cur = cur->_left; // 到左边插入
      }
      else if (key > cur->_key)
      {
        prev = cur;
        cur = cur->_right;
      }
      else
      {
        return false; // 相等，插入失败
      }
    }
 
    cur = new Node(key); // 走到这，cur就是要插入的位置
    if (key < prev->_key) // 如果key比cur的父亲小
    {
      prev->_left = cur; // 插入到父亲的左孩子
    }
    else
    {
      prev->_right = cur;
    }
    return true;
  }
 
  bool Find(const K& key)
  {
    Node* cur = _root;
    while (cur != nullptr)
    {
      if (key < cur->_key)
      {
        cur = cur->_left;
      }
      else if (key > cur->_key)
      {
        cur = cur->_right;
      }
      else
      {
        return true;
      }
    }
    return false;
  }
 
  bool Erase(const K& key)
  {
    Node* cur = _root;
    Node* father = nullptr;
    while (cur) // 找到要删除的结点
    {
      if (key < cur->_key)
      {
        father = cur;
        cur = cur->_left;
      }
      else if (key > cur->_key)
      {
        father = cur;
        cur = cur->_right;
      }
      else // 找到后开始删除，分三种情况
      {
        if (cur->_left == nullptr) // ①该结点无左孩子
        {
          if (cur == _root)
          {
            _root = cur->_right;
          }
          else
          {
            if (cur == father->_left)
            {
              father->_left = cur->_right;
            }
            else //(cur == father->_right)
            {
              father->_right = cur->_right;
            }
          }
          delete cur;
          cur = nullptr;
        }
        else if (cur->_right == nullptr) //  ②该结点无右孩子
        {
          if (cur == _root)
          {
            _root = cur->_left;
          }
          else
          {
            if (cur == father->_left)
            {
              father->_left = cur->_left;
            }
            else //(cur == father->_left)
            {
              father->_right = cur->_left;
            }
          }
          delete cur;
          cur = nullptr;
        }
        else // ③有两个结点，替换法删除
        {
          Node* MinNode = cur->_right;
          Node* MinParNode = cur;
          while (MinNode->_left) // 找右子树的最小
          {
            MinParNode = MinNode;
            MinNode = MinNode->_left;
          }
          swap(cur->_key, MinNode->_key); // 找到后交换
 
          if(MinParNode->_right == MinNode) // 链接父亲结点，这步易漏
          {
            MinParNode->_right = MinNode->_right;
          }
          else
          {
            MinParNode->_left = MinNode->_right;
          }
          delete MinNode;
          MinNode = nullptr;
        }
        return true;
      }
    }
    return false;
  }
 
  void InOrder()
  {
    _InOrder(_root);
    cout << endl;
  }
 
  bool FindR(const K& key)
  {
    return _FindR(_root, key);
  }
 
  bool InsertR(const K& key)
  {
    return _InsertR(_root, key);
  }
 
  bool EraseR(const K& key)
  {
    return _EraseR(_root, key);
  }
 
  ~BSTree()
  {
    _Destory(_root);
  }
 
  BSTree(const BSTree<K>& t)
  {
    _root = _Copy(t._root);
  }
 
  //BSTree() // 这样写也行，但是下面是C++11的用法
  //{}
  BSTree() = default; // C++11的关键字，强制编译器生成默认的构造
 
  BSTree<K> operator=(BSTree<K> t)
  {
    swap(_root, t._root);
    return *this;
  }
 
protected:
  Node* _Copy(Node* root)
  {
    if (root == nullptr)
    {
      return nullptr;
    }
 
    Node* CopyRoot = new Node(root->_key); // 中序递归链接左右子树
    CopyRoot->_left = _Copy(root->_left);
    CopyRoot->_right = _Copy(root->_right);
    return CopyRoot;
  }
 
  void _Destory(Node*& root) // 加引用下面的置空就起作用了
  {
    if (root == nullptr)
    {
      return;
    }
    _Destory(root->_left);
    _Destory(root->_right);
    delete root;
    root = nullptr;
  }
 
  bool _FindR(Node* root, const K& key)
  {
    if (root == nullptr)
    {
      return false;
    }
    if (key < root->_key)
    {
      _FindR(root->_left, key);
    }
    else if (key > root->_key)
    {
      _FindR(root->_right, key);
    }
    else
    {
      return true;
    }
  }
 
  bool _InsertR(Node*& root, const K& key)
  {
    if (root == nullptr)
    {
      root = new Node(key);
      return true;
    }
 
    if (key < root->_key)
    {
      return _InsertR(root->_left, key);
    }
    else if (key > root->_key)
    {
      return _InsertR(root->_right, key);
    }
    else
    {
      return false;
    }
  }
 
  bool _EraseR(Node*& root, const K& key)
  {
    if (root == nullptr)
    {
      return false;
    }
 
    if (root->_key < key)
    {
      return _EraseR(root->_right, key);
    }
    else if (root->_key > key)
    {
      return _EraseR(root->_left, key);
    }
    else // 找到要删除的结点，开始删除
    {
      Node* del = root;
      if (root->_left == nullptr) // 这里就体现了引用的神之一手，根本不用判断父亲
      {
        root = root->_right;
      }
      else if (root->_right == nullptr)
      {
        root = root->_left;
      }
      else // 找右树的最左节点替换删除
      {
        Node* MinNode = root->_right;
        while (MinNode->_left)
        {
          MinNode = MinNode->_left;
        }
        swap(root->_key, MinNode->_key);
        //return EraseR(key);  错的
        return _EraseR(root->_right, key);
      }
      delete del;
      return true;
    }
  }
 
  void _InOrder(Node* root)
  {
    if (root == nullptr)
    {
      return;
    }
    _InOrder(root->_left);
    cout << root->_key << " ";
    _InOrder(root->_right);
  }
 
  Node* _root = nullptr;
};
 
//二叉搜索树的KV结构
namespace KeyValue
{
  //定义两个类模板参数K、V
  template<class K, class V>
  class BSTreeNode
  {
  public:
    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; //存放了两个类型的数据，相比较与K模型
    V _value;
  };
 
  //同样的，定义两个类模板参数K、V
  //搜索二叉树依旧是按照K的数据进行排序，和V无关
  template<class K, class V>
  class BSTree
  {
    typedef BSTreeNode<K, V> Node;
  public:
    bool Insert(const K& key, const V& value)
    {
      if (_root == nullptr)
      {
        _root = new Node(key, value);
        return true;
      }
 
      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
        {
          return false;
        }
      }
 
      cur = new Node(key, value);
      if (parent->_key < key)
      {
        parent->_right = cur;
      }
      else
      {
        parent->_left = cur;
      }
 
      return true;
    }
 
    //查找只和数据_key有关，与数据_value无关
    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;
    }
 
    //删除只和数据_key有关，与数据_value无关
    bool Erase(const K& key)
    {
      //... 和K模型一样
      return true;
    }
 
    void InOrder()
    {
      _InOrder(_root);
      cout << endl;
    }
  protected:
    void _InOrder(Node* root)
    {
      if (root == nullptr)
      {
        return;
      }
 
      _InOrder(root->_left);
      cout << root->_key << ":" << root->_value << endl;
      _InOrder(root->_right);
    }
 
    Node* _root = nullptr;
  };
 
  void TestBSTree1()
  {
    BSTree<string, string> dict; // 字典树，如果所有单词都在里面就能很准确查找
    dict.Insert("sort", "排序");
    dict.Insert("left", "左边");
    dict.Insert("right", "右边");
    dict.Insert("string", "字符串");
    dict.Insert("insert", "插入");
    string str;
    while (cin >> str) // Crtl+z+换行结束，或者Crtl+c结束
    {
      BSTreeNode<string, string>* ret = dict.Find(str);
      if (ret)
      {
        cout << "对应的中文:" << ret->_value << endl;
      }
      else
      {
        cout << "对应的中文->无此单词" << endl;
      }
    }
  }
 
  void TestBSTree2() // 统计水果出现的次数
  {
    string arr[] = { "香蕉", "苹果", "香蕉", "草莓", "香蕉", "苹果", "苹果", "苹果" };
 
    BSTree<string, int> countTree;
    for (auto& str : arr)
    {
      //BSTreeNode<string, int>* ret = countTree.Find(str);
      auto ret = countTree.Find(str);
      if (ret)
      {
        ret->_value++;
      }
      else
      {
        countTree.Insert(str, 1);
      }
    }
 
    countTree.InOrder();
  }
}

#include "BinarySearchTree.h"
 
void TestBSTree1() 
{
  BSTree<int> t;
  int arr[] = { 8, 3, 1, 10, 2, 2, 3, 6, 4, 7, 14, 13 };
  for (const auto& e : arr)
  {
    t.Insert(e);
  }
  t.InOrder();
 
  t.Erase(8);
  t.Erase(3);
  t.InOrder();
  for (const auto& e : arr)
  {
    t.Erase(e);
  }
  t.InOrder();
}
 
void TestBSTree2()
{
  BSTree<int> t;
  int arr[] = { 8, 3, 1, 10, 2, 2, 3, 6, 4, 7, 14, 13 };
  for (const auto& e : arr)
  {
    t.InsertR(e);
  }
  t.InOrder();
 
  t.EraseR(8);
  t.EraseR(3);
  t.EraseR(2);
  t.InOrder();
  cout << t.Find(10) << endl;
  cout << t.Find(100) << endl;
  cout << t.FindR(10) << endl;
  cout << t.FindR(100) << endl;
  for (const auto& e : arr)
  {
    t.EraseR(e);
  }
  t.InOrder();
}
 
void TestBSTree3()
{
  BSTree<int> t;
  int arr[] = { 8, 3, 1, 10, 2, 2, 3, 6, 4, 7, 14, 13 };
  for (const auto& e : arr)
  {
    t.InsertR(e);
  }
  t.InOrder();
 
  BSTree<int> copy = t;
  copy.InOrder();
 
  BSTree<int> t2;
  t2.Insert(3);
  t2.Insert(5);
  t2.Insert(4);
  copy = t2;
  t2.InOrder();
  copy.InOrder();
}
 
int main()
{
  //TestBSTree3();
  KeyValue::TestBSTree2();
 
  return 0;
}

本篇完。

下一部分：树的OJ题，然后是map和set，再然后是AVL树和红黑树。

从C语言到C++_24(二叉搜索树)概念+完整代码实现+笔试题（下）

3. 搜索二叉树的应用

3.1 K 模型

3.2 KV 模型

4. 笔试选择题

答案：

5. 完整代码：

本篇完。

热门文章

最新文章

相关课程

相关电子书