目錄

1.二叉搜索樹的基本概念

1.1二叉搜索樹的基本特征

?2.二叉搜索樹的實(shí)現(xiàn)

2.1數(shù)據(jù)的插入(迭代實(shí)現(xiàn))

2.2數(shù)據(jù)的搜索(迭代實(shí)現(xiàn))

2.3中序遍歷(遞歸實(shí)現(xiàn))

2.4數(shù)據(jù)的刪除(迭代實(shí)現(xiàn))

2.5數(shù)據(jù)的搜索(遞歸實(shí)現(xiàn))

2.6數(shù)據(jù)的插入(遞歸實(shí)現(xiàn))

2.7數(shù)據(jù)的刪除(遞歸實(shí)現(xiàn))

2.8類的完善

3.二叉搜索樹的應(yīng)用

4.完整代碼

?二叉搜索樹

1.二叉搜索樹的基本概念

二叉搜索樹又稱二叉排序樹，它可以是一顆空樹。二叉搜索樹的作用是搜索，排序(二叉搜索樹的中序遍歷是一組遞增有序數(shù)據(jù))。

1.1二叉搜索樹的基本特征

如果某顆二叉樹(包括空樹)滿足以下性質(zhì)，可以作為一顆二叉搜索樹：

????????1.如果左子樹不為空，其鍵值應(yīng)小于根節(jié)點(diǎn)的鍵值。

????????2.如果右子樹不為空，其鍵值應(yīng)大于根節(jié)點(diǎn)的鍵值。

????????3.左右子樹都滿足上述條件。

沒有二叉搜索樹之前，常用的查找算法為二分查找。但是二分查找是有局限性的(必須針對有序數(shù)組)。二叉搜索樹因其特性，例如我們需要查找Key值，只需要與根節(jié)點(diǎn)的鍵值做比較：若Key小于根節(jié)點(diǎn)的鍵值，則往根節(jié)點(diǎn)的左子樹遍歷；若Key值大于根節(jié)點(diǎn)的鍵值，則往根節(jié)點(diǎn)的右子樹遍歷。經(jīng)計(jì)算，查找的次數(shù)等于二叉搜索樹的深度。正因?yàn)槿绱?#xff0c;二叉搜索樹并不是一個(gè)優(yōu)秀的數(shù)據(jù)結(jié)構(gòu)，因?yàn)橐坏龅綐O端情況，二叉搜索樹的搜索效率將會(huì)大打折扣。所以在往后的章節(jié)中，將會(huì)使其平衡。

?2.二叉搜索樹的實(shí)現(xiàn)

?將二叉搜索樹定義為一個(gè)類，現(xiàn)在將展示類的框架。往后所有的演示代碼，都可以直接加入其中：

// 節(jié)點(diǎn)
template <class K>
struct BST_node
{BST_node<K>* _left;		//左子樹BST_node<K>* _right;	//右子樹K _key;BST_node(const K& _key):_key(key),_left(nullptr),_right(nullptr){}
};template <class K>		//節(jié)點(diǎn)鍵值的數(shù)據(jù)類型
class BST
{typedef BST_node<K> Node;
public:private:Node* _root;	//根節(jié)點(diǎn)
};

2.1數(shù)據(jù)的插入(迭代實(shí)現(xiàn))

bool insert(const K& key)
{if (_root == nullptr){_root = new Node(key);return true;}Node* prev = nullptr;	// cur的父節(jié)點(diǎn)Node* cur = _root;while (cur){if (key < cur->_key)	//如果比根節(jié)點(diǎn)的鍵值小{prev = cur;cur = cur->_left;}else if(key > cur->_key)	//如果比根節(jié)點(diǎn)的鍵值大{prev = cur;cur = cur->_right;}else{// 我們不允許插入重復(fù)的數(shù)據(jù)return false;}}// 直到遍歷到空，才施行插入cur = new Node(key);if (key < prev->_key){prev->_left = cur;}else if (key > prev->_key){prev->_right = cur;}return true;
}

2.2數(shù)據(jù)的搜索(迭代實(shí)現(xiàn))

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

2.3中序遍歷(遞歸實(shí)現(xiàn))

void MidTraval()	//此接口作公有
{__MidTraval(_root);cout << endl;
}void __MidTraval(Node* root)	//此接口做私有
{if (root == nullptr){return;}__MidTraval(root->_left);cout << root->_key << " ";__MidTraval(root->_right);
}

2.4數(shù)據(jù)的刪除(迭代實(shí)現(xiàn))

需要注意，要?jiǎng)h除二叉搜索樹的節(jié)點(diǎn)，就必須分兩種情況討論：

????????1.要?jiǎng)h除節(jié)點(diǎn)的左子樹或右子樹為空。

????????2.要?jiǎng)h除節(jié)點(diǎn)的左、右子樹都不為空。

bool erase(const K& key)
{if (_root == nullptr){return false;}Node* prev = _root;Node* cur = _root;while (cur){if (key < cur->_key){prev = cur;cur = cur->_left;}else if (key > cur->_key){prev = cur;cur = cur->_right;}else{// 如果左子樹為空if (cur->_left == nullptr){// 假設(shè)右子樹不為空，則將右子樹托孤給父節(jié)點(diǎn)if (_root == cur){_root = _root->_right;}else if (prev->_left == cur){prev->_left = cur->_right;}else if (prev->_right == cur){prev->_right = cur->_right;}delete cur;return true;}// 如果右子樹為空else if (cur->_right == nullptr){//假設(shè)左子樹不為空，則將左子樹托孤給父節(jié)點(diǎn)if (_root == cur){_root = _root->_left;}else if (prev->_left == cur){prev->_left = cur->_left;}else if (prev->_right == cur){prev->_right = cur->_left;}delete cur;return true;}// 如果左右子樹都不為空else{// 假設(shè)使用右子樹的最小值替代Node* prev = _root;Node* minRight = cur->_right;while (minRight->_left)		//二叉樹特性，越往左越小{prev = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;// 替換好后，就要?jiǎng)h除minRightif (prev->_left == minRight){prev->_left = minRight->_right;}else if (prev->_right == minRight){prev->_right = minRight->_right;}delete minRight;return true;}}}return false;
}

2.5數(shù)據(jù)的搜索(遞歸實(shí)現(xiàn))

bool findR(const K& key)
{return __findR(_root, key);
}bool __findR(Node* root, const K& key)	//此接口作私有
{if (root == nullptr){return false;}if (key < root->_key){return __findR(root->_left, key);}else if (key > root->_key){return __findR(root->_right, key);}return true;
}

2.6數(shù)據(jù)的插入(遞歸實(shí)現(xiàn))

bool insertR(const K& key)
{return __insertR(_root, key);
}bool __insertR(Node*& root, const K& key)	//此接口作私有
{if (root == nullptr){root = new Node(key);	//注意引用傳參，root相當(dāng)于root->left或root->right的別名return true;}if (key < root->_key){return __insertR(root->_left, key);}else if (key > root->_key){return __insertR(root->_right, key);}return false;
}

2.7數(shù)據(jù)的刪除(遞歸實(shí)現(xiàn))

bool eraseR(const K& key)
{return __eraseR(_root, key);
}bool __eraseR(Node*& root, const K& key)	//此接口作私有
{if (root == nullptr){return false;}if (key < root->_key){return __eraseR(root->_left, key);}else if (key > root->_key){return __eraseR(root->_right, key);}else{Node* del = root;if (root->_left == nullptr){// 此時(shí)root就是要?jiǎng)h除的節(jié)點(diǎn)，并且是root的父節(jié)點(diǎn)的子節(jié)點(diǎn)的引用(root == root->_left...)root = root->_right;delete del;return true;}else if (root->_right == nullptr){root = root->_left;delete del;return true;}else{Node* prev = _root;Node* minRight = root->_right;while (minRight->_left)		//二叉樹特性，越往左越小{prev = minRight;minRight = minRight->_left;}root->_key = minRight->_key;// 替換好后，就要?jiǎng)h除minRightif (prev->_left == minRight){prev->_left = minRight->_right;}else if (prev->_right == minRight){prev->_right = minRight->_right;}delete minRight;return true;}}return false;
}

2.8類的完善

BST():_root(nullptr)
{}~BST()
{Destructor(_root);_root = nullptr;
}void Destructor(Node* root)	//此函數(shù)作私有
{if (root == nullptr){return;}// 后序刪除Destructor(root->_left);Destructor(root->_right);delete root;
}BST(const BST<K>& t)
{_root = Copy(t._root);
}Node* Copy(Node* root)	//此接口作私有
{if (root == nullptr){return nullptr;}Node* ret = new Node(root->_key);ret->_left = Copy(root->_left);ret->_right = Copy(root->_right);return ret;
}BST<K>& operator==(BST<K> t)	//現(xiàn)代寫法
{swap(_root, t._root);return *this;
}

3.二叉搜索樹的應(yīng)用

1.K模型：

????????K模型即只有key作為關(guān)鍵碼，結(jié)構(gòu)中只需要存儲Key即可，關(guān)鍵碼即為需要搜索到的值。上面模擬實(shí)現(xiàn)的搜索就是K模型。

? ? ? ? 例如將英文字典所有的英文單詞存儲二叉搜索樹這個(gè)數(shù)據(jù)結(jié)構(gòu)，那么可將英文單詞看作關(guān)鍵碼Key，假設(shè)我們想查找"hello"這個(gè)單詞，直接去數(shù)據(jù)結(jié)構(gòu)找即可。

2.KV模型：

????????每一個(gè)關(guān)鍵碼key，都有與之對應(yīng)的值Value，即<Key, Value>的鍵值對。該種方式在現(xiàn)實(shí)生活中非常常見。

? ? ? ? 例如英漢互譯，一個(gè)英文單詞對應(yīng)了多個(gè)漢語翻譯。我們將<英文單詞，中文翻譯的數(shù)組>這樣的鍵值對放入二叉搜索樹中。例如查找"hello"這個(gè)單詞的中文翻譯，只需要查找鍵值對的英文單詞即可。

KV模型例題：

給定下面數(shù)組，求每種水果出現(xiàn)的次數(shù)：

string arr[] = { "蘋果", "西瓜", "蘋果", "西瓜", "蘋果", "蘋果", "西瓜",
"蘋果", "香蕉", "蘋果", "香蕉" };

第一步：先實(shí)現(xiàn)二叉搜索樹(為了方便，這里只保留插入數(shù)據(jù)、查找和中序遍歷的接口)：

namespace KV
{// 節(jié)點(diǎn)template <class Key,class Val>struct BST_node{BST_node<Key,Val>* _left;		//左子樹BST_node<Key,Val>* _right;	//右子樹Key _key;Val _val;BST_node(const Key& key,const Val& val):_key(key), _val(val),_left(nullptr), _right(nullptr){}};template <class Key,class Val>class BST{typedef BST_node<Key,Val> Node;public:bool insert(const Key& key,const Val& val){if (_root == nullptr){_root = new Node(key,val);return true;}Node* prev = nullptr;Node* cur = _root;while (cur){if (key < cur->_key){prev = cur;cur = cur->_left;}else if (key > cur->_key){prev = cur;cur = cur->_right;}else{return false;}}cur = new Node(key,val);if (key < prev->_key){prev->_left = cur;}else if (key > prev->_key){prev->_right = cur;}return true;}Node* find(const Key& key){if (_root == nullptr){return nullptr;}Node* cur = _root;while (cur){if (key < cur->_key){cur = cur->_left;}else if (key > cur->_key){cur = cur->_right;}else{// 找到了return cur;}}return nullptr;}bool erase(const Key& key){if (_root == nullptr){return false;}Node* prev = _root;Node* cur = _root;while (cur){if (key < cur->_key){prev = cur;cur = cur->_left;}else if (key > cur->_key){prev = cur;cur = cur->_right;}else{if (cur->_left == nullptr){if (_root == cur){_root = _root->_right;}else if (prev->_left == cur){prev->_left = cur->_right;}else if (prev->_right == cur){prev->_right = cur->_right;}delete cur;return true;}else if (cur->_right == nullptr){if (_root == cur){_root = _root->_left;}else if (prev->_left == cur){prev->_left = cur->_left;}else if (prev->_right == cur){prev->_right = cur->_left;}delete cur;return true;}else{Node* prev = _root;Node* minRight = cur->_right;while (minRight->_left){prev = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;if (prev->_left == minRight){prev->_left = minRight->_right;}else if (prev->_right == minRight){prev->_right = minRight->_right;}delete minRight;return true;}}}return false;}void MidTraval()	{__MidTraval(_root);cout << endl;}private:Node* _root = nullptr;void __MidTraval(Node* root){if (root == nullptr){return;}__MidTraval(root->_left);cout << root->_key << ":" << root->_val << endl;__MidTraval(root->_right);}};
}

第二步：算法實(shí)現(xiàn)：

void test_count()
{KV::BST<string, int> bt;string arr[] = { "蘋果", "西瓜", "蘋果", "西瓜", "蘋果", "蘋果", "西瓜",
"蘋果", "香蕉", "蘋果", "香蕉" };for (auto& e : arr){KV::BST_node<string, int>* ret = bt.find(e);if (ret)	//不為空，證明數(shù)據(jù)結(jié)構(gòu)已有{ret->_val++;	//次數(shù)++}else{bt.insert(e, 1);}}bt.MidTraval();
}

4.完整代碼

?二叉搜索樹