数据结构——二叉搜索树

���录

二叉搜索树的概念

二叉搜索树的实现

创建结点

插入函数

 查找函数

构造函数

拷贝构造函数

赋值运算符重载函数

析构函数

删除函数

如果左为空，右不为空。

 如果右为空，左不为空。

如果左右都不为空 

中序遍历

二叉树的应用之KV模型

见见猪跑（先看看模型的具体实现有什么用）

英汉互译

统计水果个数

---

二叉搜索树的概念

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

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

  例如，下面就是一棵二叉搜索树：

  • 二叉搜索树与普通的二叉树有所不同，如果我们按照中序遍历进行访问结点的值的时候我们可以发现它是一个升序的序列。
  • 每个结点的左子树结点上边的值都小于该结点的值，右子树是上边的值都大于该结点的值。

    二叉搜索树的实现

    创建结点

    首先使用结构体+模板来创建结点，里面需要给出左子树，右子树，结点的值。只需要写一个构造函数对其值赋初值就行了。

    //定义一个结构体 template struct BSTreeNode{BSTreeNode* _left;BSTreeNode* _right;K _key;//构造函数BSTreeNode(const K& key):_key(key), _left(nullptr), _right(nullptr){}};

    插入函数

    1. 首先进行遍历，该key的值比cur中的值大，就向cur的右子树中寻找，反之，向cur的左子树去寻找，直到叶子结点为止，如果与cur的值相同，则返回false（因为二叉搜索树中不允许有相同值的两个结点）。
    2. 判断是否为空树，如果为空树直接返回true（因为已经插入完毕）。
    3. 由于我们插入的过程中需要进行链接，所以我们应当创建一个父结点来跟着我们需要遍历的结点（cur）这样才能完成链接过程。
    4. 跟父结点进行比较，如果比父结点大，放入父结点的右子树。反之，放入父结点的左子树。

    bool Insert(const K& key){//这一步是为 _root 赋值//也就是插入的第一个值if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;//cur获得根的值Node* cur = _root;//若根为空将不进入whilewhile (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key _key){parent = cur;cur = cur->_left;}else//相等{return false;}}cur = new Node(key);if (key > parent->_key){parent->_right = cur;}else{parent->_left = cur;}return true;}

     查找函数

    • key>cur->_key就向cur的右子树中去找；
    • key_key就向cur的左子树中去找；
    • key==cur->_key就返回true；

      bool Find(const K& key){Node* cur = _root;if (key == cur->_key){return true;}while (cur){if (key > cur->_key){cur = cur->_right;}else if (key _key){cur = cur->_left;}else//相等->找到了{return true;}}return false;}

      构造函数

      只需写一个空函数体的构造即可。

      BSTree():_root(nullptr){}

      拷贝构造函数

      递归去拷贝每个二叉搜索树的结点。

      BSTree(const BSTree& t)//拷贝构造函数接口{_root = Copy(t._root);}Node* Copy(Node* root)//拷贝构造函数子函数{if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_key);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}

      赋值运算符重载函数

      BSTree& operator=(BSTree t){swap(_root, t.root);return *this;}

      析构函数

      由于二叉树的特殊结构，我们释放结点的时候应该递归进行；

      注意最后将根节点置空；

      void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}~BSTree(){Destroy(_root);_root = nullptr;}

      删除函数

      删除是二叉搜索树中最重要也是最难的一个函数，我们来使用图形结合的方法来理解它。

      1、如果是叶子结点，则直接删除

      2、①如果左为空，右不为空

            ②如果右为空，左不为空

            ③如果左右都不为空

      如果左为空，右不为空。

      1、若删除的是根节点，那么直接让根结点指向原根结点的右子树。

      2、若删除的不是根节点，那么将它的子树托孤给它的父节点。

       如果右为空，左不为空。

      1、若删除的是根节点，那么直接让根结点指向原根结点的左子树。

      2、若删除的不是根节点，那么将它的子树托孤给它的父节点。

      如果左右都不为空 

       由于这种情况比较复杂，并且考虑到删除不能破坏二叉搜索树的性质。我们创建了一个辅助结点变量minright（被删结点右子树中的最左结点），来解决这个问题。

      1、若所需要删除的结点的右结点是其右子树的最左结点

      将minright的值赋给cur然后直接使cur的右结点变为minright的右结点。

      2、 若所需要删除的结点的右结点不是其右子树的最左结点

      交换cur与minright的值，然后让minright的父节点的的左指针指向minright的右指针。

       

      bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key _key){parent = cur;cur = cur->_left;}else//找到结点了{//1、左为空//2、右为空//3、左右都不为空//4、注意如果左右都为空无论走哪个都行 //因为cur的两个子节点都为空无论走哪个都是将cur的子节点给给cur的父节点if (cur->_left == 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;}else{if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else{Node* minright = cur->_right;Node* parent = cur;//寻找最小结点while (minright->_left){parent = minright;minright = minright->_left;}cur->_key = minright->_key;if (minright == parent->_right){parent->_right = minright->_right;}else{parent->_left = minright->_right;}delete minright;}return true;}}return false;}

      中序遍历

      因为二叉搜索树的特殊性质，我们可以写一个中序遍历来判断构建的二叉搜索树是否正确。

      void _InOrder(Node* root)//中序遍历子函数{if (root == nullptr){return;}_InOrder(root->_left);cout _key _right);}void InOrder()//中序遍历调用接口{_InOrder(_root);cout  cur->_key){parent = cur;cur = cur->_right;}else if (key _key){parent = cur;cur = cur->_left;}else{return false;}}//这一步是为了链接并且将key和value给定curcur = new Node(key, value);if (parent->_key _right = cur;}else{parent->_left = cur;}return true;}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_key _right;}else if (cur->_key > key){cur = cur->_left;}else{return cur;}}return nullptr;}void Inorder(){_Inorder(_root);}void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout _key > str){//Find返回的是结点的指针KV::BSTreeNode* ret = dict.Find(str);if (ret){cout _value