C++ 二叉搜索树原理及其实现
2024-08-30 21:42:46
首先是概念：
二叉搜索树又称二叉排序树，它具有以下的性质：
- 若是左子树不为空，则左子树上所有节点的值小于根节点的值
- 若是右子树不为空，则右子树上所有结点的值大于根节点的值
- 二叉搜索树的左右子树也是二叉搜索树
- 二叉搜索树的中序排列是一个有序数列
再下来是它的实现
首先是构造节点
template<class K>
struct BStreeNode{
BStreeNode(const K& date = K()) //节点的定义
:leftC(nullptr), // 初始化
rightC(nullptr),
date_(date)
{}
BStreeNode<K> *leftC; //左孩子
BStreeNode<K> *rightC; //右孩子
K date_;
};
然后是类的实现（具体细节都标在了注释里）：
template<class K>
class BStree{
typedef BStreeNode<K> BsNode;
public:
BStree() :
_root(nullptr)
{}
BsNode* Find(const K& date){ //查找节点
BsNode* pNode = _root;
while (pNode){
if (pNode->date_ == date){
return pNode;
}
else if (pNode->date_ > date){
pNode = pNode->rightC;
}
else
pNode = pNode->leftC;
}
return nullptr;
}
bool Insert(const K& date){
BsNode *pNode = _root;
BsNode *parent=nullptr;
if (_root == nullptr){ //空树时开辟空间定义为根节点
_root = new BsNode(date);
return true;
}
else if (Find(date)){ //存在相同结点不进行插入
return false;
}
else{
while (pNode){ //找到插入位置，但是这里循环结束后只确认了父母结点，是做左孩子还是右孩子不确认( 因为此时值为nullptr )
parent = pNode;
if (pNode->date_ > date){
pNode = pNode->leftC;
}
else{
pNode = pNode->rightC;
}
}
pNode = new BsNode(date); //构造结点
if (parent->date_ > date){ //确认是做左孩子还是右孩子
parent->leftC = pNode;
}
else{
parent->rightC = pNode;
}
return true;
}
} bool Delete(const K& date){
BsNode *pNode = _root;
BsNode *parent = nullptr;
if (pNode == nullptr){ //空树情况
return false;
}
while (pNode){ //找到要删除的结点
if (pNode->date_ == date){
break;
}
else if (pNode->date_ < date){
parent = pNode;
pNode = pNode->rightC;
}
else{
parent = pNode;
pNode = pNode->leftC;
}
}
//BsNode *pdel=pNode;
if (pNode == parent){ //要删除的点是根节点
if (pNode->leftC){
pNode = pNode->leftC;
}
else if (pNode->rightC){
pNode = pNode->rightC;
}
else{
pNode = nullptr;
}
}
if (pNode == nullptr){ // 没有找到要删除的节点
return false;
}
if (pNode->rightC && pNode->leftC == nullptr){ //结点只有右子树
if (pNode == parent->leftC){
parent->leftC = pNode->rightC;
}
else{
parent->rightC = pNode->rightC;
}
}
else if (pNode->leftC && pNode->rightC == nullptr){ //结点只有左子树
if (pNode == parent->leftC){
parent->leftC = pNode->leftC;
}
else{
parent->rightC = pNode->leftC;
}
}
else if (pNode->leftC && pNode->rightC){ //儿女俱全
if (pNode == parent->leftC){ //要删除的节点是父母节点的左孩子，删除后的位置要由原先节点的右孩子替代
pNode->rightC->leftC = pNode->leftC;
parent->leftC = pNode->rightC;
}
else{
pNode->leftC->rightC= pNode->rightC; //要删除的节点是父母节点的右孩子，删除后的位置要由原先节点的左孩子替代
parent->rightC = pNode->leftC;
}
}
else{ //无子可依
if (pNode == parent->leftC){
parent->leftC = nullptr;
}
else{
parent->rightC = nullptr;
}
}
delete pNode; //在连接完成后最后再进行删除
return true;
} BsNode* IfLeftMost(){
if (_root == nullptr){
return nullptr;
}
BsNode *pNode = _root;
while (pNode->leftC){
pNode = pNode->leftC;
}
return pNode;
}
BsNode* IfRightMost(){
if (_root == nullptr){
return nullptr;
}
BsNode *pNode = _root;
while (pNode->rightC){
pNode = pNode->rightC;
}
return pNode;
}
void InOrder(){ //定义一个借口给外部调用，因为根节点在这里是private权限
InOrder(_root);
cout << endl;
} private:
void InOrder(BsNode *pNode){ //二叉树的中序遍历，用来检查结果（二叉搜索树中序遍历应该是一个有序序列）
if (pNode){
InOrder(pNode->leftC);
cout << pNode->date_ << ' ';
InOrder(pNode->rightC);
}
}
private:
BsNode *_root;
};
最新文章
- Android系统的架构
- DotNetBar v12.7.0.2 Fully Cracked
- sql主键的一点重要理解
- Mysql engine
- Win10安卓模拟器Visual Studio Emulator for Android使用简介（转）
- 只获取linux ip的命令
- deflate——过时的网页压缩格式，最好禁用[转]
- CLR基础之一---认识CLR [《CLR via C#》读书笔记]
- win8删除无线网络其中的一项配置
- [Lua]Lua入门教程
- 再探Spring IOC
- （转）为Xcode添加删除行、复制行快捷键
- Linux（CentOs 7）系统重装笔记(一)
- QUARTZ系列之零:概述
- matlab知识
- 即时消息服务框架（iMSF）应用实例之分布式事务三阶段提交协议的实现
- linux下部署git服务器
- python记录_day11 闭包 迭代器
- sqrt函数倒数计算新对比
- grep和sed替换文件中的字符串【转】