基于面向对象的，C++实现二叉搜索树的一系列操作
发布时间：2024年01月18日
1.树
树是由节点和边组成的一种可以表示数据的层次结构
根节点：树的最顶端的节点
叶节点：树的最底层的节点
子节点：通过边相连的位于下层的为子节点
父节点：通过边相连的位于上层的为父节点
层次：一个节点到根节点的距离称为层次
度：一个节点拥有子树的数量，如果一个树中所有节点的度都不大于n，那么这个树就是n叉树
2.二叉树
树中的每个节点最多只有两个节点称为二叉树
性质1：二叉树的每一层最多有2^i个节点
性质2：高度为k的二叉树的最大节点数为2^(k+1)-1，
性质3：二叉树的度为0的节点数m和度为2的节点数n满足：m=n+1
二叉树一般有三种：完美二叉树，完全二叉树，满二叉树
1.完美二叉树：二叉树的每一层都是满的，即深度为k的其节点数为2^(k+1)-1
2.完全二叉树：二叉树的节点从左到右没有空隙
3.满二叉树：每个非叶子节点的度均为2
3.二叉搜索树（BST）
左子树的所有节点的值都小于根节点的值，右子树的所有节点的值都大于根节点的值，所有而插不上中的值唯一，且可以通过深度优先搜索算法中的中序遍历方法即可按照值的升序来遍历二叉搜索树
3.1 BST的相关代码
3.1.1 TreeNode.h
#pragma once
class TreeNode
{
public:
int value;
TreeNode* left;
TreeNode* right;
TreeNode(int val);
~TreeNode();
};
3.1.2 TreeNode.cpp
#include "TreeNode.h"
TreeNode::TreeNode(int val)
{
this->value = val;
left = nullptr;
right = nullptr;
}
TreeNode::~TreeNode()
{
}
3.1.3 BST的相关代码
#pragma once
#include"TreeNode.h"
class BinarySearchTree
{
public:
TreeNode* root;
BinarySearchTree();
~BinarySearchTree();
bool insert(int val);//插入
bool search(int val);//查找
bool remove(int val);//删除
void BFS();//Breadth First Search
//Depth First Search:PreOrder,PostOrder,InOrder
//PreOrder: 中左右
void DFS_PreOrder(TreeNode* temp);
void DFS_PreOrder();
//InOrder：左中右
void DFS_InOrder(TreeNode* temp);
void DFS_InOrder();
//PostOrder:左右中
void DFS_PostOrder(TreeNode* temp);
void DFS_PostOrder();
};
3.1.4 BST的相关代码
#include "BinarySearchTree.h"
#include <queue>
#include <iostream>
BinarySearchTree::BinarySearchTree()
{
root = nullptr;
}
BinarySearchTree::~BinarySearchTree()
{
}
bool BinarySearchTree::insert(int val)
{
TreeNode* newNode = new TreeNode(val);
if (root == nullptr) {
root = newNode;
return true;
}
TreeNode* temp = root;
while (true) {
if (newNode->value == temp->value) {
return false;
}
if (newNode->value < temp->value) {
if (temp->left == nullptr) {
temp->left = newNode;
return true;
}
temp = temp->left;
}
else {
if (temp->right == nullptr) {
temp->right = newNode;
return true;
}
temp = temp->right;
}
}
}
bool BinarySearchTree::search(int val)
{
if (root == nullptr) {
return false;
}
TreeNode* temp = root;
while (temp) {
if (val < temp->value) {
temp = temp->left;
}
else if (val > temp->value) {
temp = temp->right;
}
else {
return true;
}
}
return false;
}
bool BinarySearchTree::remove(int val)
{
TreeNode* temp = root;
TreeNode* parent = nullptr;
while (temp) {
if (val < temp->value) {
parent = temp;
temp = temp->left;
}
else if(val > temp->value){
parent = temp;
temp = temp->right;
}
else {
if (temp->left == nullptr) {//左孩子为空
if (temp == root) {
root = temp->right;
}
else if (temp == parent->left) {
parent->left = temp->right;
}
else {
parent->right = temp->right;
}
}
else if (temp->right == nullptr) {//右孩子为空
if (temp == root) {
root = temp->left;
}
else if (temp = temp->left) {
parent->left = temp->left;
}
else {
parent->right = temp->left;
}
}
else {//左右孩子都不为空：找左子树中的最大值或者右子树中的最小值
TreeNode* maxleft = temp->left;
parent = temp;
while (maxleft->right) {//找左子树中的最大值
parent = maxleft;
maxleft = maxleft->right;
}
temp->value = maxleft->value;//交换
if (parent->left == maxleft) {//此时删除的节点没有子节
parent->left = maxleft->left;
}
else {//此时删除的节点只有一个子节点
parent->right = maxleft->left;
}
}
return true;
}
}
return false;
}
void BinarySearchTree::BFS()
{
std::queue<TreeNode*> myQueue;
myQueue.push(root);
while (myQueue.size() > 0) {
TreeNode* temp = myQueue.front();
myQueue.pop();
std::cout << temp->value << " ";
if (temp->left != nullptr) {
myQueue.push(temp->left);
}
if (temp->right != nullptr) {
myQueue.push(temp->right);
}
}
}
void BinarySearchTree::DFS_PreOrder(TreeNode* temp)
{
std::cout << temp->value << " ";
if (temp->left != nullptr) {
DFS_PreOrder(temp->left);
}
if (temp->right != nullptr) {
DFS_PreOrder(temp->right);
}
}
void BinarySearchTree::DFS_PreOrder()
{
DFS_PreOrder(root);
}
void BinarySearchTree::DFS_InOrder(TreeNode* temp)
{
if (temp->left != nullptr) {
DFS_InOrder(temp->left);
}
std::cout << temp->value << " ";
if (temp->right != nullptr) {
DFS_InOrder(temp->right);
}
}
void BinarySearchTree::DFS_InOrder()
{
DFS_InOrder(root);
}
void BinarySearchTree::DFS_PostOrder(TreeNode* temp)
{
if (temp->left != nullptr) {
DFS_PostOrder(temp->left);
}
if (temp->right != nullptr) {
DFS_PostOrder(temp->right);
}
std::cout << temp->value << " ";
}
void BinarySearchTree::DFS_PostOrder()
{
DFS_PostOrder(root);
}
3.2 BST的先序
先序遍历：根节点->左子树->右子树
void BinarySearchTree::DFS_PreOrder(TreeNode* temp)
{
std::cout << temp->value << " ";
if (temp->left != nullptr) {
DFS_PreOrder(temp->left);
}
if (temp->right != nullptr) {
DFS_PreOrder(temp->right);
}
}
void BinarySearchTree::DFS_PreOrder()
{
DFS_PreOrder(root);
}
3.3 BST的中序
中序遍历：左子树->根节点->右子树
//中序：左中右
void BinarySearchTree::DFS_InOrder(TreeNode* temp)
{
if (temp->left != nullptr) {
DFS_InOrder(temp->left);
}
std::cout << temp->value << " ";
if (temp->right != nullptr) {
DFS_InOrder(temp->right);
}
}
void BinarySearchTree::DFS_InOrder()
{
DFS_InOrder(root);
}
3.4 BST的后序
后序遍历：左子树->右子树->根节点
void BinarySearchTree::DFS_PostOrder(TreeNode* temp)
{
if (temp->left != nullptr) {
DFS_PostOrder(temp->left);
}
if (temp->right != nullptr) {
DFS_PostOrder(temp->right);
}
std::cout << temp->value << " ";
}
void BinarySearchTree::DFS_PostOrder()
{
DFS_PostOrder(root);
}
3.5 BST的层序遍历
层序遍历：从上到下，从左到右
void BinarySearchTree::BFS()
{
std::queue<TreeNode*> myQueue;
myQueue.push(root);
while (myQueue.size() > 0) {
TreeNode* temp = myQueue.front();
myQueue.pop();
std::cout << temp->value << " ";
if (temp->left != nullptr) {
myQueue.push(temp->left);
}
if (temp->right != nullptr) {
myQueue.push(temp->right);
}
}
}
3.5 BST的插入
1.创造新节点
2.判断新节点与root节点的大小
3.在判断root相应的子节点是否为空：
为空就直接插入，不为空就反复循环上述2,3步骤
bool BinarySearchTree::insert(int val)
{
TreeNode* newNode = new TreeNode(val);
if (root == nullptr) {
root = newNode;
return true;
}
TreeNode* temp = root;
while (true) {
if (newNode->value == temp->value) {
return false;
}
if (newNode->value < temp->value) {
if (temp->left == nullptr) {
temp->left = newNode;
return true;
}
temp = temp->left;
}
else {
if (temp->right == nullptr) {
temp->right = newNode;
return true;
}
temp = temp->right;
}
}
}
3.6 BST的删除
1.删除的节点没有子节点：
（1）如果删除节点是左子节点，将其父节点的指针设为nullptr
（2）如果删除节点是右子节点，将其父节点的指针设为nullptr
2.删除的节点有一个子节点：
（1）如果删除节点是左子节点，将其父节点的左指针指向删除节点的子节点
（2）如果删除节点是右子节点，将其父节点的右指针指向删除节点的子节点
3.删除的节点有两个子节点：
（1）从删除节点的左子树中查找value最大的节点（或者右子树中的最小值）
（2）将找到的节点移动到删除位置
（3）交换待删除的节点和左子树的最大值（或者右子树中的最小值）
（4）删除已经移动的节点
bool BinarySearchTree::remove(int val)
{
TreeNode* temp = root;
TreeNode* parent = nullptr;
while (temp) {
if (val < temp->value) {
parent = temp;
temp = temp->left;
}
else if(val > temp->value){
parent = temp;
temp = temp->right;
}
else {
if (temp->left == nullptr) {//左孩子为空
if (temp == root) {
root = temp->right;
}
else if (temp == parent->left) {
parent->left = temp->right;
}
else {
parent->right = temp->right;
}
}
else if (temp->right == nullptr) {//右孩子为空
if (temp == root) {
root = temp->left;
}
else if (temp = temp->left) {
parent->left = temp->left;
}
else {
parent->right = temp->left;
}
}
else {//左右孩子都不为空：找左子树中的最大值或者右子树中的最小值
TreeNode* maxleft = temp->left;
parent = temp;
while (maxleft->right) {//找左子树中的最大值
parent = maxleft;
maxleft = maxleft->right;
}
temp->value = maxleft->value;//交换
if (parent->left == maxleft) {//此时删除的节点没有子节
parent->left = maxleft->left;
}
else {//此时删除的节点只有一个子节点
parent->right = maxleft->left;
}
}
return true;
}
}
return false;
}
3.7 BST的查找
根据二叉搜索树的定义进行查找：比节点大的往右边走，比节点小的往左边走
bool BinarySearchTree::search(int val)
{
if (root == nullptr) {
return false;
}
TreeNode* temp = root;
while (temp) {
if (val < temp->value) {
temp = temp->left;
}
else if (val > temp->value) {
temp = temp->right;
}
else {
return true;
}
}
return false;
}
4.测试
#include<iostream>
#include"BinarySearchTree.h"
using namespace std;
void test03() {
BinarySearchTree* mybst3 = new BinarySearchTree();
mybst3->insert(4);
mybst3->insert(2);
mybst3->insert(6);
mybst3->insert(1);
mybst3->insert(3);
mybst3->insert(5);
mybst3->insert(7);
cout << "先序：";
mybst3->DFS_PreOrder();
cout << endl;
cout << "中序：";
mybst3->DFS_InOrder();
cout << endl;
cout << "后序：";
mybst3->DFS_PostOrder();
cout << endl;
cout << "层序：";
mybst3->BFS();
}
void test05() {
BinarySearchTree* mybst5 = new BinarySearchTree();
mybst5->insert(4);
mybst5->insert(2);
mybst5->insert(6);
mybst5->insert(1);
mybst5->insert(3);
mybst5->insert(5);
mybst5->insert(7);
cout << "删除前：";
mybst5->DFS_InOrder();
cout << endl;
mybst5->remove(6);
cout << "删除后：";
mybst5->DFS_InOrder();
}
int main() {
test03();
cout << endl;
cout << "---------------------------------" << endl;
test05();
}
文章来源:https://blog.csdn.net/qq_44961737/article/details/135678363
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！
最新文章
- Python教程
- 深入理解 MySQL 中的 HAVING 关键字和聚合函数
- Qt之QChar编码（1）
- MyBatis入门基础篇
- 用Python脚本实现FFmpeg批量转换
- c++中this的操作和链式操作
- 2.【CPP】入门（宏||内联函数||拷贝构造||析构函数||构造函数）
- ERA ·Era Network:Web3.0社交的破局者
- 互质数（函数）
- Linux学习之系统编程2（关于进程及其相关的函数）
- Linux下修改文件名的三种方法
- 人力资源方面的证书有哪些？HR必看！
- 无限创意与自由协作：现可在 Splashtop 上使用 Wacom Bridge 的通用版本
- C++初阶------------------入门C++
- Python之可迭代对象、迭代器、生成器