【C++高階一】二叉搜索樹剖析
- 1.什么是二叉搜索樹
- 2.二叉搜索樹非遞歸實現
- 2.1插入
- 2.2刪除
- 2.2.1刪除分析一
- 2.2.2刪除分析二
- 2.3查找
- 3.二叉搜索樹遞歸實現
- 3.1插入
- 3.2刪除
- 3.3查找
- 4.完整代碼
1.什么是二叉搜索樹
任何一個節點，他的左子樹的所有節點都比他小，右子樹的所有節點都比他大
二叉搜索樹是有序的，中序遍歷這棵二叉搜索樹剛好是升序
時間復雜度為O(N)，因為會出現這種極端情況
二叉搜索樹中不能出現值相同的節點
2.二叉搜索樹非遞歸實現
大致框架
template<class K>
struct BSTreeNode //二叉搜索樹節點
{BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;BSTreeNode(const K& key):_left(nullptr),_right(nullptr),_key(key){}
};template<class K>
class BSTree//二叉搜索樹
{typedef BSTreeNode<K> Node;
public:private:Node* _root = nullptr;
};
2.1插入
插入的值比根大就往右走，比根小就往左走，如果遇見和插入值相同的值就返回false
bool insert(const k& key){if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(key);if (parent->_key > key){parent->_left = cur;}else {parent->_right = cur;}return true;}
parent保存每一步的父節點，在插入之后起到父子節點連接作用
2.2刪除
2.2.1刪除分析一
- 被刪除節點無孩子：
直接將此節點刪除，不用做特殊處理 - 被刪除節點只有左孩子：
此節點被刪除后，將此節點的左孩子連接到此節點的父親節點 - 被刪除節點只有右孩子：
此節點被刪除后，將此節點的右孩子連接到此節點的父親節點
bool erase(const k& key)
{Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if(cur->_key > key){parent = cur;cur = cur->_right;}else//找到了{if (cur->_left == nullptr)//左孩子為空{if (cur == _root)_root = cur->_right;else{if (cur == parent->_right)parent->_right = cur->_right;elseparent->_left = cur->_right;}delete cur;}else if (cur->_right == nullptr)//右孩子為空{if (cur == _root)_root = cur->_left;else{if (cur == parent->_right)parent->_right = cur->_leftelseparent->_left = cur->_left;}delete cur;}//第四種情況 //else{}}}return false；
}
表面只寫了兩種情況，其實已經把無孩子的情況包括了
2.2.2刪除分析二
當被刪除的節點存在左右孩子時，我們要使用替換法
被替換的節點一定要滿足一個條件:
是左子樹的最大值 || 是右子樹的最小值
假設使用右子樹中最小的節點來替換，其左孩子為空，但右孩子未知，還需要分情況討論
else//左右孩子都不為空
{//用右子樹最小值來替換Node* Temp_parent = cur;//臨時父節點Node* R_subtree_min = cur->_right;//右子樹最小值while (R_subtree_min->_left){Temp_parent = R_subtree_min;R_subtree_min = R_subtree_min->_left;}swap(cur->_key, R_subtree_min->_key);if (R_subtree_min == Temp_parent->_left){Temp_parent->_left = R_subtree_min->_right;}else{Temp_parent->_right = R_subtree_min->_right;}delete R_subtree_min;
}
2.3查找
bool find(const K& key)
{Node* cur = _root;while (cur){if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}else{return true;}}return false;
}
3.二叉搜索樹遞歸實現
遞歸實現全都使用了函數嵌套的方式，是為了使用_root這個定義在類中的成員變量
3.1插入
插入的基本思路一樣,但遞歸到空時構建新節點的鏈接有三種方式：
1.多傳一個參數，記錄父節點
2.遞歸到空節點的上一層，比如if(root->_left==NULL) 開始構建節點
3.傳引用
前兩個方法和循環寫法沒什么區別，下面都使用傳引用
bool Re_insert(const K& key)
{return _Re_insert(_root, key);
}bool _Re_insert(Node*& root, const K& key)
{if (root == nullptr){root = new Node(key);return true;}if (root->_key > key){return _Re_insert(root->_left, key);}else if (root->_key < key){return _Re_insert(root->_right, key);}else{return false;}
}
3.2刪除
bool Re_erase(const K& key)
{return _Re_erase(_root, key);
}
bool _Re_erase(Node*& root, const K& key)
{if (root == nullptr)return false;if (root->_key > key){return _Re_erase(root->_left, key);}else if (root->_key < key){return _Re_erase(root->_right, key);}else//找到了，準備刪除{if (root->_left == nullptr)//左孩子為空{Node* temp = root;root = root->_right;delete temp;return true;}else if (root->_right == nullptr)//右孩子為空{Node* temp = root;root = root->_left;delete temp;return true;}else//左右孩子都不為空{//找右子樹的最小值Node* temp = root->_right;while (temp->_left){temp = temp->_left;}swap(root->_key, temp->_key);return _Re_erase(root->_right, key);}}
}
3.3查找
bool Re_find(const K& key)
{return _Re_find(_root, key);
}
private:
bool _Re_find(Node* root,const K& key)
{if (root == nullptr)return false;if (root->_key > kry){return _Re_find(root->_left, key);}else if (root->_key < kry){return _Re_find(root->_right, key);}else{return true;}
}
4.完整代碼
template<class K>
struct BSTreeNode //二叉搜索樹節點
{BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;BSTreeNode(const K& key):_left(nullptr),_right(nullptr),_key(key){}
};template<class K>
class BSTree//二叉搜索樹
{typedef BSTreeNode<K> Node;
public:bool insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(key);if (parent->_key > key){parent->_left = cur;}else {parent->_right = cur;}return true;}bool erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if(cur->_key < key){parent = cur;cur = cur->_right;}else//找到了,準備刪除{if (cur->_left == nullptr)//左孩子為空{if (cur == _root)_root = cur->_right;else{if (cur == parent->_right)parent->_right = cur->_right;elseparent->_left = cur->_right;}delete cur;}else if (cur->_right == nullptr)//右孩子為空{if (cur == _root)_root = cur->_left;else{if (cur == parent->_right)parent->_right = cur->_leftelseparent->_left = cur->_left;}delete cur;}else//左右孩子都不為空{//用右子樹最小值來替換Node* Temp_parent = cur;//臨時父節點Node* R_subtree_min = cur->_right;//右子樹最小值while (R_subtree_min->_left){Temp_parent = R_subtree_min;R_subtree_min = R_subtree_min->_left;}swap(cur->_key, R_subtree_min->_key);if (R_subtree_min == Temp_parent->_left){Temp_parent->_left = R_subtree_min->_right;}else{Temp_parent->_right = R_subtree_min->_right;}delete R_subtree_min;}return true;}}return false;}bool find(const K& key){Node* cur = _root;while (cur){if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}else{return true;}}return false;}bool Re_insert(const K& key){return _Re_insert(_root, key);}bool Re_erase(const K& key){return _Re_erase(_root, key);}bool Re_find(const K& key){return _Re_find(_root, key);}
private:bool _Re_insert(Node*& root, const K& key){if (root == nullptr){root = new Node(key);return true;}if (root->_key > key){return _Re_insert(root->_left, key);}else if (root->_key < key){return _Re_insert(root->_right, key);}else{return false;}}bool _Re_erase(Node*& root, const K& key){if (root == nullptr)return false;if (root->_key > key){return _Re_erase(root->_left, key);}else if (root->_key < key){return _Re_erase(root->_right, key);}else//找到了，準備刪除{if (root->_left == nullptr)//左孩子為空{Node* temp = root;root = root->_right;delete temp;return true;}else if (root->_right == nullptr)//右孩子為空{Node* temp = root;root = root->_left;delete temp;return true;}else//左右孩子都不為空{//找右子樹的最小值Node* temp = root->_right;while (temp->_left){temp = temp->_left;}swap(root->_key, temp->_key);return _Re_erase(root->_right, key);}}}bool _Re_find(Node* root,const K& key){if (root == nullptr)return false;if (root->_key > kry){return _Re_find(root->_left, key);}else if (root->_key < kry){return _Re_find(root->_right, key);}else{return true;}}
private:Node* _root = nullptr;
};
)
