数据结构基础（C++语言实现）——-平衡二叉搜索树

声明：

1. 该代码基于之前的二叉搜索树代码修改来的，可以点击这里查看相关笔记；

2. 上一条提到的笔记里面的代码有 bug，可以选择不用看了，bug 如下：

   1. 节点使用 location 字段记录是左子还是右子，其实没有必要，整个代码里面使用到的地方并不多；
   2. 在删除节点时没有对父子关系进行维护，会存在隐藏问题，比如死循环；

3. 对于新代码主要修改有以下：

   • 修改:

     1. 删除 location 字段以及相关操作；
     2. 将 add 函数和 delete 函数修改为递归函数；
     3. 对可能出现空指针异常的地方添加判断（这个是这次改动中出现的最多的问题）

   • 添加:

     1. 添加节点左旋转与右旋转操作，用于实现平衡二叉树；
     2. 添加判断是否平衡和是否为搜索树的函数；

再唠一句

这次编写平衡二叉树再次让我体会到了 C++ 空指针有多么恶心，这玩意完全不按照套路来，或者说我也没有摸清楚 C++ 操作指针的套路，可能是因为 Java 和 Python 写多了，对于指针的理解没有那么深刻，算是得到了一个教训吧，只能说慢慢练，还不知道后面写图的代码会遇到多恶心的东西，我这里甚至还没用上模板，要是用上了，估计会更恶心。（恶心！恶心呐！恶心！tui~真恶心）

啰嗦一下左右旋转

这里面涉及到的左旋转和右旋转操作并不复杂，这里大致画一下就是这 4 种情况：

/**
 * 右旋转
 *        y                              x
 *       / \                           /   \
 *      x   T4     向右旋转 (y)        z     y
 *     / \       - - - - - - - ->    / \   / \
 *    z   T3                       T1  T2 T3 T4
 *   / \
 * T1   T2
 */
 
================================================
 
/**
 * 左旋转
 *    y                             x
 *  /  \                          /   \
 * T1   x      向左旋转 (y)       y     z
 *     / \   - - - - - - - ->   / \   / \
 *   T2   z                    T1 T2 T3 T4
 *       / \
 *      T3 T4
 */
 
================================================
 
/**
 * 先右旋转再左旋转                              
 *    y                            y                                z
 *  /  \                          /  \                            /   \
 * T    x      向右旋转 (y)       T     z      向左旋转 (y)        y      x
 *     / \   - - - - - - - ->         / \   - - - - - - - ->   / \     / \
 *    z  T                           T   x                    T  T    T   T 
 *   / \                                / \   
 *  T   T                              T   T
 */

================================================
 
/**
 * 先左旋转再右旋转                              
 *        y                                 y                              z
 *      /  \                              /  \                           /   \
 *     x    T      向左旋转 (y)           z    z       向右旋转 (y)       y      x
 *   /  \       - - - - - - - ->       / \         - - - - - - - ->   / \    /  \
 *  T    z                            x   T                          T  T   T    T 
 *      / \                          / \   
 *     T   T                        T   T
 */

类定义

//
// 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;
    int height;
    BinarySearchTreeNode *parent;
    BinarySearchTreeNode *left;
    BinarySearchTreeNode *right;
public:
    explicit BinarySearchTreeNode(int value, BinarySearchTreeNode *p);

    BinarySearchTreeNode();

    ~BinarySearchTreeNode();

    void setValue(int v);

    int getValue() const;

    void setHeight(int h);

    int getHeight() const;

    void setParent(BinarySearchTreeNode *p);

    BinarySearchTreeNode *getParent();

    void setLeft(BinarySearchTreeNode *l);

    BinarySearchTreeNode *getLeft();

    void setRight(BinarySearchTreeNode *r);

    BinarySearchTreeNode *getRight();

    BinarySearchTreeNode(BinarySearchTreeNode *pNode);
};

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

    int count;

    void preShow(BinarySearchTreeNode *node);

    void midShow(BinarySearchTreeNode *node);

    void postShow(BinarySearchTreeNode *node);

    void showTree(BinarySearchTreeNode *arr, int num);

    void destroyTree(BinarySearchTreeNode *node);

    BinarySearchTreeNode *deleteNode(BinarySearchTreeNode *node, int value);

    BinarySearchTreeNode *addNode(BinarySearchTreeNode *node, BinarySearchTreeNode *parentNode, int value);

    static int getNodeHeight(BinarySearchTreeNode *node);

    int getBalanceFactor(BinarySearchTreeNode *node);

    bool isBST(BinarySearchTreeNode *node);

    bool isBalanced(BinarySearchTreeNode *node);

    BinarySearchTreeNode *turnRight(BinarySearchTreeNode *node);

    BinarySearchTreeNode *turnLeft(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);

    bool isBST();

    bool isBalanced();

    int deleteNode(int v);

    void preShow();

    void midShow();

    void postShow();

    void showTree();
};

节点类实现

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

using namespace std;

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

BinarySearchTreeNode::BinarySearchTreeNode(int value, BinarySearchTreeNode *p) {
    this->value = value;
    this->height = 1;
    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::setHeight(int h) {
    this->height = h;
}

int BinarySearchTreeNode::getHeight() const {
    return this->height;
}

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

BinarySearchTreeNode::BinarySearchTreeNode(BinarySearchTreeNode *pNode) {
    this->value = pNode->value;
    this->height = pNode->height;
    this->parent = pNode->parent;
    this->left = pNode->left;
    this->right = pNode->right;
}

树代码实现

//
// Created by Tianyi on 2021/11/29.
//
#include <cmath>
#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 node
 * @return
 */
int BinarySearchTree::getNodeHeight(BinarySearchTreeNode *node) {
    if (node == nullptr) {
        return 0;
    }
    return node->getHeight();
}

/**
 * 获得该节点的平衡因子
 * @param node
 * @return
 */
int BinarySearchTree::getBalanceFactor(BinarySearchTreeNode *node) {
    if (node == nullptr) {
        return 0;
    }
    return this->getNodeHeight(node->getLeft()) - this->getNodeHeight(node->getRight());
}

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

    this->root = this->addNode(this->root, nullptr, value);
    this->count++;
}

/**
 * 递归添加节点
 * 递归添加节点的好处就是省去了大部分循环代码，只用专注逻辑即可
 * @param node
 * @param parentNode
 * @param value
 * @param location
 * @return
 */
BinarySearchTreeNode *BinarySearchTree::addNode(BinarySearchTreeNode *node,
                                                BinarySearchTreeNode *parentNode,
                                                int value) {
    if (node == nullptr) {
        return new BinarySearchTreeNode(value, parentNode);
    }

    if (value < node->getValue()) {
        node->setLeft(addNode(node->getLeft(), node, value));
    } else if (value > node->getValue()) {
        node->setRight(addNode(node->getRight(), node, value));
    }

    // 更新 height
    node->setHeight(1 + max(this->getNodeHeight(node->getLeft()), this->getNodeHeight(node->getRight())));

    // 计算平衡因子
    int balanceFactor = this->getBalanceFactor(node);

    // 平衡维护
    // 右旋转
    if (balanceFactor > 1 && getBalanceFactor(node->getLeft()) >= 0) {
        node = this->turnRight(node);
    }

    // 左旋转
    if (balanceFactor < -1 && getBalanceFactor(node->getRight()) <= 0) {
        node = this->turnLeft(node);
    }

    // 先左旋转再右旋转
    if (balanceFactor > 1 && getBalanceFactor(node->getLeft()) < 0) {
        node->setLeft(this->turnLeft(node->getLeft()));
        node = this->turnRight(node);
    }

    // 先右旋转再左旋转
    if (balanceFactor < -1 && getBalanceFactor(node->getRight()) > 0) {
        node->setRight(this->turnRight(node->getRight()));
        node = this->turnLeft(node);
    }

    return node;
}

/**
 * 查找某个节点是否存在：
 * - 存在则返回该结点
 * - 不存在返回空指针
 * @param v
 * @return
 */
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;
}

/**
 * 判断是否为平衡二叉树
 * @return
 */
bool BinarySearchTree::isBST() {
    return this->isBST(this->root);
}

/**
 * 实际调用的检查方法
 * @param node
 * @return
 */
bool BinarySearchTree::isBST(BinarySearchTreeNode *node) {
    // 判断当前节点是否为空
    if (node == nullptr) {
        return true;
    }

    // 判断当前节点是否是叶子节点
    if (node->getLeft() == nullptr && node->getRight() == nullptr) {
        return true;
    }

    bool leftFlag = this->isBST(node->getLeft());
    // 如果当前节点没有右子树，则只比较左子树大小
    if (node->getRight() == nullptr) {
        return leftFlag & (node->getLeft()->getValue() < node->getValue());
    }
    bool rightFlag = this->isBST(node->getRight());

    return leftFlag & rightFlag;
}

/**
 * 判断此二分搜索树是否平衡
 * @return
 */
bool BinarySearchTree::isBalanced() {
    return this->isBalanced(this->root);
}

/**
 * 实际用于判断平衡的函数
 * @param node
 * @return
 */
bool BinarySearchTree::isBalanced(BinarySearchTreeNode *node) {
    if (node == nullptr) {
        return true;
    }

    int balanceFactor = this->getBalanceFactor(node);
    if (abs(balanceFactor) > 1) {
        return false;
    }
    return isBalanced(node->getLeft()) && isBalanced(node->getRight());
}

/**
 * 右旋转
 *        y                              x
 *       / \                           /   \
 *      x   T4     向右旋转 (y)        z     y
 *     / \       - - - - - - - ->    / \   / \
 *    z   T3                       T1  T2 T3 T4
 *   / \
 * T1   T2
 * @param node
 */
BinarySearchTreeNode *BinarySearchTree::turnRight(BinarySearchTreeNode *node) {

    auto *y = node;
    auto *x = node->getLeft();

    if (x->getRight() != nullptr) {
        x->getRight()->setParent(y);
        y->setLeft(x->getRight());
    } else {
        y->setLeft(nullptr);
    }
    x->setRight(y);

    // 更新父节点
    x->setParent(y->getParent());
    y->setParent(x);

    // 更新节点高度
    y->setHeight(max(getNodeHeight(y->getLeft()), getNodeHeight(y->getRight())) + 1);
    x->setHeight(max(getNodeHeight(x->getLeft()), getNodeHeight(x->getRight())) + 1);

    return x;
}

/**
 * 左旋转
 *    y                             x
 *  /  \                          /   \
 * T1   x      向左旋转 (y)       y     z
 *     / \   - - - - - - - ->   / \   / \
 *   T2  z                     T1 T2 T3 T4
 *      / \
 *     T3 T4
 * @param node
 */
BinarySearchTreeNode *BinarySearchTree::turnLeft(BinarySearchTreeNode *node) {

    auto *y = node;
    auto *x = node->getRight();

    if (x->getLeft() != nullptr) {
        x->getLeft()->setParent(y);
        y->setRight(x->getLeft());
    } else {
        y->setRight(nullptr);
    }
    x->setLeft(y);
;
    x->setParent(y->getParent());
    y->setParent(x);

    // 更新节点高度
    y->setHeight(max(getNodeHeight(y->getLeft()), getNodeHeight(y->getRight())) + 1);
    x->setHeight(max(getNodeHeight(x->getLeft()), getNodeHeight(x->getRight())) + 1);

    return x;
}

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

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

    auto * retNode =this->deleteNode(this->root, v);
    // 检查是否删除成功断言
    assert(retNode != nullptr);
    if (retNode != nullptr) {
        this->root = retNode;
        delete(findNode);
    }

    return v;
}

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

    // TODO 使用递归重写删除函数

    BinarySearchTreeNode *retNode;

    if (value < node->getValue()) {
        auto * newNode = this->deleteNode(node->getLeft(), value);
        // 维护父子节点关系
        node->setLeft(newNode);
        if (newNode != nullptr) {
            newNode->setParent(node);
        }
        retNode = node;
    } else if (value > node->getValue()) {
        auto * newNode = this->deleteNode(node->getRight(), value);
        // 维护父子节点关系
        node->setRight(newNode);
        if (newNode != nullptr) {
            newNode->setParent(node);
        }
        retNode = node;
    } else {
        // 待删除节点左子树为空
        if (node->getLeft() == nullptr) {
            auto * rightNode = node->getRight();
            node->setRight(nullptr);
            this->count --;
            return rightNode;
        }

        // 待删除节点右子树为空
        if (node->getRight() == nullptr) {
            auto * leftNode = node->getLeft();
            node->setLeft(nullptr);
            this->count--;
            return leftNode;
        }

        // 待删除节点左右子树都不为空
        else {
            auto * successor = this->minimum(node->getRight());
            auto * sucRightChild = this->deleteNode(node->getRight(), successor->getValue());
            // 维护右子树父子关系
            successor->setRight(sucRightChild);
            if (sucRightChild != nullptr) {
                sucRightChild->setParent(successor);
            }
            // 维护左子树父子关系
            successor->setLeft(node->getLeft());
            successor->getLeft()->setParent(successor);

            node->setLeft(nullptr);
            node->setRight(nullptr);
            this->count--;

            retNode = successor;
        }
    }

    // 更新 height
    retNode->setHeight(1 + max(this->getNodeHeight(retNode->getLeft()), this->getNodeHeight(retNode->getRight())));

    // 计算平衡因子
    int balanceFactor = this->getBalanceFactor(retNode);

    // 平衡维护
    // 右旋转
    if (balanceFactor > 1 && getBalanceFactor(retNode->getLeft()) >= 0) {
        retNode = this->turnRight(retNode);
    }

    // 左旋转
    if (balanceFactor < -1 && getBalanceFactor(retNode->getRight()) <= 0) {
        retNode = this->turnLeft(retNode);
    }

    // 先左旋转再右旋转
    if (balanceFactor > 1 && getBalanceFactor(retNode->getLeft()) < 0) {
        retNode->setLeft(this->turnLeft(retNode->getLeft()));
        retNode = this->turnRight(retNode);
    }

    // 先右旋转再左旋转
    if (balanceFactor < -1 && getBalanceFactor(retNode->getRight()) > 0) {
        retNode->setRight(this->turnRight(retNode->getRight()));
        retNode = this->turnLeft(retNode);
    }

    return retNode;
}

/**
 * 前序遍历
 */
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() << " - ";
}

/**
 * 按照树结构打印
 */
void BinarySearchTree::showTree() {
    this->showTree(this->root, 1);
}

void BinarySearchTree::showTree(BinarySearchTreeNode *arr, int num) {
    if (num == 0) {
        return;
    }

    int len = 0;

    for (int i = 0; i < num; i++) {
        for (int j = 0; j < arr[i].getHeight(); ++j) {
            cout << " ";
        }
        // 输出当前节点
        cout << arr[i].getValue();
    }

    cout << endl;

    for (int i = 0; i < num; i++) {
        for (int j = 0; j < arr[i].getHeight(); ++j) {
            cout << " ";
        }
        // 判断是否有子节点，有的话 len + 1，用于构建新数组
        if (arr[i].getLeft() != nullptr) {
            cout << "/";
            len++;
        }
        if (arr[i].getRight() != nullptr) {
            cout << "\\";
            len++;
        }
    }

    cout << endl;

    auto *newArr = new BinarySearchTreeNode[len];

    for (int i = 0, j = 0; i < num; i++) {
        if (arr[i].getLeft() != nullptr) {
            newArr[j] = arr[i].getLeft();
            j++;
        }
        if (arr[i].getRight() != nullptr) {
            newArr[j] = arr[i].getRight();
            j++;
        }
    }

    showTree(newArr, len);
}

/**
 * 获取整棵树的最小值
 * @return
 */
BinarySearchTreeNode *BinarySearchTree::minimum() {
    auto *arr = new BinarySearchTreeNode[1];
    arr[0] = this->root;
    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(5);
    tree->addNode(2);
    tree->addNode(4);
    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);
    cout << "count is " << tree->getCount() << endl;
    cout << "是否是二分搜索树 : " << tree->isBST() << endl;
    cout << "是否是平衡二分搜索树 : " << tree->isBalanced() << endl;

    tree->midShow();


    tree->deleteNode(9);
    tree->deleteNode(7);
    tree->deleteNode(13);
    tree->deleteNode(15);
    tree->deleteNode(14);
    tree->deleteNode(16);
    tree->deleteNode(4);
    tree->midShow();
    cout << "count is " << tree->getCount() << endl;
    cout << "是否是二分搜索树 : " << tree->isBST() << endl;
    cout << "是否是平衡二分搜索树 : " << tree->isBalanced() << endl;

    delete (tree);

    return 0;
}