目錄

1.什么是二叉搜索樹

2.二叉搜索樹的查找

3.二叉搜索樹插入

4.二叉搜索樹的刪除

1.刪除的節點只有左子樹或者右子樹

2.刪除節點左右子樹都有的情況

5.代碼

---

1.什么是二叉搜索樹

左節點的值小于根節點

右節點大于根節點

左右子樹也滿足上面兩個條件

例：arr[] = {5,2,1,3,4,7,6,8} 轉化為二叉搜索樹

2.二叉搜索樹的查找

思路：尋找4，4比5小去左子樹尋找-> 4比2大去右子樹尋找->4比3大去右子樹尋找->找到4。

3.二叉搜索樹插入

思路：查找插入元素可以存儲的位置 ，插入。

例：插入9, 9比5大去右子樹尋找->9比7大去右子樹尋找->9比8大去右子樹尋找->找到9可以插入的位置->將9插入8的右子樹。

4.二叉搜索樹的刪除

二叉搜索樹刪除的情況可以分成兩種

1.刪除的節點只有左子樹或者右子樹

?如果刪除節點是刪除節點父親節點的左子樹，那就把刪除節點的左子樹或者右子樹，托付給父親節點的左子樹。

?如果刪除節點是刪除節點父親節點的右子樹，那就把刪除節點的左子樹或者右子樹，托付給父親節點的右子樹。

例：刪除3就把4托付給2的右子樹

? ? ? ?刪除4就把空節點托付給3的右子樹

2.刪除節點左右子樹都有的情況

找左子樹的最右節點或者右子樹的最左節點替換刪除節點，再將左子樹最右節點或者右子樹最左節點刪除，因為最右節點一定沒有右子樹，最左節點一定沒有左子樹，就把問題轉化為情況1了。

例：刪除2

用右子樹的最左節點：3為右子樹最左節點，把3賦值給2，去右子樹把3刪除，把4托付給3的右子樹?。

用左子樹的最右節點：1為左子樹最右節點，把1賦值給2，去左子樹把1刪除，把空節點托付給1的左子樹。

5.代碼

#pragma oncenamespace V
{template<class K>struct BinarySearchTreeNode//節點{typedef struct BinarySearchTreeNode<K> Node;BinarySearchTreeNode():_val(){}BinarySearchTreeNode(const K& val):_val(val){}Node* _left = nullptr;Node* _right = nullptr;K _val;};template <class K>class BST//二叉搜索樹{typedef struct BinarySearchTreeNode<K> Node;public:BST()//構造函數:_root(nullptr){}BST(const BST<K> &t){_root = Copy(t._root);}Node* Copy(Node* root){if (nullptr == root){return nullptr;}Node* newNode = new Node(root->_val);newNode->_left = Copy(root->_left);newNode->_right = Copy(root->_right);return newNode;}BST<K>& operator=(BST<K> t){std::swap(_root,t._root);return *this;}bool Insert(const K& key){if (nullptr == _root){_root = new Node(key);return true;}Node* cur = _root;Node* parent = nullptr;while (nullptr != cur){if (key > cur->_val){parent = cur;cur = cur->_right;}else if (key < cur->_val){parent = cur;cur = cur->_left;}else { return  false; }}Node* newNode = new Node(key);if (parent->_val > newNode->_val){parent->_left = newNode;return true;}else{parent->_right = newNode;return true;}}Node* Find(const K& key){Node* cur = _root;while (nullptr != cur){if (cur->_val > key){cur = cur->_left;}else if (cur->_val < key){cur = cur->_right;}else if (cur->_val == key){return cur;}}return nullptr;}bool Erase(const K& key){Node* cur = _root;Node* parent = _root;while (nullptr != cur){if (cur->_val > key){parent = cur;cur = cur->_left;}else if (cur->_val < key){parent = cur;cur = cur->_right;}else if (cur->_val == key)//找到key{if (nullptr == cur->_left)//當key左子樹為空{if (_root == cur){_root = cur->_right;}else if (cur == parent->_left)//當cur是父親的左子樹{parent->_left = cur->_right;}else if(cur == parent->_right)//cur是父親的右子樹{parent->_right = cur->_right;}delete cur;cur = nullptr;return true;}else if (nullptr == cur->_right)//key的右子樹為空{if(cur == _root){ _root = cur->_left;}else if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_left;}delete cur;cur = nullptr;return true;}else //左右子樹都不為空 {Node* LNode = cur->_left;Node* LParent = cur;while (LNode->_right)//找左子樹的最右節點 替換cur {LParent = LNode;LNode = LNode->_right;}cur->_val = LNode->_val;//修改值//最右節點沒有右子樹if (LNode == LParent->_left){LParent->_left = LNode->_left;}else{LParent->_right = LNode->_left;}delete LNode;LNode = nullptr;return true;}}}return false;}void InOrder(){return _InOrder(_root);}void Destory(){_Destory(_root);}~BST(){Destory();}///遞歸實現bool FindR(const K &val){return _FindR(_root,val);}bool InsertR(const K& val){return _InsertR(_root,val);}bool EraseR(const K& val){return _EraseR(_root, val);}private:Node* _root;void _InOrder(Node* root){if (nullptr == root){return;}std::cout << root->_val << " ";_InOrder(root->_left);_InOrder(root->_right);}void _Destory(Node * root){if (nullptr == root){return;}_Destory(root->_left);_Destory(root->_right);delete root;}bool _InsertR(Node * &root, const K &val){if (nullptr == root){root = new Node(val);return true;}if (root->_val > val)_InsertR(root->_left, val);else if (root->_val < val)_InsertR(root->_right, val);return false;}bool _FindR(Node * root,const K&val){if (nullptr == root)return false;if (root->_val > val)_FindR(root->_left, val);else if (root->_val < val)_FindR(root->_right, val);else return true;}bool _EraseR(Node * &root,const K&val){if (root == nullptr){return false;}if(root->_val > val){_EraseR(root->_left,val);}else if (root->_val < val){_EraseR(root->_right, val);}else{Node* del = root;//當左孩子為空，if (nullptr == root->_left){root = root->_right;}else if (nullptr == root->_right){root = root->_left;}else {Node* leftmax = root->_left;while (leftmax->_right)//左子樹的最右節點{leftmax = leftmax->_right;}swap(leftmax->_val, root->_val);return _EraseR(root->_left,val);}delete del;return true;}}};}