目錄

概念

?性能分析

?二叉搜索樹(shù)的插入

二叉樹(shù)的查找

二叉樹(shù)的前序遍歷

二叉搜索樹(shù)的刪除（重點(diǎn)）

?完整代碼

?key與value的使用

---

概念

? ? ? ? 對(duì)于一個(gè)二叉搜索樹(shù)

• 若它的左子樹(shù)不為空，則左子樹(shù)上所有的節(jié)點(diǎn)的值都小于等于根節(jié)點(diǎn)的值
• 若它的右子樹(shù)不為空，則右字?jǐn)?shù)上所有的節(jié)點(diǎn)的值都大于等于根節(jié)點(diǎn)的值
• 它的左右子樹(shù)也分別為二叉搜索樹(shù)
• 二叉搜索樹(shù)中可以支持插入相等的值，也可以不支持插入相等的值，具體看使用場(chǎng)景?

template<class K,class V>
struct BSTreeNode
{typedef BSTreeNode<K, V> Node;BSTreeNode(const K& key,const V& val):_key(key),_value(val){}K _key;V _value;Node* _left = nullptr;Node* _right = nullptr;
};

?性能分析

指出二叉搜索樹(shù)：

• 最優(yōu)情況下，二叉搜索樹(shù)近似為完全二叉樹(shù)，高度為
• 最差情況下，二叉搜索樹(shù)退化為類(lèi)似于單支樹(shù)，高度為
• 最優(yōu)情況下增刪查改為
• 最差情況下增刪查改為
• 綜合來(lái)講時(shí)間復(fù)雜度為

指出二分查找：

• 二分查找需要在允許下標(biāo)隨機(jī)訪(fǎng)問(wèn)的結(jié)構(gòu)中
• 二分查找需要在有序的結(jié)構(gòu)中
• 二分查找的時(shí)間復(fù)雜度為
• 二分查找對(duì)應(yīng)的結(jié)構(gòu)一般為數(shù)組，它挪動(dòng)數(shù)據(jù)的時(shí)間復(fù)雜

?二叉搜索樹(shù)的插入

• 樹(shù)為空，直接增新節(jié)點(diǎn)，賦值給root指針
• 樹(shù)不為空，按照性質(zhì)，插入值比當(dāng)前節(jié)點(diǎn)大走右邊，反之走左邊，插入空位置
• 如果支持插入相等的值可以插左邊或者右邊（但是插左邊就都插左邊，反之相同）

?int num[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };

bool Insert(const K& key, const V& value)
{if (_root == nullptr){_root = new Node(key, value);return true;}else{bool right = true;Node* p = _root;Node* c = _root;while (c != nullptr){p = c;if (key > c->_key){right = true;c = p->_right;}else if(key < c->_key){right = false;c = p->_left;}else{return false;}}c = new Node(key, value);if (right){p->_right = c;}else{p->_left = c;}return true;}
}

二叉樹(shù)的查找

• ?從根開(kāi)始查找，key比節(jié)點(diǎn)大就走右，比節(jié)點(diǎn)小就走左邊
• 最多查找高度次數(shù)，走到空還沒(méi)找到就不存在
• 不支持插入相等的值，找到x就返回，反之繼續(xù)查找直到高度次

	Node* Find(const K& key,Node** p = nullptr){	Node* ptr = _root;while (ptr){if (key > ptr->_key){if (p)*p = ptr;ptr = ptr->_right;}else if (key < ptr->_key){if (p)*p = ptr;ptr = ptr->_left;}elsereturn ptr;}return ptr;}

二叉樹(shù)的前序遍歷

• 采用遞歸
• 打印左邊節(jié)點(diǎn)
• 打印中間節(jié)點(diǎn)
• 打印右邊節(jié)點(diǎn)

	void _InOrder(Node* root) {if (root == nullptr) return;_InOrder(root->_left);cout << root->_key << '{' << root->_value << '}' << ' ';_InOrder(root->_right);}

二叉搜索樹(shù)的刪除（重點(diǎn)）

• 先查找是否存在，不存在返回false
• 若存在有以下四種情況
  • 刪除節(jié)點(diǎn)的左右孩子均為空
    • 直接刪除然后給空
  • 刪除節(jié)點(diǎn)的左（右）孩子為空，另一邊不為空
    • 把節(jié)點(diǎn)的父親對(duì)應(yīng)的孩子節(jié)點(diǎn)的指針指向孩子不為空的一邊，然后刪除節(jié)點(diǎn)
  • 刪除節(jié)點(diǎn)左右均不為空
    • 找左子樹(shù)的最大節(jié)點(diǎn)（右子樹(shù)的最小節(jié)點(diǎn)）替代刪除節(jié)點(diǎn)，，然后刪除最值節(jié)點(diǎn)

bool Erase(const K& key)
{Node* par = _root;Node* ptr = Find(key,&par);if (!ptr)return false;if (ptr == par){delete ptr;_root = nullptr;return true;}if(!ptr->_left&&!ptr->_right){if(par->_left == ptr)par->_left = nullptr;if(par->_right == ptr)par->_right = nullptr;delete ptr;return true;}else if (!ptr->_left && ptr->_right)//左空右不空{(diào)if (par->_left == ptr){par->_left = ptr->_right;}if (par->_right == ptr){par->_right = ptr->_right;}delete ptr;return true;}else if(ptr->_left && !ptr->_right){if (par->_left == ptr){par->_left = ptr->_left;}if (par->_right == ptr){par->_right = ptr->_left;}delete ptr;return true;}else//兩邊均不為空直接替換操作{//找左側(cè)最大節(jié)點(diǎn)Node* Max = ptr->_left;Node* Maxp = ptr;while (Max->_right != nullptr){Maxp = Max;Max = Max->_right;}//交換ptr->_key = Max->_key;ptr->_value = Max->_value;//刪除MAX的位置if (Maxp == ptr){ptr->_left = Max->_left;}else if (Max->_left){Maxp->_right = Max->_left;}else{Maxp->_right = Max->_right;}//刪除Maxdelete Max;return true;}return false;
}

?完整代碼

#pragma once
#include<iostream>
#include<string>
using namespace std;template<class K,class V>
struct BSTreeNode
{
public:typedef BSTreeNode<K, V> Node;BSTreeNode(const K& key,const V& val):_key(key),_value(val){}K _key;V _value;Node* _left = nullptr;Node* _right = nullptr;
};template<class K, class V>
class BSTree
{typedef BSTreeNode<K, V> Node;
public:bool Insert(const K& key, const V& value) {if (_root == nullptr) {_root = new Node(key, value);return true;}else {bool right = true;Node* p = _root;Node* c = _root;while (c != nullptr) {p = c;if (key > c->_key) {right = true;c = p->_right;}else if (key < c->_key){right = false;c = p->_left;}else{return false;}}c = new Node(key, value);if (right){p->_right = c;}else{p->_left = c;}return true;}}Node* Find(const K& key,Node** p = nullptr){	Node* ptr = _root;while (ptr){if (key > ptr->_key){if (p)*p = ptr;ptr = ptr->_right;}else if (key < ptr->_key){if (p)*p = ptr;ptr = ptr->_left;}elsereturn ptr;}return ptr;}bool Erase(const K& key){Node* par = _root;Node* ptr = Find(key,&par);if (!ptr)return false;if (ptr == par){delete ptr;_root = nullptr;return true;}if(!ptr->_left&&!ptr->_right){if(par->_left == ptr)par->_left = nullptr;if(par->_right == ptr)par->_right = nullptr;delete ptr;return true;}else if (!ptr->_left && ptr->_right)//左空右不空{(diào)if (par->_left == ptr){par->_left = ptr->_right;}if (par->_right == ptr){par->_right = ptr->_right;}delete ptr;return true;}else if(ptr->_left && !ptr->_right){if (par->_left == ptr){par->_left = ptr->_left;}if (par->_right == ptr){par->_right = ptr->_left;}delete ptr;return true;}else//兩邊均不為空直接替換操作{//找左側(cè)最大節(jié)點(diǎn)Node* Max = ptr->_left;Node* Maxp = ptr;while (Max->_right != nullptr){Maxp = Max;Max = Max->_right;}//交換ptr->_key = Max->_key;ptr->_value = Max->_value;//刪除MAX的位置if (Maxp == ptr){ptr->_left = Max->_left;}else if (Max->_left){Maxp->_right = Max->_left;}else{Maxp->_right = Max->_right;}//刪除Maxdelete Max;return true;}return false;}void InOrder(){_InOrder(_root);}
private:void _InOrder(Node* root) {if (root == nullptr) return;_InOrder(root->_left);cout << root->_key << '{' << root->_value << '}' << ' ';_InOrder(root->_right);}Node* _root = nullptr;
};

?key與value的使用

void TestBSTree()
{BSTree<string, string> dict;dict.Insert("insert", "插入");dict.Insert("erase", "刪除");dict.Insert("left", "左邊");dict.Insert("string", "字符串");string str;while (cin >> str){auto ret = dict.Find(str);if (ret){cout << str << ":" << ret->_value << endl;}else{cout << "單詞拼寫(xiě)錯(cuò)誤" << endl;}}//string strs[] = { "蘋(píng)果", "西瓜", "蘋(píng)果", "櫻桃", "蘋(píng)果", "櫻桃", "蘋(píng)果", "櫻桃", "蘋(píng)果" };統(tǒng)計(jì)水果出現(xiàn)的次//BSTree<string, int> countTree;//for (auto str : strs)//{//	auto ret = countTree.Find(str);//	if (ret == NULL)//	{//		countTree.Insert(str, 1);//	}//	else//	{//		ret->_value++;//	}//}//countTree.InOrder();
}