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

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

一. 概念


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


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


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


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


0a2653c851af460fa595bd959398a8f1.png


二. 基本操作


🌈查找元素 Search


2d65d23f6d4748949b924e4057485923.png


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

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

//查找
  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右子树

动画演示:


2019082413041482.gif


//相同的
  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

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


0a2653c851af460fa595bd959398a8f1.png2d65d23f6d4748949b924e4057485923.png


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


0a2653c851af460fa595bd959398a8f1.png2d65d23f6d4748949b924e4057485923.png


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

2


N

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

2

N


五. 二叉搜索树的应用


💦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️⃣根据二叉树创建字符串

题目地址:传送


0a2653c851af460fa595bd959398a8f1.png


思路:


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

左右括号为空,省略

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️⃣二叉树的层序遍历

题目地址:传送


0a2653c851af460fa595bd959398a8f1.png


解题思路:


要控制一层一层的出,定义一个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


0a2653c851af460fa595bd959398a8f1.png

要求反过来输出

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


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

题目链接:传送


2d65d23f6d4748949b924e4057485923.png


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

此处函数的起名很重要

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️⃣ 二叉搜索树与双向链表

题目地址:传送


0a2653c851af460fa595bd959398a8f1.png



思路:


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️⃣从前序与中序遍历序列构造二叉树

题目链接:传送


0a2653c851af460fa595bd959398a8f1.png


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


思路:


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

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

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);
    }
};


相关文章
|
21天前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
71 8
|
25天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
1月前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
26 7
|
1月前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
24 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
1月前
|
存储 算法 搜索推荐
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
26 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
|
1月前
|
Java
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
28 1
|
1月前
|
算法 Java C语言
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
25 1
|
1月前
|
存储
【数据结构】二叉树链式结构——感受递归的暴力美学
【数据结构】二叉树链式结构——感受递归的暴力美学
|
1月前
|
存储 编译器 C++
【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析
【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析
|
1月前
|
存储 算法 调度
数据结构--二叉树的顺序实现(堆实现)
数据结构--二叉树的顺序实现(堆实现)