二叉搜索树的插入、删除节点

二叉树结构定义

struct Node
{
    int data=0;
    Node* parent=NULL;
    Node* lchild=NULL;
    Node* rchild=NULL;
    Node(int n)
    {
        data=n;
    }
};
class BinarySearchTree
{
    Node* root;
public:
Node* getRoot(){return root;}
Node* getNode(int data);//查找对应节点
Node* sucessor(Node *p);//查找对应节点的在中序遍历中的后继节点
        bool insert(int data);//插入
bool remove(int data);//删除
};

插入节点

bool BinarySearchTree::insert(int data) //插入
{
    Node *p = root, *newNode = new Node(data);
    Node *temp = p;
    if (!root) //空树
    {
        root = newNode; //插入的为根节点
    }
    else
    {
        while (p)
        {
            temp = p;
            if (data < p->data)
                p = p->lchild;
            else if (data > p->data)
                p = p->rchild;
            else
                return false;
        } //找到应该插入的位置
        newNode->parent = temp;
        if (newNode->data > temp->data)
            temp->rchild = newNode;
        else
            temp->lchild = newNode;
    }
    return true;
}

删除节点

bool BinarySearchTree::remove(int data)
{
    Node *p = getNode(data);
    if (!p->parent) //根节点
    {
        Node *q = sucessor(p); //找到后继节点
        int tempData = q->data;
        remove(q->data);    //删除后继节点
        p->data = tempData; //修改值为后继节点的值
        return true;
    }
    bool flag = p->data > p->parent->data; //是否为右子树，下面多次使用，特此做标记
    //如果是叶子节点，直接删除即可
    if (!p->lchild && !p->rchild)
    {
        if (flag)
            p->parent->rchild = NULL;
        else
            p->parent->lchild = NULL;
        delete p; //释放内存
    }
    else if (p->lchild && !p->rchild) //如果只有左子树
    {
        if (flag) //父节点的右子树指向当前节点的左子树
            p->parent->rchild = p->lchild;
        else //父节点的左子树指向当前节点的左子树
            p->parent->lchild = p->lchild;
    }
    else if (!p->lchild && p->rchild) //如果只有右子树
    {
        if (flag) //父节点的右子树指向当前节点的右子树
            p->parent->rchild = p->rchild;
        else //父节点的左子树指向当前节点的右子树
            p->parent->lchild = p->rchild;
    }
    else //既有左子树又有右子树
    {
        Node *q = sucessor(p); //找到后继节点
        p->data = q->data;     //修改值为后继节点的值
        remove(q->data);       //删除后继节点
    }
    return true;
}

辅助函数

Node *BinarySearchTree::getNode(int data)
{ //折半查找元素
    Node *p = root;
    while (p && p->data != data)
    {
        if (p->data < data)
        {
            p = p->rchild;
        }
        else
        {
            p = p->lchild;
        }
    }
    return p;
}
Node *BinarySearchTree::sucessor(Node *p)
{ //找到中序遍历的后继节点
    if (!p)
        return NULL;
    else if (p->rchild) //有右子树，找到右子树中最小的
    {
        p = p->rchild;
        while (p->lchild)
        {
            p = p->lchild;
        }
    }
    else //无右子树，找父节点
    {
        if (!p->parent)
            return NULL;
        while (p->parent)
        {
            if (p->parent->data <= p->data)
                p = p->parent;
        }
        p = p->parent;
    }
    return p;
}