二叉搜索树
1. 二叉树的概念2. 二叉树的实现2.1创建节点类2.2 查找Find2.3 插入Insert2.4 删除Erase2.5 中序遍历2.6 构造/析构 3. 递归实现3.1 查找FindR3.2 插入InsertR3.3 删除EraseR 4.整体代码
1. 二叉树的概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值若它的右子树不为空，则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树2. 二叉树的实现
2.1创建节点类
template <class T>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 < cur->_key) cur = cur->_left;else return true;}return false;}2.3 插入Insert
插入也是同样的道理，大于某个节点就往右走，小于某个节点就往左走。直到为空，这个节点就是我们要插入的点。但是因为树是单向的，所以同样要有个parent指针用来记录上一个节点，便于链接节点。注意细节：
当插入的节点是第一个节点的时候。链接的时候是连接左节点还是右节点。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 < cur->_key){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(val);//判断是链接右节点还是左节点。if (parent->_key < val)parent->_right = cur;elseparent->_left = cur;return true;}2.4 删除Erase
删除分三种情况：
要删除的节点的左节点为空。要删除的节点的右节点为空。要删除的左右节点都不为空。
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 < cur->_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 << endl;}private:void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_key << " ";_Inorder(root->_right);}2.6 构造/析构
BSTree(Node* root = nullptr):_root(root){}BSTree(const BSTree<T>& b){_root = Copy(b._root);}BSTree<T>& operator=(BSTree<T> 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 < root->_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 < root->_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 < root->_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 <iostream>using namespace std;template <class T>struct BSTreeNode{typedef BSTreeNode Node;Node* _left;Node* _right;T _key;BSTreeNode(const T& val):_left(nullptr),_right(nullptr),_key(val){}};template <class T>class BSTree{typedef BSTreeNode<T> Node;public:BSTree(Node* root = nullptr):_root(root){}BSTree(const BSTree<T>& b){_root = Copy(b._root);}BSTree<T>& operator=(BSTree<T> 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 < cur->_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 < cur->_key){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(val);if (parent->_key < val)parent->_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 < cur->_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 << endl;}///递归版本/bool FindR(const T& val){return _FindR(val, _root);}bool InsertR(const T& val){return _InsertR(val, _root);}bool EraseR(const T& val){return _EraseR(val, _root);}private:bool _EraseR(const T& val, Node*& root){if (root == nullptr)return false;if (val > root->_key)return _EraseR(val, root->_right);else if (val < root->_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 < root->_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 < root->_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 << root->_key << " ";_Inorder(root->_right);}private:Node* _root = nullptr;};
