数据结构基础（C++语言实现）—— 二叉搜索树(不支持重复数据)

注意：该笔记的代码有 bug，已经在平衡二叉树的笔记中修正，点击这里跳转笔记；

先说明一下为什么这个代码不支持重复数据，主要是删改查这三个操作没有对重复数据进行操作，所以不支持（主要是懒的实现了）。

这个代码可能和其他博客里面的实现方式有些许不同，主要在以下几个方面：

• 树节点记录了父节点以及该结点是左子还是右子，需要多维护几个属性；
• 左右操作针对结点对象操作，不对结点里面的值操作，比如删除操作，并不是将替换节点直接 replace，而是将整个替换节点的地址覆盖删除节点的地址；
• 应该没了

下面就是代码实现，至于二叉搜索树的概念和前面一样，自己去查，大佬说的比我更好。

类定义

//
// Created by Tianyi on 2021/11/29.
//

#ifndef DATA_STRUCT_NEW_BINARY_TREE_H
#define DATA_STRUCT_NEW_BINARY_TREE_H

#endif //DATA_STRUCT_NEW_BINARY_TREE_H

#include <iostream>

/**
 * 二叉查找树节点
 */
class BinarySearchTreeNode {
private:
    int value;
    // -1 为根节点
    // 0 为左子
    // 1 为右子
    int location;
    BinarySearchTreeNode *parent;
    BinarySearchTreeNode *left;
    BinarySearchTreeNode *right;
public:
    explicit BinarySearchTreeNode(int value, int location, BinarySearchTreeNode *p);

    BinarySearchTreeNode();

    ~BinarySearchTreeNode();

    void setValue(int v);

    [[nodiscard]] int getValue() const;

    void setLocation(int v);

    int getLocation() const;

    void setParent(BinarySearchTreeNode *p);

    BinarySearchTreeNode *getParent();

    void setLeft(BinarySearchTreeNode *l);

    BinarySearchTreeNode *getLeft();

    void setRight(BinarySearchTreeNode *r);

    BinarySearchTreeNode *getRight();
};

/**
 * 二分查找树
 */
class BinarySearchTree {
private:
    BinarySearchTreeNode *root;

    int count;

    void preShow(BinarySearchTreeNode *node);

    void midShow(BinarySearchTreeNode *node);

    void postShow(BinarySearchTreeNode *node);

    void destroyTree(BinarySearchTreeNode *node);

    BinarySearchTreeNode *deleteNode(BinarySearchTreeNode *node);

public:
    BinarySearchTree();

    ~BinarySearchTree();

    BinarySearchTreeNode *getRoot();

    int getCount() const;

    void addNode(int value);

    BinarySearchTreeNode *minimum();

    BinarySearchTreeNode *minimum(BinarySearchTreeNode *node);

    BinarySearchTreeNode *maximum();

    BinarySearchTreeNode *maximum(BinarySearchTreeNode *node);

    BinarySearchTreeNode *findNode(int v);

    int deleteNode(int v);

    void preShow();

    void midShow();

    void postShow();
};

节点方法实现

//
// Created by Tianyi on 2021/11/29.
//
#include "../header/binary_tree_define.h"

using namespace std;

BinarySearchTreeNode::BinarySearchTreeNode() {
    this->value = -65535;
    this->location = -1;
    this->parent = nullptr;
    this->left = nullptr;
    this->right = nullptr;
}

BinarySearchTreeNode::BinarySearchTreeNode(int value, int location, BinarySearchTreeNode *p) {
    this->value = value;
    this->location = location;
    this->parent = p;
    this->left = nullptr;
    this->right = nullptr;
}

BinarySearchTreeNode::~BinarySearchTreeNode() {
    cout << "释放二分搜索树 " << this->value << " 结点内存" << endl;
}

void BinarySearchTreeNode::setValue(const int v) {
    this->value = v;
}

int BinarySearchTreeNode::getValue() const {
    return this->value;
}

void BinarySearchTreeNode::setLocation(int v) {
    this->location = v;
}

int BinarySearchTreeNode::getLocation() const {
    return this->location;
}

void BinarySearchTreeNode::setParent(BinarySearchTreeNode *p) {
    this->parent = p;
}

BinarySearchTreeNode *BinarySearchTreeNode::getParent() {
    return this->parent;
}

void BinarySearchTreeNode::setLeft(BinarySearchTreeNode *l) {
    this->left = l;
}

BinarySearchTreeNode *BinarySearchTreeNode::getLeft() {
    return this->left;
}

void BinarySearchTreeNode::setRight(BinarySearchTreeNode *r) {
    this->right = r;
}

BinarySearchTreeNode *BinarySearchTreeNode::getRight() {
    return this->right;
}

树方法实现

//
// Created by Tianyi on 2021/11/29.
//
#include "../header/binary_tree_define.h"

using namespace std;

BinarySearchTree::BinarySearchTree() {
    this->root = nullptr;
    this->count = 0;
}

/**
 * 释放树的所有内存
 * （需要后序遍历所有节点进行释放内存，后面再完成）
 */
BinarySearchTree::~BinarySearchTree() {
    // 后序遍历释放内存
    destroyTree(this->root);
}

void BinarySearchTree::destroyTree(BinarySearchTreeNode *node) {
    if (node == nullptr) {
        return;
    }

    destroyTree(node->getLeft());
    destroyTree(node->getRight());
    delete (node);
}

BinarySearchTreeNode *BinarySearchTree::getRoot() {
    return this->root;
}

int BinarySearchTree::getCount() const {
    return this->count;
}

/**
 * 添加节点
 * @param value 节点值
 */
void BinarySearchTree::addNode(int value) {
    // 如果树为空直接作为根节点添加
    if (this->count == 0 && this->root == nullptr) {
        this->root = new BinarySearchTreeNode(value, -1, nullptr);
        this->count++;
        return;
    }

    auto *node = this->root;

    while (node != nullptr) {
        if (value > node->getValue()) {
            if (node->getRight() == nullptr) {
                node->setRight(new BinarySearchTreeNode(value, 1, node));
                this->count++;
                return;
            } else {
                node = node->getRight();
            }
        } else {
            if (node->getLeft() == nullptr) {
                node->setLeft(new BinarySearchTreeNode(value, 0, node));
                this->count++;
                return;
            } else {
                node = node->getLeft();
            }
        }
    }
}

/**
 * 查找某个节点是否存在：
 * - 存在则返回该结点
 * - 不存在返回空指针
 * @param v
 * @return
 */
[[maybe_unused]] BinarySearchTreeNode *BinarySearchTree::findNode(int v) {

    auto *node = this->root;

    while (node != nullptr) {
        if (v > node->getValue()) {
            node = node->getRight();
        } else if (v < node->getValue()) {
            node = node->getLeft();
        } else {
            return node;
        }
    }

    return nullptr;
}

/**
 * 删除二叉搜索树的节点
 * @param node
 * @return
 */
BinarySearchTreeNode *BinarySearchTree::deleteNode(BinarySearchTreeNode *node) {

    cout << "处理 " << node->getValue() << " 节点" << endl;

    // 判断删除的节点是否是叶子节点
    //      1 如果是叶子节点，直接 delete 释放内存
    //      2 如果不是叶子节点，要判断是否存在左右子树
    //          2.1 如果有右子树，则判断右子树是否存在左子树
    //              2.1.1 如果存在则从左子树中找到 左子树 最大值 替换当前节点
    //              2.1.2 如果不存在，将这个右子树的根替换到当前节点
    //          2.2 如果没有右子树，则将左子树的第一个节点替代当前节点即可
    if (node->getRight() == nullptr && node->getLeft() == nullptr) {
        // 修改父节点指向该结点的指针
        if (node->getLocation() == 0) {
            node->getParent()->setLeft(nullptr);
        } else if(node->getLocation() == 1) {
            node->getParent()->setRight(nullptr);
        }

        return node;
    }

    BinarySearchTreeNode *replaceNode = nullptr;

    // 当前删除节点 的父节点
    auto *parentNode = node->getParent();

    if (node->getRight() != nullptr) {
        // 需要替换的节点
        replaceNode = this->minimum(node->getRight());
        cout << "替换当前 " << node->getValue() << " 节点的是 " << replaceNode->getValue() << " 节点" << endl;
        // 递归删除
        deleteNode(replaceNode);

        replaceNode->setParent(parentNode);
        replaceNode->setLocation(node->getLocation());
        replaceNode->setLeft(node->getLeft());
        replaceNode->setRight(node->getRight());
    } else {
        // 这种情况只针对只有左子树的情况
        // 需要替换的节点
        replaceNode = node->getLeft();

        replaceNode->setParent(parentNode);
        replaceNode->setLocation(node->getLocation());
    }

    // 删除节点是父节点的左子还是右子，或者是根节点
    // 根节点不作处理
    int location = node->getLocation();
    if (location == 0) {
        parentNode->setLeft(replaceNode);
    } else if (location == 1) {
        parentNode->setRight(replaceNode);
    } else {
        this->root = replaceNode;
    }

    return node;
}

/**
 * 删除节点需要找到该节点的子树中处于中间的那个节点：
 * @param v
 * @return
 */
int BinarySearchTree::deleteNode(int v) {

    // 1. 先查询需要删除的节点是否存在
    auto *findNode = this->findNode(v);
    if (findNode == nullptr) {
        cout << "需要删除的节点不存在" << endl;
        return -1;
    }

    // 释放内存
    auto *deleteNode = this->deleteNode(findNode);
    delete (deleteNode);
    this->count--;

    return v;
}

/**
 * 前序遍历
 */
void BinarySearchTree::preShow() {
    cout << "前序遍历" << endl;
    preShow(this->root);
    cout << endl;
    cout << "================" << endl;
}

void BinarySearchTree::preShow(BinarySearchTreeNode *node) {
    if (node == nullptr) {
        return;
    }

    cout << node->getValue() << " - ";
    preShow(node->getLeft());
    preShow(node->getRight());
}

/**
 * 中序遍历
 */
void BinarySearchTree::midShow() {
    cout << "中序遍历" << endl;
    midShow(this->root);
    cout << endl;
    cout << "================" << endl;
}

void BinarySearchTree::midShow(BinarySearchTreeNode *node) {
    if (node == nullptr) {
        return;
    }

    midShow(node->getLeft());
    cout << node->getValue() << " - ";
    midShow(node->getRight());
}

/**
 * 后序遍历
 */
void BinarySearchTree::postShow() {
    cout << "后序遍历" << endl;
    postShow(this->root);
    cout << endl;
    cout << "================" << endl;
}

void BinarySearchTree::postShow(BinarySearchTreeNode *node) {
    if (node == nullptr) {
        return;
    }

    postShow(node->getLeft());
    postShow(node->getRight());
    cout << node->getValue() << " - ";
}

/**
 * 获取整棵树的最小值
 * @return
 */
BinarySearchTreeNode *BinarySearchTree::minimum() {
    return this->minimum(this->root);
}

/**
 * 获取指定节点下的最小值
 * @param node
 * @return
 */
BinarySearchTreeNode *BinarySearchTree::minimum(BinarySearchTreeNode *node) {
    if (node == nullptr) {
        cout << "该结点不存在" << endl;
        return nullptr;
    }

    // 如果当前节点没有左子树，则当前节点就是最小值节点
    if (node->getLeft() == nullptr) {
        return node;
    }

    // 最左叶节点就是最小值
    auto *tempNode = node;
    while (tempNode->getLeft() != nullptr) {
        tempNode = tempNode->getLeft();
    }

    return tempNode;
}

/**
 * 获取整棵树的最大值
 * @return
 */
BinarySearchTreeNode *BinarySearchTree::maximum() {
    return this->maximum(this->root);
}

/**
 * 获取指定节点下的最大值
 * @param node
 * @return
 */
BinarySearchTreeNode *BinarySearchTree::maximum(BinarySearchTreeNode *node) {
    if (node == nullptr) {
        cout << "该结点不存在" << endl;
        return nullptr;
    }

    // 如果当前节点没有右子树，则当前节点就是最大值节点
    if (node->getRight() != nullptr) {
        return node;
    }

    // 最左叶节点就是最小值
    auto *tempNode = node;
    while (tempNode->getRight() == nullptr) {
        tempNode = tempNode->getRight();
    }

    return tempNode;
}

测试代码

#include "header/binary_tree_define.h"

using namespace std;

int main() {
    auto *tree = new BinarySearchTree();
    tree->addNode(9);
    tree->addNode(4);
    tree->addNode(2);
    tree->addNode(5);
    tree->addNode(1);
    tree->addNode(3);
    tree->addNode(7);
    tree->addNode(6);
    tree->addNode(8);
    tree->addNode(15);
    tree->addNode(10);
    tree->addNode(13);
    tree->addNode(14);
    tree->addNode(11);
    tree->addNode(12);
    tree->addNode(16);

    tree->midShow();

//    auto *node = tree->findNode(9);
//    auto * miniNode = tree->minimum(node);
//    cout << "最小值是 " << miniNode->getValue() << endl;
//    cout << node->getValue() << " - " << node->getLeft()->getValue() << " - " << node->getRight()->getValue() << endl;


    tree->deleteNode(5);

    tree->midShow();

    delete (tree);

    return 0;
}

可能会用到的 CMake 文件

cmake_minimum_required(VERSION 3.20)
project(data_struct_new)

set(CMAKE_CXX_STANDARD 14)

# Add header file header directories
include_directories(header)

add_executable(data_struct_new main.cpp src/binary_tree_node.cpp src/binary_tree.cpp)