首页 > 编程语言 >C++----二叉树的进阶

C++----二叉树的进阶

时间：2022-10-03 11:33:47浏览次数：67  
标签：Node return cur C++ ---- 二叉树 key root left


文章目录

前言

这章我们来学习二叉树的进阶之搜索二叉树，为了更好的学习C++的map和set容器做的铺垫，这节课我们需要先了解二叉搜索树的特性，之前使用C语言去完成有些OJ可能非常困难，结合今天的学习，我们也可以对初阶的二叉树进行收尾。

​​正文开始​​

一、二叉搜索树

2.1 二叉搜索树概念

二叉搜索树又称二叉排序树(Binary Search Tree)，它或者是一棵空树，或者是具有以下性质的二叉树:
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树

C++----二叉树的进阶_算法


第一个树不是二叉搜索树，因为10的右子树5大于该子树的根节点，不满足二叉搜索树的特性！

2.2二叉树节点

struct BSTreeNode
{
  BSTreeNode(const K& key)//节点的构造函数
    :_left(nullptr)
    ,_right(nullptr)
    ,_key(key)
  {}
  BSTreeNode<K>* _left;
  BSTreeNode<K>* _right;
  K _key;
};

2.3 二叉搜索树操作

C++----二叉树的进阶_子树_02

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

1. 二叉搜索树的查找

a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
b、最多查找高度次，走到到空，还没找到，这个值不存在。

如上图比如我们要找7这个数字
7<8排除右子树，在左子树找查找
7>3排除左子树，在右子树中查询
6>7排除右子树，在左子树找查找
7==7则找到该数
否则该数就在搜索二叉树中不存在

2. 二叉搜索树的插入

插入的具体过程如下：
a. 树为空，则直接新增节点，赋值给root指针
b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

C++----二叉树的进阶_算法_03


一般我们对于数据结构最重要的就是增删查改，增加和查找我们已经了解了，下来看看删除吧！

3. 搜索二叉树的删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情
况：
a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点

看起来有待删除节点有4种情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程
如下：

情况A如下

C++----二叉树的进阶_二叉搜索树_04

情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除
情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除

C++----二叉树的进阶_二叉搜索树_05

情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点

中，再来处理该结点的删除问题–替换法删除

C++----二叉树的进阶_子树_06

2.4 二叉搜索树的实现

首先是非递归实现

template<class K>
class BSTree
{
  typedef BSTreeNode<K> Node;
public:
  //强制编译器自己生成构造
  BSTree() = default;
  //BSTree() {}
  BSTree(const BSTree<K>& t)
  {
    _root=CopyTree(t._root);
  }
  BSTree<K>& operator=(BSTree<K> t)
  {
    swap(_root,t._root);
    return *this;
  }
  ~BSTree()
  {
    DestroyTree(_root);
    _root = nullptr;
  }
  bool Insert(const K& key)
  {
    if (_root == nullptr)
    {
      Node* newNode = new Node(key);
      _root = newNode;
      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;
      }
    }
    Node* newNode = new Node(key);
    if (parent->_key < key)
    {
      parent->_right = newNode;
    }
    else
    {
      parent->_left = newNode;
    }
    return true;
  }
  bool Find(const K& key)
  //const 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 true;
    }
    return false;
  }
  //找左子树的最大值节点或者右子树的最小值节点
  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
      {
        //一个孩子---左为空or右为空
        //两个孩子----替代法
        if (cur->_left==nullptr)
        {
          //if (parent == nullptr)
          if (cur == _root)
          {
            _root = cur->_right;
          }
          else
          {
            if (parent->_left == cur)
            {
              parent->_left = cur->_right;
            }
            else
            {
              parent->_right = cur->_right;
            }
          }
          delete cur;
        }
        else if (cur->_right == nullptr)
        {
          if (cur == _root)
          {
            _root = cur->_left;
          }

          if (parent->_left == cur)
          {
            parent->_left = cur->_left;
          }
          else
          {
            parent->_right = cur->_left;
          }
          delete cur;
        }
        //两个孩子都不为空
        //找左子树的最大值节点或者右子树的最小值节点
        else
        {
          //找右子树的最小值节点
          Node* minParent = cur;
          Node* minNode = cur->_right;
          while (minNode->_left)
          {
            minParent = minNode;
            minNode = minNode->_left;
          }
          cur->_key = minNode->_key;
          if (minParent->_left == minNode)
          {
            minParent->_left = minNode->_right;
          }
          else
          {
            minParent->_right = minNode->_right;
          }
          delete minNode;
          //swap(cur->_key, minNode->_key);
          //return Erase(key);
          交换后不满足搜索二叉树，然后找不到3
        }
        return true;
      }  
    }
    return false;
  }
  void Inorder()
  {
    _Inorder(_root);
    cout << endl;
  }
  void DestroyTree(Node* root)
  {
    if (root == NULL)
      return;
    DestroyTree(root->_left);
    DestroyTree(root->_right);
    delete root;
  }
  Node* CopyTree(Node* root)
  {
    if (root == nullptr)
      return nullptr;
    Node* copyNode = new Node(root->_key);
    copyNode->_left = CopyTree(root->_left);
    copyNode->_right = CopyTree(root->_right);
    return copyNode;
  }
private:
  Node* _root=nullptr;
};

递归实现

template<class K>
class BSTree
{
  typedef BSTreeNode<K> Node;
public:
  //强制编译器自己生成构造
  BSTree() = default;
  //BSTree() {}
  BSTree(const BSTree<K>& t)
  {
    _root=CopyTree(t._root);
  }
  BSTree<K>& operator=(BSTree<K> t)
  {
    swap(_root,t._root);
    return *this;
  }
  ~BSTree()
  {
    DestroyTree(_root);
    _root = nullptr;
  }
  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->_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* minRight = root->_right;
        while (minRight->_left)
        {
          minRight= minRight->_left;
        }
        swap(root->_key, minRight->_key);
        return _EraseR(root->_right, minRight->_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->_right);
    }
    else if (root->_key > key)
    {
      return _InsertR(root->_left, key);
    }
    else
    {
      return false;
    }
  }

  bool _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,key);
    }
    else
    {
      return true;
    }
  }

  void _Inorder(Node* root)
  {
    if (root == nullptr)
      return;
    _Inorder(root->_left);
    cout << root->_key << " ";
    _Inorder(root->_right);
  }
  void DestroyTree(Node* root)
  {
    if (root == NULL)
      return;
    DestroyTree(root->_left);
    DestroyTree(root->_right);
    delete root;
  }
  Node* CopyTree(Node* root)
  {
    if (root == nullptr)
      return nullptr;
    Node* copyNode = new Node(root->_key);
    copyNode->_left = CopyTree(root->_left);
    copyNode->_right = CopyTree(root->_right);
    return copyNode;
  }
  Node* _root=nullptr;
};

2.5 二叉搜索树的应用

  1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
    比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
  2. KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方
    式在现实生活中非常常见：
    比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英
    文单词与其对应的中文<word, chinese>就构成一种键值对；
    再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出
    现次数就是<word, count>就构成一种键值对

在这里只需要改变节点的属性即可完成kv模型的实现

template<class K,class V>
  struct BSTreeNode
  {
    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;
    V _value;
  };
  template<class K, class V>
  class BSTree
  {
    typedef BSTreeNode<K, V> Node;
  public:
    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);
      }
      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* minRight = root->_right;
          while (minRight->_left)
          {
            minRight = minRight->_left;
          }
          swap(root->_key, minRight->_key);
          swap(root->_value, minRight->_value);

          return _EraseR(root->_right, minRight->_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 == nullptr)
        return;
      _Inorder(root->_left);
      cout << root->_key << ":" << root->_value << endl;
      _Inorder(root->_right);
    }
    void DestroyTree(Node* root)
    {
      if (root == NULL)
        return;
      DestroyTree(root->_left);
      DestroyTree(root->_right);
      delete root;
    }
    Node* CopyTree(Node* root)
    {
      if (root == nullptr)
        return nullptr;
      Node* copyNode = new Node(root->_key);
      copyNode->_left = CopyTree(root->_left);
      copyNode->_right = CopyTree(root->_right);
      return copyNode;
    }
    Node* _root = nullptr;
  };

2.6 二叉搜索树的性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

C++----二叉树的进阶_算法_07


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

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

问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插

入关键码，二叉搜索树的性能都能达到最优？那么我们后续章节学习的AVL树和红黑树就可以上
场了。

总结

(本章完！)


标签：Node,return,cur,C++,----,二叉树,key,root,left
From： https://blog.51cto.com/u_15612778/5729981

相关文章

  • （未完待续）集合框架——HashSet集合源码分析
    本篇内容是对B站《韩顺平零基础30天学会java》中关于HashSet章节的一个知识回顾和总结HashSet相对比ArrayList、Vector及LinkedList，知识内容和难度有所提高，阅读源码更富......
  • 计网英文复习
    chapter1ComputerNetworksandtheInternet(计算机网络英文题库(含答案)Chapter1ComputerNetworksandtheInternet_清沐沐的博客-CSDN博客_计算机网络英文选择......
  • 【推荐收藏】时间序列分析全面指南（附Python代码）
    大家好，时间序列是在规律性时间间隔上记录的观测值序列。本文我将带你了解在Python中分析给定时间序列的特征的21个全过程。内容较长，建议收藏、点赞、关注。内容​​1.什......
  • websocket2.0 适用于发送的数据体很大
    当websocket发送的数据体积很大,需要的传输时间很长,并且传输频率较高的情况下使用pom配置<dependency><groupId>org.springframework</groupId......
  • TransBigData：一款基于 Python 的超酷炫交通时空大数据工具包
    今天分享一次Python交通数据分析与可视化的实战！其中主要是使用TransBigData库快速高效地处理、分析、挖掘出租车GPS数据。所介绍的相关技术开发了Python开源库TransBigData，......
  • Spring Lombok 实体类死循环问题
    在SpringJPA1对多查询的时候出现死循环的问题。如下图所示：  所有的配置都是正确的的，就是没有办法获得数据，并且出现死循环问题和解决因为使用lombak的 @Data......
  • 英语16时态总结 转自JimBoom
    作者：​​DATA_MONK​​​......
  • [架构之路-10]：目标系统 - 需求分析 - 业务意识、价值意识
    架构师所架构的系统，不单纯的是软件和硬件。架构不仅仅是没有生命的目标软件/硬件系统，在一个公司组织内部，它也承载着公司的长期的价值，承载这为客户解决问题的职责。因此，在架......
  • 【Golang开发面经】深信服（两轮技术面）
    文章目录​​写在前面​​​​一面​​​​了解过切片和数组吗？有什么区别？​​​​那这样初始化可以吗？有什么问题？​​​​用过map吧？怎么遍历map？​​​​那遍历map是有序的......
  • Jupyter notebook 详细安装步骤
    前言：在安装​​Jupyter​​​notebook之前，确认您已安装python编译器（​​点击进入python官网​​）一、开始安装1、打开cmd命令窗口    在键盘上点击  win+r键，......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99