【数据结构】搜索二叉树-阿里云开发者社区

二叉搜索树的概念

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

若它的左子树不为空，则左子树上的所有节点的值都小于根节点的值。
若它的右子树不为空，则右子树上的所有节点的值都大于根节点的值。
它的左右子树也分别为二叉搜索树。

二叉搜索树的特点是搜索数据比较快，最多高度次就可以找到所值，其高度最大就是O(N)

二叉搜索树的实现过程

基本框架

需要有一个struct的类（struct的类默认公开）来包含一个节点的所有特性，包括其可以指向左子树、右子树以及其包含的数据。
然后使用class的类来对这棵二叉搜索树进行封装。

template<class K>
struct BSTreeNode
{
  BSTreeNode(const K& key)
    :_left(nullptr)
    ,_right(nullptr)
    ,_key(key)
  {}
 
  BSTreeNode<K>* _left;
  BSTreeNode<K>* _right;
  K _key;
};
 
template<class K>
struct BSTree
{
  typedef BSTreeNode<K> Node;
public:
 
private:
  Node* _root;
};

初始化二叉树：

  //初始化节点
  BSTree()
    :_root(nullptr)
  {}

二叉搜索树的插入

插入过程：

当树为空的时候，直接新增节点，赋值给root指针。
树不为空，按二叉搜索树的性质查找插入位置，插入新节点。

//插入数据
bool insert(const K& key)
{
  if (_root == nullptr)
  {
    _root = new Node(key);
    return true;
  }
  Node* cur = _root;
  Node* parent = nullptr;
  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);
  if (cur->_key > parent->_key)
  {
    parent->_right = cur;
  }
  else
  {
    parent->_left = cur;
  }
  return true;
}

搜索二叉树的打印（使用中序遍历）

在这段代码中，使用_root作为参数传递给_InOrder函数，而不是直接在_InOrder函数中使用__root，主要是为了增加代码的灵活性和可复用性。

这样做的好处是，_InOrder函数可以处理不同的二叉树，而不仅仅局限于某个特定的二叉树对象。通过将二叉树的根节点作为参数传递给_InOrder函数，就可以对任意给定的二叉树进行中序遍历。

如果直接在_InOrder函数中使用_root，那么_InOrder函数就只能操作类内部固定的_root成员变量所代表的二叉树。而通过参数传递的方式，可以在需要的时候将不同的二叉树根节点传递给_InOrder函数，使其能够对各种不同的二叉树进行操作，提高了函数的通用性。

  //二叉树的升序打印
  void InOrder()
  {
    _InOrder(_root);
    cout << endl;
  }
  void _InOrder(Node* root)
  {
    if (root == nullptr)
    {
      return;
    }
    _InOrder(root->_left);
    cout << root->_key << " ";
    _InOrder(root->_right);
  }

二查搜索树的查找

从根开始查找，如果比根小走左路，比根大走右路。
最多查找高度次，如果没找到则不存在。

二叉搜索树的删除（难点）

首先需要查找元素中是否在二叉搜索树中，如果不存在，则返回，否则要删除的节点可以分为下面四种情况：

要删除的节点无孩子节点。
要删除的节点只有左孩子节点。
要删除的节点只有右孩子节点。
要删除的节点有左、右孩子节点。

总结下来，实际中真正要删除的情况只有三种：

删除该节点且使被删除节点的双亲结点指向被删除节点的左孩子节点——直接删除。
删除该节点且使被删除节点的双亲结点指向被删除节点的右孩子节点——直接删除。
在它的右子树中寻找中序下的第一个节点（数值最小）或者在它的左子树中寻找中序前的最后一个节点（数值最大），用它的值填补到被删除节点中，再来处理该节点的删除问题【替换法】。

再进行缩减就是：

没有孩子或者只有一个孩子，进行托孤。
有俩个孩子进行替换。

  //搜索二叉树的删除
  bool Erase(const K& key)
  {
    Node* cur = _root;
    Node* parent = nullptr;
    while (cur)
    {
      if (cur->_key > key)
      {
        parent = cur;
        cur = cur->_left;
      }
      else if (cur->_key < key)
      {
        parent = cur;
        cur = cur->_right;
      }
      else
      {
        if (cur->_left == nullptr)
        {
          if (cur == _root)
          {
            _root = cur->_right;
          }
          else
          {
            if (parent->_left == cur)
            {
              parent->_left = cur->_right;
            }
            else
            {
              parent->_right = cur->_right;
            }
          }
        }
        else if(cur->_right == nullptr)
        {
          if (cur == _root)
          {
            _root = cur->_left;
          }
          else
          {
            if (parent->_left == cur)
            {
              parent->_left = cur->_left;
            }
            else
            {
              parent->_right = cur->_left;
            }
          }
        }
        else
        {
          //替换法
          Node* LeftMax = _root->_left;
          Node* parent = _root;
          while (LeftMax->_right)
          {
            parent = LeftMax;
            LeftMax = LeftMax->_right;
          }
          swap(LeftMax->_key, cur->_key);
 
          if (parent->_left == LeftMax)
          {
            parent->_left = LeftMax->_left;
          }
          else
          {
            parent->_right = LeftMax->_left;
          }
 
          cur = LeftMax;
        }
        delete cur;
        return true;
      }
    }
    return false;
  }

分析该代码：

二叉树的递归实现

在递归实现的过程中，唯一需要注意的地方是使用了指针引用，这是因为引用不能改变指向，但是在递归函数的过程中都会重新定义引用。

递归升序打印

  //二叉树的升序打印
  void InOrder()
  {
    _InOrder(_root);
    cout << endl;
  }
private:
  void _InOrder(Node* root)
  {
    if (root == nullptr)
    {
      return;
    }
    _InOrder(root->_left);
    cout << root->_key << " ";
    _InOrder(root->_right);
  }

递归查找

  //查找
  bool FindR(const K& key)
  {
    return _FindR(_root, key);
  }
private:
  bool _FindR(Node* root, const K& key)
  {
    if (root == nullptr)
    {
      return false;
    }
 
    if (root->_key > key)
    {
      return _FindR(root->_left, key);
    }
    else if (root->_key < key)
    {
      return _FindR(root->_right, key);
    }
    else
    {
      return true;
    }
  }

递归插入

  //插入
  bool InsertR(const K& key)
  {
    return _InsertR(_root, key);
  }
private:
  bool _InsertR(Node*& root, const K& key)
  {
    if (root == nullptr)
    {
      root = new Node(key);
      return true;
    }
 
    if (root->_key > key)
    {
      return _InsertR(root->_left, key);
    }
    else if (root->_key < key)
    {
      return _InsertR(root->_right, key);
    }
    else
    {
      return false;
    }
  }

递归删除

  //删除
  bool EraseR(const K& key)
  {
    return _EraseR(_root, key);
  }
private:
  bool _EraseR(Node*& root, const K& key)
  {
    if (root == nullptr)
    {
      return false;
    }
 
    if (root->_key > key)
    {
      return _EraseR(root->_left, key);
    }
    else if(root->_key < key)
    {
      return _EraseR(root->_right, key);
    }
    else
    {
      Node* del = root;
      if (root->_left == nullptr)
      {
        root = root->_right;
      }
      else if (root->_right == nullptr)
      {
        root = root->_left;
      }
      else
      {
        Node* MaxLeft = root->_left;
        while (MaxLeft->_right)
        {
          MaxLeft = MaxLeft->_right;
        }
        swap(root->_key, MaxLeft->_key);
 
        return _EraseR(root->_left, key);
      }
      delete del;
      return true;
    }
  }

二叉树完整代码展示

#pragma once
#include<iostream>
using namespace std;
 
template<class K>
struct BSTreeNode
{
  BSTreeNode(const K& key)
    :_left(nullptr)
    ,_right(nullptr)
    ,_key(key)
  {}
 
  BSTreeNode<K>* _left;
  BSTreeNode<K>* _right;
  K _key;
};
 
template<class K>
struct BSTree
{
  typedef BSTreeNode<K> Node;
public:
  //初始化节点
  BSTree()
    :_root(nullptr)
  {}
  //插入数据
  bool insert(const K& key)
  {
    if (_root == nullptr)
    {
      _root = new Node(key);
      return true;
    }
    Node* cur = _root;
    Node* parent = nullptr;
    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);
    if (cur->_key > parent->_key)
    {
      parent->_right = cur;
    }
    else
    {
      parent->_left = cur;
    }
    return true;
  }
 
  //搜索二叉树的查找
  bool Find(const K& key)
  {
    Node* cur = _root;
    while (cur)
    {
      if (cur->_key > key)
      {
        cur = cur->_left;
      }
      else if (cur->_key < key)
      {
        cur = cur->_right;
      }
      else
      {
        return true;
      }
    }
    return false;
  }
 
  //搜索二叉树的删除
  bool Erase(const K& key)
  {
    Node* cur = _root;
    Node* parent = nullptr;
    while (cur)
    {
      if (cur->_key > key)
      {
        parent = cur;
        cur = cur->_left;
      }
      else if (cur->_key < key)
      {
        parent = cur;
        cur = cur->_right;
      }
      else
      {
        if (cur->_left == nullptr)
        {
          if (cur == _root)
          {
            _root = cur->_right;
          }
          else
          {
            if (parent->_left == cur)
            {
              parent->_left = cur->_right;
            }
            else
            {
              parent->_right = cur->_right;
            }
          }
        }
        else if(cur->_right == nullptr)
        {
          if (cur == _root)
          {
            _root = cur->_left;
          }
          else
          {
            if (parent->_left == cur)
            {
              parent->_left = cur->_left;
            }
            else
            {
              parent->_right = cur->_left;
            }
          }
        }
        else
        {
          //替换法
          Node* LeftMax = _root->_left;
          Node* parent = _root;
          while (LeftMax->_right)
          {
            parent = LeftMax;
            LeftMax = LeftMax->_right;
          }
          swap(LeftMax->_key, cur->_key);
 
          if (parent->_left == LeftMax)
          {
            parent->_left = LeftMax->_left;
          }
          else
          {
            parent->_right = LeftMax->_left;
          }
 
          cur = LeftMax;
        }
        delete cur;
        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);
  }
private:
  bool _EraseR(Node*& root, const K& key)
  {
    if (root == nullptr)
    {
      return false;
    }
 
    if (root->_key > key)
    {
      return _EraseR(root->_left, key);
    }
    else if(root->_key < key)
    {
      return _EraseR(root->_right, key);
    }
    else
    {
      Node* del = root;
      if (root->_left == nullptr)
      {
        root = root->_right;
      }
      else if (root->_right == nullptr)
      {
        root = root->_left;
      }
      else
      {
        Node* MaxLeft = root->_left;
        while (MaxLeft->_right)
        {
          MaxLeft = MaxLeft->_right;
        }
        swap(root->_key, MaxLeft->_key);
 
        return _EraseR(root->_left, key);
      }
      delete del;
      return true;
    }
  }
 
  bool _InsertR(Node*& root, const K& key)
  {
    if (root == nullptr)
    {
      root = new Node(key);
      return true;
    }
 
    if (root->_key > key)
    {
      return _InsertR(root->_left, key);
    }
    else if (root->_key < key)
    {
      return _InsertR(root->_right, key);
    }
    else
    {
      return false;
    }
  }
 
  bool _FindR(Node* root, const K& key)
  {
    if (root == nullptr)
    {
      return false;
    }
 
    if (root->_key > key)
    {
      return _FindR(root->_left, key);
    }
    else if (root->_key < key)
    {
      return _FindR(root->_right, key);
    }
    else
    {
      return true;
    }
  }
 
  void _InOrder(Node* root)
  {
    if (root == nullptr)
    {
      return;
    }
    _InOrder(root->_left);
    cout << root->_key << " ";
    _InOrder(root->_right);
  }
  Node* _root;
};

二叉树的应用

1.K模型：K模型即只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值。K模型可以快速判断在不在的场景，之前模拟实现的就是K模型。

应用1：门禁系统。
应用2：小区车辆出入系统（是否允许进入）。
应用3：判断单词是否正确。

2.KV模型：每一个关键码key，都会对应一个value的值，即< key,value >。KV模型可以通过一个值快速找到另外一个值。

应用1：手机号码查询快递。
应用2：商城车辆出入系统（记录实际）。
应用3：高铁实名制车票系统。
应用4：英汉词典的中英文对应关系。

KV模型代码展示：

#include<iostream>
 
using namespace std;
 
namespace key_value
{
  template<class K, class V>
  struct BSTreeNode
  {
    BSTreeNode<K, V>* _left;
    BSTreeNode<K, V>* _right;
    K _key;
    V _value;
 
    BSTreeNode(const K& key, const V& value)
      :_left(nullptr)
      , _right(nullptr)
      , _key(key)
      , _value(value)
    {}
  };
 
  template<class K, class V>
  class BSTree
  {
    typedef BSTreeNode<K, V> Node;
  public:
    BSTree()
      :_root(nullptr)
    {}
 
    void InOrder()
    {
      _InOrder(_root);
      cout << endl;
    }
 
    Node* FindR(const K& key)
    {
      return _FindR(_root, key);
    }
 
    bool InsertR(const K& key, const V& value)
    {
      return _InsertR(_root, key, value);
    }
 
    bool EraseR(const K& key)
    {
      return _EraseR(_root, key);
    }
 
  private:
    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;
 
        // 1、左为空
        // 2、右为空
        // 3、左右都不为空
        if (root->_left == nullptr)
        {
          root = root->_right;
        }
        else if (root->_right == nullptr)
        {
          root = root->_left;
        }
        else
        {
          Node* leftMax = root->_left;
          while (leftMax->_right)
          {
            leftMax = leftMax->_right;
          }
 
          swap(root->_key, leftMax->_key);
 
          return _EraseR(root->_left, key);
        }
 
        delete del;
        return true;
      }
    }
 
    bool _InsertR(Node*& root, const K& key, const V& value)
    {
      if (root == nullptr)
      {
        root = new Node(key, value);
        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;
      }
    }
 
    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;
      }
    }
 
    void _InOrder(Node* root)
    {
      if (root == NULL)
      {
        return;
      }
 
      _InOrder(root->_left);
      cout << root->_key << ":" << root->_value << endl;
      _InOrder(root->_right);
    }
  private:
    Node* _root;
  };
 
  void TestBSTree1()
  {
    //BSTree<string, Date> carTree;
    BSTree<string, string> dict;
    dict.InsertR("insert", "插入");
    dict.InsertR("sort", "排序");
    dict.InsertR("right", "右边");
    dict.InsertR("date", "日期");
 
    string str;
    while (cin >> str)
    {
      BSTreeNode<string, string>* ret = dict.FindR(str);
      if (ret)
      {
        cout << ret->_value << endl;
      }
      else
      {
        cout << "无此单词" << endl;
      }
    }
  }
 
  void TestBSTree2()
  {
    // 统计水果出现的次数
    string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
    BSTree<string, int> countTree;
    for (auto& str : arr)
    {
      auto ret = countTree.FindR(str);
      if (ret == nullptr)
      {
        countTree.InsertR(str, 1);
      }
      else
      {
        ret->_value++;
      }
    }
 
    countTree.InOrder();
  }
}

二叉树的性能分析

插入和删除都必须先查找，查找效率代表了二叉搜索树的各个操作的性能。

对于n个节点的二叉搜索树，若是每一个元素查找的概率相等，则二叉搜索树平均查找长度是节点在二叉搜索树的深度的函数，即节点越深，则比较的次数越多。

但是如果同一组数据的插入次序不同，可能得到不同结构的二叉搜索树。

最优的情况是：二叉搜索树为完全二叉树（或者接近完全二叉树），其平均比较次数为：logN

最差的情况是：二叉搜索树退化成单支树（或者类似单支），其平均的比较次数为N。

使用有序数组进行二分查找的时候，其缺点是插入与删除效率不高；

使用搜索二叉树进行二分查找的时候，其可以很好地利用其特性进行查找、插入、删除、排序等操作，但是搜索二叉树的唯一缺点就是下限无保障（一条光杆树）。

所以在后续的C++文章中会介绍AVL树、红黑树、B树来解决这个问题。

【数据结构】搜索二叉树

二叉搜索树的概念

二叉搜索树的实现过程

基本框架

初始化二叉树：

二叉搜索树的插入

搜索二叉树的打印（使用中序遍历）

二查搜索树的查找

二叉搜索树的删除（难点）

二叉树的递归实现

递归升序打印

递归查找

递归插入

递归删除

二叉树完整代码展示

二叉树的应用

二叉树的性能分析

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【数据结构】搜索二叉树

二叉搜索树的概念

二叉搜索树的实现过程

基本框架

初始化二叉树：

二叉搜索树的插入

搜索二叉树的打印（使用中序遍历）

二查搜索树的查找

二叉搜索树的删除（难点）

二叉树的递归实现

递归升序打印

递归查找

递归插入

递归删除

二叉树完整代码展示

二叉树的应用

二叉树的性能分析

热门文章

最新文章

相关课程

相关电子书