C++二叉树进阶——二叉搜索树

二叉搜索树

• 1. 二叉树的概念
• 2. 二叉树的实现
• • 2.1创建节点类
  • 2.2 查找Find
  • 2.3 插入Insert
  • 2.4 删除Erase
  • 2.5 中序遍历
  • 2.6 构造/析构
  • 3. 递归实现
  • • 3.1 查找FindR
    • 3.2 插入InsertR
    • 3.3 删除EraseR
    • 4.���体代码

      1. 二叉树的概念

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

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

        2. 二叉树的实现

        2.1创建节点类

        template struct BSTreeNode{typedef BSTreeNode Node;Node* _left;Node* _right;T _key;BSTreeNode(const T& val):_left(nullptr),_right(nullptr),_key(val){}};

        2.2 查找Find

        • 查找就很简单了，因为搜索二叉树的结构特殊，任何一个节点的左节点都小于父节点，任何一个节点的右节点都大于父节点。所以搜索一个值只需要判断大于这个节点还是小于这个节点。如果小于则往左节点走，如果大于则往右节点走。

          bool Find(const T& val){Node* cur = _root;while (cur){if (val > cur->_key) cur = cur->_right;else if (val _key) cur = cur->_left;else return true;}return false;}

          2.3 插入Insert

          • 插入也是同样的道理，大于某个节点就往右走，小于某个节点就往左走。直到为空，这个节点就是我们要插入的点。但是因为树是单向的，所以同样要有个parent指针用来记录上一个节点，便于链接节点。

            注意细节：

            1. 当插入的节点是第一个节点的时候。
            2. 链接的时候是连接左节点还是右节点。

            bool Insert(const T& val){//记录链接的节点。Node* parent = nullptr;Node* cur = _root;//当插入的节点是第一个节点时if (_root == nullptr){_root = new Node(val);return true;}while (cur){if (val > cur->_key){parent = cur;cur = cur->_right;}else if (val _key){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(val);//判断是链接右节点还是左节点。if (parent->_key _right = cur;elseparent->_left = cur;return true;}

            2.4 删除Erase

            删除分三种情况：

            1. 要删除的节点的左节点为空。
            2. 要删除的节点的右节点为空。
            3. 要删除的左右节点都不为空。

            bool Erase(const T& val){Node* cur = _root;Node* parent = nullptr;while (cur){if (val > cur->_key){parent = cur;cur = cur->_right;}else if (val _key){parent = cur;cur = cur->_left;}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;}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{//替换法//这里要注意力RightMin不能定义成nullptr，因为如果删除的是头节点就会出现野指针的问题，所以这里要定义成curNode* RightMin = cur;//定义右子树，找到右子树最左节点Node* RightCur = cur->_right;while (RightCur->_left){RightMin = RightCur;RightMin = RightMin->_left;}//交换值swap(RightCur->_key, cur->_key);if (RightMin->_left == RightCur){RightMin -> _left = RightCur->_right;}else{RightMin->_right = RightCur->_right;}delete RightCur;}return true;}}return false;}

            2.5 中序遍历

            这里我们会发现中序遍历搜索二叉树得到是一个有序的数列。

            //这里说明一下，因为中序是要使用到递归的，也就是要传_root成员变量的。//但是我们又不能修改_root所以要额外写一个函数来是由递归。void Inorder(){_Inorder(_root);cout _left);cout _key _right);}

            2.6 构造/析构

            BSTree(Node* root = nullptr):_root(root){}BSTree(const BSTree& b){_root = Copy(b._root);}BSTree& operator=(BSTree b){swap(_root, b._root);return *this;}~BSTree(){Destroy(_root);}private://前序常见节点Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* newNode = new Node(root->_key);newNode->_left = Copy(root->_left);newNode->_right = Copy(root->_right);return newNode;}//后序delete节点void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);}

            3. 递归实现

            递归版本的整体思路是一样的。

            3.1 查找FindR

            bool FindR(const T& val){return _FindR(val, _root);}bool _FindR(const T& val, Node* root){if (root == nullptr)return false;if (val > root->_key)return _FindR(val, root->_right);else if (val _key)return _FindR(val, root->_left);elsereturn true;}

            3.2 插入InsertR

            bool InsertR(const T& val){return _InsertR(val, _root);}bool _InsertR(const T& val, Node*& root){if (root == nullptr){root = new Node(val);return true;}if (val > root->_key)return _InsertR(val, root->_right);else if (val _key)return _InsertR(val, root->_left);elsereturn false;}

            3.3 删除EraseR

            删除也是一样的参数传递Node*& root

            但是当删除的节点左右都不为空的时候就可以不用替换法了，只需要将将最左节点和删除的点swap一下，在递归删除节点指向的_right也就是右子树再次递归一下即可。

            bool EraseR(const T& val){return _EraseR(val, _root);}bool _EraseR(const T& val, Node*& root){if (root == nullptr)return false;if (val > root->_key)return _EraseR(val, root->_right);else if (val _key)return _EraseR(val, root->_left);else{Node* del = root;if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{Node* cur = root->_right;while (cur->_left){cur = cur->_left;}//交换cur节点和最左节点swap(root->_key, cur->_key);递归右子树return _EraseR(val, root->_right);}delete del;return true;}}

            4.整体代码

            #pragma once#include using namespace std;template struct BSTreeNode{typedef BSTreeNode Node;Node* _left;Node* _right;T _key;BSTreeNode(const T& val):_left(nullptr),_right(nullptr),_key(val){}};template class BSTree{typedef BSTreeNode Node;public:BSTree(Node* root = nullptr):_root(root){}BSTree(const BSTree& b){_root = Copy(b._root);}BSTree& operator=(BSTree b){swap(_root, b._root);return *this;}~BSTree(){Destroy(_root);}bool Find(const T& val){Node* cur = _root;while (cur){if (val > cur->_key) cur = cur->_right;else if (val _key) cur = cur->_left;else return true;}return false;}bool Insert(const T& val){Node* parent = nullptr;Node* cur = _root;if (_root == nullptr){_root = new Node(val);return true;}while (cur){if (val > cur->_key){parent = cur;cur = cur->_right;}else if (val _key){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(val);if (parent->_key _right = cur;elseparent->_left = cur;return true;}bool Erase(const T& val){Node* cur = _root;Node* parent = nullptr;while (cur){if (val > cur->_key){parent = cur;cur = cur->_right;}else if (val _key){parent = cur;cur = cur->_left;}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;}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* RightMin = cur;Node* RightCur = cur->_right;while (RightCur->_left){RightMin = RightCur;RightMin = RightMin->_left;}swap(RightCur->_key, cur->_key);if (RightMin->_left == RightCur){RightMin -> _left = RightCur->_right;}else{RightMin->_right = RightCur->_right;}delete RightCur;}return true;}}return false;}void Inorder(){_Inorder(_root);cout  root->_key)return _EraseR(val, root->_right);else if (val _key)return _EraseR(val, root->_left);else{Node* del = root;if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{Node* cur = root->_right;while (cur->_left){cur = cur->_left;}swap(root->_key, cur->_key);return _EraseR(val, root->_right);}delete del;return true;}}bool _InsertR(const T& val, Node*& root){if (root == nullptr){root = new Node(val);return true;}if (val > root->_key)return _InsertR(val, root->_right);else if (val _key)return _InsertR(val, root->_left);elsereturn false;}bool _FindR(const T& val, Node* root){if (root == nullptr)return false;if (val > root->_key)return _FindR(val, root->_right);else if (val _key)return _FindR(val, root->_left);elsereturn true;}private:Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* newNode = new Node(root->_key);newNode->_left = Copy(root->_left);newNode->_right = Copy(root->_right);return newNode;}void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout _key _right);}private:Node* _root = nullptr;};