C++ 二叉搜索树
概念
对于一个二叉搜索树
- 若它的左子树不为空，则左子树上所有的节点的值都小于等于根节点的值
- 若它的右子树不为空，则右字数上所有的节点的值都大于等于根节点的值
- 它的左右子树也分别为二叉搜索树
- 二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景
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;
};性能分析
指出二叉搜索树：
- 最优情况下，二叉搜索树近似为完全二叉树，高度为
- 最差情况下，二叉搜索树退化为类似于单支树，高度为
- 最优情况下增删查改为
- 最差情况下增删查改为
- 综合来讲时间复杂度为
指出二分查找：
- 二分查找需要在允许下标随机访问的结构中
- 二分查找需要在有序的结构中
- 二分查找的时间复杂度为
- 二分查找对应的结构一般为数组，它挪动数据的时间复杂
二叉搜索树的插入
- 树为空，直接增新节点，赋值给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;
}
else
return 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;
}
//删除Max
delete 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;
}
else
return 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;
}
//删除Max
delete 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();
}
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-01-21，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
