C++ 二叉搜索树

概念

性能分析

二叉搜索树的插入

二叉树的查找

二叉树的前序遍历

二叉搜索树的删除（重点）

完整代码

key与value的使用

概念

对于一个二叉搜索树

若它的左子树不为空，则左子树上所有的节点的值都小于等于根节点的值
若它的右子树不为空，则右字数上所有的节点的值都大于等于根节点的值
它的左右子树也分别为二叉搜索树
二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景

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;
};

性能分析

指出二叉搜索树：

最优情况下，二叉搜索树近似为完全二叉树，高度为 $\log_{2} N$
最差情况下，二叉搜索树退化为类似于单支树，高度为 $N$
最优情况下增删查改为 $O\left ( log_{2}N\right )$
最差情况下增删查改为 $O\left ( {N} \right )$
综合来讲时间复杂度为 $O\left ( N \right )$

指出二分查找：

二分查找需要在允许下标随机访问的结构中
二分查找需要在有序的结构中
二分查找的时间复杂度为 $O\left ( log_{2}N \right )$
二分查找对应的结构一般为数组，它挪动数据的时间复杂

二叉搜索树的插入

树为空，直接增新节点，赋值给root指针
树不为空，按照性质，插入值比当前节点大走右边，反之走左边，插入空位置
如果支持插入相等的值可以插左边或者右边（但是插左边就都插左边，反之相同）

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;}
}

二叉树的查找

从根开始查找，key比节点大就走右，比节点小就走左边
最多查找高度次数，走到空还没找到就不存在
不支持插入相等的值，找到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;}

二叉树的前序遍历

采用递归
打印左边节点
打印中间节点
打印右边节点

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

二叉搜索树的删除（重点）

先查找是否存在，不存在返回false
若存在有以下四种情况
删除节点的左右孩子均为空
直接删除然后给空

删除节点的左（右）孩子为空，另一边不为空
把节点的父亲对应的孩子节点的指针指向孩子不为空的一边，然后删除节点

删除节点左右均不为空
找左子树的最大节点（右子树的最小节点）替代删除节点，，然后删除最值节点

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)//左空右不空{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//两边均不为空直接替换操作{//找左侧最大节点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)//左空右不空{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//两边均不为空直接替换操作{//找左侧最大节点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 << "单词拼写错误" << endl;}}//string strs[] = { "苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果" };统计水果出现的次//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();
}