【高阶数据结构】搜索二叉树 & 经典习题讲解-阿里云开发者社区

一. 概念

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

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

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

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

二. 基本操作

🌈查找元素 Search

从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找

最多查找高度次，走到到空，还没找到，这个值不存在

//查找
  bool 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 true;
    }
  }
  }

🌈插入 Insert

思路如下：

树为空，则直接新增节点，直接插入root指针即可

因为不能插入重复的元素，并且每次插入都是要定位到空节点的位置；定义一个 cur 从root开始，插入的元素比当前位置元素小就往左走，比当前位置元素大就往右走，直到为空；

再定义一个parent记录 cur的前一个位置，最后判断cur是parent的左子树or右子树

动画演示：

//相同的
  bool Insert(const K& key)
  {
  if (_root == nullptr)
  {
    _root = new Node(key);
    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);
  if(parent->_key < key)
  {
    parent->_right = cur;
  }
  else
  {
    parent->_left = cur;
  }
  return true;
  }

🌈删除 Delete

删除有三种情况：

无牵无挂型：如果是叶子结点，直接置空并链接到空指针

独生子女型：只有一个子节点，删除自己本身，并链接子节点和父节点

替罪羊型：寻找出右子树最小节点、左子树最大节点，其节点可以作为交换节点和删除结点进行交换，交换后删除交换节点、交换节点要么没有孩子，要么只有一个孩子可以直接删除

其实在代码层面第一种情况可以归类到第二种情况（没有左孩子，就链接上右孩子）

在代码层面实际上是四种：

左为空

右为空

左右都为空（细节很多看下图）

cur是跟节点位置（特殊情况移动root）

//删除
  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
    {
    //找到了，开始删除，有三种情况
    //1、左为空
    //2、右为空
    //3、左右都不为空
    //4、删除跟root 要移动root（特殊情况）
    if (cur->_left == nullptr)
    {
      if (cur == _root)
      {
      _root = cur->_right;
      }
      else
      {
      if (cur == parent->_left)
      {
        parent->_left = cur->_right;
      }
      else
      {
        parent->_right = cur->_right;
      }
      }
      delete cur;
      cur = nullptr;
    }
    else if (cur->_right == nullptr)
    {
      if (_root == cur)
      {
      _root = cur->_left;
      }
      else
      {
      if (cur == parent->_left)
      {
        parent->_left = cur->_left;
      }
      else
      {
        parent->_right = cur->_left;
      }
      }
      delete cur;
      cur = nullptr;
    }
    else
    {
      //左右都不为空  ——  替换法删除
      //找到右树最小节点进行替换
      Node* min = cur->_right;
      Node* minparent = nullptr;
      while (min->_left)
      {
      minparent = min;
      min = min->_left;
      }
      swap(cur->_key, min->_key);
      //注意min的右子树还有连接节点的可能
      //和判断min在哪边的问题？
      if (minparent->left = min)
      {
      minparent->_left = min->_right;
      }
      else
      {
      minparent->_right = min->_right;
      }
      delete min;
    }
    return true;
    }
  }
  return false;
  }

三. 进阶操作 ~ 递归写法

🥑递归查找 Search

唤起递归的记忆吧

void _FindR(Node* root, const K& key)
  {
  //根为空的情况下
  if (root == nullptr)
  {
    return false;
  }
  if (root->_key < key)
  {
    return _FindR(root->_right);
  }
  else if (root->_key > key)
  {
    return _FindR(root->_left);
  }
  else
  {
    return true;
  }
  }

🥑递归插入 Insert

要注意，这里有“神之一手”

void _InsertR(Node*& root, const K& key)
  {
  if (root == nullptr)
  {
    root = new Node(key);
    return true;
  }
  if (root->_key < key)
  {
    return _InsertR(root->_right, key);
  }
  else if (root->_key > key)
  {
    return _InsertR(root->_left, key);
  }
  else
  {
    return false;
  }
  }

🥑递归删除 Delete

神之操作：root = root->_left

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* min = root->_right;
    while (min->_left)
    {
      min = min->_left;
    }
    swap(min->_key, root->_key);
    return _Erase(root->_right)
    }
    delete del;
    return true;
  }
  }

四. 性能分析

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为： l o g 2 N log_2 N log

最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为： N 2 \frac{N}{2}

五. 二叉搜索树的应用

💦Key模型

key的搜索模型，判断关键字在不在

刷卡进宿舍楼

检测一篇英文文档中单词拼写是否正确

以上都是把全部相关的资料都插入到一颗搜索树中，然后开始寻找，判断在不在

💦Key- Value模型

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

比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对

再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对

// 改造二叉搜索树为KV结构
template<class K, class V>
struct BSTNode
{
  BSTNode(const K& key = K(), const V& value = V())
  : _pLeft(nullptr), _pRight(nullptr), _key(key), _Value(value)
  {}
  BSTNode<T>* _pLeft;
  BSTNode<T>* _pRight;
  K _key;
  V _value
};
template<class K, class V>
class BSTree
{
  typedef BSTNode<K, V> Node;
  typedef Node* PNode;
public:
  BSTree() : _pRoot(nullptr) {}
  PNode Find(const K& key);
  bool Insert(const K& key, const V& value)
  bool Erase(const K& key)
private:
  PNode _pRoot;
}
void TestBSTree3()
{
  // 输入单词，查找单词对应的中文翻译
  BSTree<string, string> dict;
  dict.Insert("string", "字符串");
  dict.Insert("tree", "树");
  dict.Insert("left", "左边、剩余");
  dict.Insert("right", "右边");
  dict.Insert("sort", "排序");
  // 插入词库中所有单词
  string str;
  while (cin >> str)
  {
  BSTreeNode<string, string>* ret = dict.Find(str);
  if (ret == nullptr)
  {
    cout << "单词拼写错误，词库中没有这个单词:" << str << endl;
  }
  else
  {
    cout << str << "中文翻译:" << ret->_value << endl;
  }
  }
}

附源码

BinarySearchTree.h
#pragma once
#include<iostream>
using namespace std;
namespace Key
{
  template<class K>
  struct BSTreeNode
  {
  BSTreeNode<K>* _left;
  BSTreeNode<K>* _right;
  K _key;
  BSTreeNode(const K& key)
    :_left(nullptr)
    , _right(nullptr)
    , _key(key)
  {}
  };
  //class BinarySearchTree
  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* 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);
    if (parent->_key < 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->_right;
    }
    else if (cur->_key < key)
    {
      cur = cur->_left;
    }
    else
    {
      return true;
    }
    }
  }
  //删除
  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
    {
      //找到了，开始删除，有三种情况
      //1、左为空
      //2、右为空
      //3、左右都不为空
      //4、删除跟root 要移动root（特殊情况）
      if (cur->_left == nullptr)
      {
      if (cur == _root)
      {
        _root = cur->_right;
      }
      else
      {
        if (cur == parent->_left)
        {
        parent->_left = cur->_right;
        }
        else
        {
        parent->_right = cur->_right;
        }
      }
      delete cur;
      cur = nullptr;
      }
      else if (cur->_right == nullptr)
      {
      if (_root == cur)
      {
        _root = cur->_left;
      }
      else
      {
        if (cur == parent->_left)
        {
        parent->_left = cur->_left;
        }
        else
        {
        parent->_right = cur->_left;
        }
      }
      delete cur;
      cur = nullptr;
      }
      else
      {
      //左右都不为空  ——  替换法删除
      //找到右树最小节点进行替换
      Node* min = cur->_right;
      Node* minparent = nullptr;
      while (min->_left)
      {
        minparent = min;
        min = min->_left;
      }
      swap(cur->_key, min->_key);
      //注意min的右子树还有连接节点的可能
      //和判断min在哪边的问题？
      if (minparent->_left = min)
      {
        minparent->_left = min->_right;
      }
      else
      {
        minparent->_right = min->_right;
      }
      delete min;
      }
      return true;
    }
    }
    return false;
  }
  //这样就能避免this指针问题,因为递归必须显示给参数
  void InOrder()
  {
    _InOrder(_root);//这样就可以使用_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()
  //{}
  //C++11的用法：强制编译器生成默认构造
  BSTree() = default;
  //拷贝构造
  BSTree(const BSTree<K>& t)
  {
    _root = _Copy(t._root);
  }
  //t2 = t1
  BSTree<K>& operator = (BSTree<K> t)
  {
    swap(_root, t._root);
    return *this;
  }
  private:
  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 _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* min = root->_right;
      while (min->_left)
      {
      min = min->_left;
      }
      swap(min->_key, root->_key);
      return _Erase(root->_right);//防止找不到key的情况
    }
    delete del;
    return true;
    }
  }
  void _InsertR(Node*& root, const K& key)
  {
    if (root == nullptr)
    {
    root = new Node(key);
    return true;
    }
    if (root->_key < key)
    {
    return _InsertR(root->_right, key);
    }
    else if (root->_key > key)
    {
    return _InsertR(root->_left, key);
    }
    else
    {
    return false;
    }
  }
  void _FindR(Node* root, const K& key)
  {
    //根为空的情况下
    if (root == nullptr)
    {
    return false;
    }
    if (root->_key < key)
    {
    return _FindR(root->_right, key);
    }
    else if (root->_key > key)
    {
    return _FindR(root->_left, key);
    }
    else
    {
    return true;
    }
  }
  void _InOrder(Node* root)
  {
    if (root == nullptr)
    {
    return;
    }
    _InOrder(root->_left);
    cout << root->_key << " ";
    _InOrder(root->_right);
  }
  private:
  Node* _root = nullptr;
  };
  void TestBSTree1()
  {
  BSTree<int> t;
  int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
  for (auto e : a)
  {
    t.Insert(e);
  }
  //排序+去重
  t.InOrder();
  t.Erase(3);
  t.InOrder();
  t.Erase(6);
  t.InOrder();
  }
  void TestBSTree2()
  {
  BSTree<int> t;
  int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
  for (auto e : a)
  {
    t.Insert(e);
  }
  BSTree<int> copy = t;
  copy.InOrder();
  t.InOrder();
  }
}

test.c

#include "BinarySearchTree.h"
int main()
{
  //TestBSTree1();
  /*TestBSTree2();*/
  TestBSTree3();
  return 0;
}

二叉树习题大全

1️⃣根据二叉树创建字符串

题目地址：传送

思路：

左括号为空，右括号不为空，不可以省略

左右括号为空，省略

class Solution {
public:
    string tree2str(TreeNode* root) {
        if(root == nullptr)
            return string();
        string str;
        str += to_string(root->val);
        //左边不为空or左变为空，右变不为空 不可以省略
        if(root->left || root->right)
        {
            str += '(';
            str += tree2str(root->left);
            str += ')';
        }
        //右为空的都可以省略
        if(root->right)
        {
            str += '(';
            str += tree2str(root->right);
            str += ')';
        }
        return str;
    }
};

2️⃣二叉树的层序遍历

题目地址：传送

解题思路：

要控制一层一层的出，定义一个levelsize，每次的队列的个数就是levelsize的大小

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        size_t levelsize = 0;
        if(root)
        {
            q.push(root);
            levelsize = 1;
        }
        vector<vector<int>> vv;
        while(!q.empty())
        {
            //控制一层一层的出
            vector<int> v;
            for(size_t i = 0; i < levelsize; i++)
            {
                TreeNode* front = q.front();
                q.pop();
                v.push_back(front->val);
                if(front->left)
                    q.push(front->left);
                if(front->right)
                    q.push(front->right);
            }
            vv.push_back(v);
            //当前层出完了，下一层都进队列了，队列的size就是下一层的数据个数
            levelsize = q.size();
        }
        return vv;
    }
};

3️⃣二叉树的层序遍历 II

要求反过来输出

其实只要在上面题目的基础上倒置一下二维数组即可

4️⃣二叉树的最近公共祖先

题目链接：传送

规则：一个是左子树中节点，一个是右子树节点，那么它就是最近公共祖先

此处函数的起名很重要

class Solution {
public:
    bool Find(TreeNode* sub, TreeNode* x)
    {
        if(sub == nullptr)
            return false;
        if(sub == x)
            return true;
        return Find(sub->left, x)
            || Find(sub->right, x);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == nullptr)
            return nullptr;
        //根是我
        if(root == q || root == p)
            return root;
        bool qInLeft, qInRight, pInLeft, pInRight;
        pInLeft = Find(root->left, p);
        pInRight = !pInLeft;
        qInLeft = Find(root->left, q);
        qInRight = !qInLeft;
        //1、一个在左一个在右，root就是最近公共祖先
        //2、如果都在左，就递归去左边
        //3、如果都在右，就递归去右边
        if((pInLeft && qInRight) || (qInLeft && pInRight))
        {
            return root;
        }
        else if (qInLeft && pInLeft)
        {
            return lowestCommonAncestor(root->left, p, q);
        }
        else if (qInRight && pInRight)
        {
            return lowestCommonAncestor(root->right, p, q);
        }
        else
        {
            return nullptr;
        }
    }
};

思路2：存储路径

定义一个stack来存储路径，通过递归来找到p和q的具体路径

大的路径先走，直到两个路径相同，比较两个路径的top（），不相等的同样pop掉，最后返回的肯定是相等的

class Solution {
public:
    bool FindPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path)
    {
        if(root == nullptr)
            return false;
        path.push(root);
        if(root == x)
            return true;
        if(FindPath(root->left, x,path))
            return true;
        if(FindPath(root->right, x, path))  
            return true;
        path.pop();
        return false;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*> pPath, qPath;
        FindPath(root, p, pPath);
        FindPath(root, q, qPath);
        //类似链表相交 —— 大的先走 直到两个相等
        while(pPath.size() != qPath.size())
        {
            if(pPath.size() > qPath.size())
                pPath.pop();
            else
                qPath.pop();
        }
        //两个值不相等一起pop
        while(pPath.top() != qPath.top())
        {
            pPath.pop();
            qPath.pop();
        }
        //最后肯定相等，随便返回一个即可
        return pPath.top();
    }
};

5️⃣ 二叉搜索树与双向链表

题目地址：传送

思路：

left指向中序的前一个；right指向中序的后一个

中序遍历：cur的前一个是prev， cur移动后，prev的后一个是cur ；构成双向链接

class Solution {
public:
  void InOderConvert(TreeNode* cur, TreeNode*& prev)
  {
  if(cur == nullptr)
    return ;
  InOderConvert(cur->left, prev);
  cur->left = prev;
  if(prev)
    prev->right = cur;
  prev = cur;
  InOderConvert(cur->right, prev);
  }
    TreeNode* Convert(TreeNode* pRootOfTree) {
        TreeNode* prev = nullptr;
  InOderConvert(pRootOfTree, prev);
  TreeNode* head = pRootOfTree;
  while(head && head->left)
    head = head->left;
  return head;
    }
};

6️⃣从前序与中序遍历序列构造二叉树

题目链接：传送

相信大家都做过这道选择题吧哈哈哈

思路：

前序创建树，中序分割左右子树

子树区间确认是否继续递归创建子树，不存在区间则空树

class Solution {
public:
    TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& prei, int inbegin, int inend) {
        if(inbegin > inend)
            return nullptr;
        TreeNode* root = new TreeNode(preorder[prei++]);
        //分割中序
        int ini = inbegin;
        while(ini <= inend)
        {
            if(inorder[ini] == root->val)
                break;
            else
                ini++;
        }
        //[inbegin, ini-1] ini [ini+1, inend]
        root->left = _buildTree(preorder, inorder, prei, inbegin, ini-1);
        root->right = _buildTree(preorder, inorder, prei, ini+1,  inend);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int i = 0;
        return _buildTree(preorder,inorder, i, 0, inorder.size()-1);
    }
};

【高阶数据结构】搜索二叉树 & 经典习题讲解

一. 概念

二. 基本操作

🌈查找元素 Search

🌈插入 Insert

🌈删除 Delete

三. 进阶操作 ~ 递归写法

四. 性能分析

五. 二叉搜索树的应用

热门文章

最新文章

相关课程

相关电子书

相关实验场景