前言

二叉排序树又叫二叉搜索树, 二叉查找树, 二叉树数据结构中相对简单的一种,一般情况下查询效率比链表高,二叉排序树在集合实际应用比较少,但它衍生出的AVL树和红黑树比较常用也比较难, 因此需要先掌握二叉排序树的结构

一：定义

二叉排序树可以是一棵空树，或者是具有下列性质的二叉树

1. 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；

2. 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；

3. 它的左右子树也分别为二叉排序树

补充：前驱与后继

前驱：节点的左子树不为空时,前驱为左子树中最大的节点(即左子树中最右节点)

后继：节点的右子树不为空时,后继为右子树中最小的节点(即右子树中最左节点)

二：插入节点

二叉排序树添加.png

三：删除节点(写法重点)

1：删除叶子节点(左右子节点都为空)时,不影响整体树结构,直接删除即可

2：删除的节点只有左子节点或只有右子节点(即右子节点为空或左子节点为空)时,只需要将其左子节点或右子节点代替删除的节点位置即可

删除只有左或右子节点.jpg

3：删除节点的左右子节点都不为空时,找到删除节点的前驱或者后继为替代删除的节点, 然后删除前驱或者后继点节即可,前驱节点为最右节点不存在右子节点,后继节点为最左节点不存在左子节点,因此删除前驱或后继节点又相当到第1,或第2步了

删除有左和右子节点.jpg

四：代码实现

struct BinarySortTreeNode {
    int data;
    BinarySortTreeNode *left = NULL;
    BinarySortTreeNode *right = NULL;
    BinarySortTreeNode(int data) {
        this->data = data;
    }
};

//二叉排序树
class BinarySortTree {
private:
    BinarySortTreeNode *root = NULL;
    int len = 0;
    //添加新节点
    BinarySortTreeNode* addNode(BinarySortTreeNode *node, int data);
    //移除节点
    BinarySortTreeNode* removeNode(BinarySortTreeNode *node, int data);
    //移除节点中最小的节点
    BinarySortTreeNode* removeLeftMinNode(BinarySortTreeNode *node, BinarySortTreeNode **successor);
    //释放节点及其所有子节点
    void freeNode(BinarySortTreeNode *node);
public:
    ~BinarySortTree();
    int size();
    void add(int data);
    void remove(int data);
    //层级打印
    void levelShow();
};

BinarySortTree::~BinarySortTree() {
    freeNode(root);
    root = NULL;
}

void BinarySortTree::freeNode(BinarySortTreeNode *node) {
    if (node) {
        freeNode(node->left);
        freeNode(node->right);
        delete node;
    }
}

BinarySortTreeNode* BinarySortTree::addNode(BinarySortTreeNode *node, int data) {
    if (!node) {
        len++;
        return new BinarySortTreeNode(data);
    }
    if (node->data > data) {
        node->left = addNode(node->left, data);
    } else {
        node->right = addNode(node->right, data);
    }
    return node;
}

BinarySortTreeNode* BinarySortTree::removeLeftMinNode(BinarySortTreeNode *node, BinarySortTreeNode **successor) {
    if (node->left) {
        node->left = removeLeftMinNode(node->left, successor);
        return node;
    } else {
        *successor = node;
        return node->right;
    }
}

BinarySortTreeNode* BinarySortTree::removeNode(BinarySortTreeNode *node, int data) {
    if (!node) return NULL;
    if (node->data > data) {
        node->left = removeNode(node->left, data);
    } else if (node->data < data) {
        node->right = removeNode(node->right, data);
    } else {  //相等
        len--;
        if (!node->left && !node->right) {
            delete node;
            return NULL;
        }
        if (!node->left) {
            BinarySortTreeNode *right = node->right;
            delete node;
            return right;//right not null
        }
        if (!node->right) {
            BinarySortTreeNode *left = node->left;
            delete node;
            return left; //left not null
        }
        //node right left都不为空
        BinarySortTreeNode *successor;
        //遍历查找后继节点时就直接断开后继节点
        node->right = removeLeftMinNode(node->right, &successor);
        node->data = successor->data;
        delete successor;
    }
    return node;
}

int BinarySortTree::size() {
    return this->len;
}

void BinarySortTree::add(int data) {
    root = addNode(root, data);
}

void BinarySortTree::remove(int data) {
    root = removeNode(root, data);
}

void BinarySortTree::levelShow() {
    std::string str;
    if (root) {
        ArrayDeque<BinarySortTreeNode*> nodeDeque;
        nodeDeque.push(root);
        while (!nodeDeque.isEmpty()) {
            BinarySortTreeNode *node = nodeDeque.pop();
            str += std::to_string(node->data);
            str += "(L:";
            if (node->left) {
                nodeDeque.push(node->left);
                str += to_string(node->left->data);
            } else {
                str +="#";
            }
            str += ",R:";
            if (node->right) {
                nodeDeque.push(node->right);
                str += to_string(node->right->data);
            } else {
                str +="#";
            }
            str += ')';
        }
    }
    LOGD("levelTree: %s", str.c_str());
}