二叉排序树的增删改查

插入查找修改没什么好说的比较基础重点看一下删除

删除操作详解

首先明确一个点删除一个节点一般都是要用到它的父指针把父指针移动到别的地方这里我定义的函数为deleteNode(BSTNode*cur) 通常是让
parent.left or parent.right=deleteNodeBST(....对应的孩子)
对于最初的根同理this->root=deleteNodeIterator(data, root);
删除的时候我们并不是修改指针的指向而是把需要删除的值用他的前驱或者后继节点的值覆盖掉然后把他的前驱或者后继给删除掉
删除的代码拿出来分析一下

BSTNode *BSTTree::deleteNodeIterator(char data, BSTNode*cur)
{
    if (!cur)return nullptr;
    if (data>cur->data)cur->rightChild= deleteNodeIterator(data, cur->rightChild);
    else if (data<cur->data)cur->leftChild=deleteNodeIterator(data,cur->leftChild);

这里 data大就要删除右子树的在里面找小就要删除左子树然后会返回一个合适的节点来代替当前cur的right 或者是left 也有可能什么都不改变就是data在树里面找不到对应的节点的情况的时候
下面是找到了也就是说当前的节点就是我要删除的节点
共有如下三个情况

cur是叶子节点返回null
cur只有左子树返回 cur.leftChild
cur只有右子树返回 cur.rightChild
左右子树都有这里我采用用后继节点代替的情况当然也可以用前驱节点原理是类似的
首先定义个parent指针指向cur next指向 cur.right 既然是找后继节点那肯定要先走右子树目的是找到右子树中最左边的节点当前的情况保证了是有右子树的然后就是开始循环了

 while(next->leftChild)
           {
               parent=next;
               next=next->leftChild;
           }

这个循环的目的是找到next 将其移动到cur的后继节点上去当然这个循环有可能完全就不执行这也是我们为什么后面需要判断一下的情况
如果是下面这种情况这个循环就不会触发

         cur     <----parent
	/  \
       a    b    <----next
             \
	      c

这样的话cur的用于替换的节点就应该是b但是我目前一次循环都没有进入 next还是parent的右孩子但是如果进入了循环一次的话 next就成为了parent的left孩子所以需要进行判断一下来确定b 也就是当前的next的子树的右子树到底该接在parent的哪边
上面这个图的情况就是要接在parent的右子树上因为要删除的是cur 后继节点是b 那我在进行完了循环之后就会有一部赋值的操作

cur->data=next->data;
           BSTNode* del=next;

现在b已经转移到了cur上那b就可以删除了只需要把parent的右子树接到next的右子树上就行了这里的del指针是为了保存一下next 也就是b的地址用于释放内存
另外一种情况就是

         cur     
	/  \
       a    b  <----parent  
           / \
next----> c   d	 
           \  
	    e

那这种情况就是要把e接到b的左子树上面了
于是就有了如下的判断代码

 if (next==parent->leftChild)
               parent->leftChild=next->rightChild;
           else
               parent->rightChild=next->rightChild;
           delete(del);

    else
    {
        if (!cur->leftChild&&!cur->rightChild)return nullptr;
        else if (!cur->leftChild)return cur->rightChild;
        else if (!cur->rightChild)return cur->leftChild;
        else
        {
            /**
             * 既不是叶子节点  也不是单枝树
             */
           BSTNode* parent=root;
           BSTNode* next=parent->rightChild;
           while(next->leftChild)
           {
               parent=next;
               next=next->leftChild;
           }
           cur->data=next->data;
           BSTNode* del=next;
           if (next==parent->leftChild)
               parent->leftChild=next->rightChild;
           else
               parent->rightChild=next->rightChild;
           delete(del);
        }
    }
    return cur;
}

整个程序的代码和测试main方法

BSTNode类

class BSTNode
{
public:
    BSTNode(char data);
    BSTNode();
    char  data;
    BSTNode* leftChild;
    BSTNode* rightChild;
    int cnt;
};

BSTNode::BSTNode(char data) : data(data)
{
    leftChild= nullptr;
    rightChild= nullptr;
    cnt=0;
}

BSTNode::BSTNode()
{
    data=' ';
    leftChild= nullptr;
    rightChild= nullptr;
    cnt=0;
}

BSTTree类

class BSTTree
{
    BSTNode* root;
    void inOrderIterator(BSTNode* root);
    BSTNode* removeIterator(BSTNode* cur, char data);
    BSTNode* searchIterator(char data,BSTNode * cur) ;
    BSTNode* insertIterator(char data,BSTNode* cur);
    BSTNode* deleteNodeIterator(char data, BSTNode* cur);
public:
    BSTTree();
    BSTNode* search(char data);
    BSTNode*  insert(char data);
    void inOrder();
    BSTNode* remove(char data);
    void destroyBTSTree(BSTNode* cur);
    virtual ~BSTTree();
    void init(std::string data);
    void   deleteNode(char data);
    BSTNode* successor(BSTNode* cur);//找直接后继的节点
    BSTNode* predecessor(BSTNode* cur);//找直接前驱的节点
    void inOrderLine();

    void inOrderLineIterator(BSTNode *cur);
};

//
// Created by 鸭子飞了 on 2020/12/3.
//

#include "BSTTree.h"
#include <iostream>

using namespace std;;
BSTTree::BSTTree()
{
    root= nullptr;
}



void BSTTree::inOrder()
{
    inOrderIterator(root);
    std::cout<<std::endl;
}

void BSTTree::inOrderIterator(BSTNode *cur)
{
    if (cur)
    {
        inOrderIterator(cur->leftChild);
        std::cout<<cur->data<<":"<<cur->cnt<<endl;
        inOrderIterator(cur->rightChild);
    }
}

BSTNode *BSTTree::remove(char data)
{
    removeIterator(root,data);
    return nullptr;
}

BSTNode *BSTTree::removeIterator(BSTNode *cur, char data)
{
    if (!cur)return nullptr;
    if (data<cur->data)cur->leftChild=removeIterator(cur->leftChild,data);
    else if (data>cur->data )cur->rightChild=removeIterator(cur->rightChild,data);
    else
    {
        if (!cur->rightChild&&!cur->leftChild)return nullptr;
        if (cur->leftChild== nullptr)
        {
            return cur->rightChild ;
        }
       if (cur->rightChild== nullptr)
       {
            return cur->leftChild;
       }
       /**
        * 左右子树都存在的情况
        */
    }
    return nullptr;
}

void BSTTree::destroyBTSTree(BSTNode *cur)
{
    if (cur== nullptr)
        return ;
    destroyBTSTree(cur->leftChild);
    destroyBTSTree(cur->rightChild);
    delete(cur);
}

BSTTree::~BSTTree()
{
    destroyBTSTree(root);
}

BSTNode *BSTTree::search(char data)
{
   return  searchIterator(data,root);
}

BSTNode *BSTTree::searchIterator(char data, BSTNode *cur)
{
    if (cur== nullptr)return nullptr;
    if (cur->data==data)return cur;
    if (data>cur->data)return searchIterator(data,cur->rightChild);
    if (data<cur->data)return searchIterator(data,cur->leftChild);
    return nullptr;
}

BSTNode *BSTTree::insert(char data)
{
    if (!root)
    {
        this->root=new BSTNode();
        root->data=data;
        root->cnt=1;
        return root;
    }
    BSTNode* searchRes=search(data);
    if (searchRes)searchRes->cnt++;
    else return insertIterator(data,root);
    return nullptr;

}

BSTNode *BSTTree::insertIterator(char data, BSTNode *cur)
{
    if (data>cur->data)
    {
        if (!cur->rightChild)
        {
            BSTNode* newNode=new BSTNode;
            newNode->cnt=1;
            newNode->data=data;
            cur->rightChild=newNode;
            return newNode;
        }
        else return insertIterator(data,cur->rightChild);
    }
    else
    {
        if (!cur->leftChild)
        {
            BSTNode* newNode=new BSTNode;
            newNode->cnt=1;
            newNode->data=data;
            cur->leftChild=newNode;
            return newNode;
        }
        else return insertIterator(data,cur->leftChild);
    }
}

void BSTTree::init(std::string data)
{
    for (int i = 0; i < data.length(); ++i)
    {
        this->insert(data[i]);
    }
}

void BSTTree::inOrderLine()
{
    this->inOrderLineIterator(root);
    cout<<endl;
}

void BSTTree::inOrderLineIterator(BSTNode *cur)
{
    if (cur)
    {
        inOrderLineIterator(cur->leftChild);
        for (int i = 0; i < cur->cnt; ++i)
        {
            cout<<cur->data;
        }
        inOrderLineIterator(cur->rightChild);
    }
}

void  BSTTree::deleteNode(char data)
{
    this->root=deleteNodeIterator(data, root);
}

BSTNode *BSTTree::deleteNodeIterator(char data, BSTNode*cur)
{
    if (!cur)return nullptr;
    if (data!=cur->data&&!cur->leftChild&&cur->rightChild)return cur;
    if (data>cur->data)cur->rightChild= deleteNodeIterator(data, cur->rightChild);
    else if (data<cur->data)cur->leftChild=deleteNodeIterator(data,cur->leftChild);
    else
    {
        if (!cur->leftChild&&!cur->rightChild)return nullptr;
        else if (!cur->leftChild)return cur->rightChild;
        else if (!cur->rightChild)return cur->leftChild;
        else
        {
            /**
             * 既不是叶子节点  也不是单枝树
             */
           BSTNode* parent=root;
           BSTNode* next=parent->rightChild;
           while(next->leftChild)
           {
               parent=next;
               next=next->leftChild;
           }
           cur->data=next->data;
           BSTNode* del=next;
           if (next==parent->leftChild)
           {
               parent->leftChild=next->rightChild;
           }
           else
           {
               parent->rightChild=next->rightChild;
           }
           delete(del);
        }
    }
    return cur;
}
/**
 * 找后继节点
 * @param cur
 * @return
 */
BSTNode *BSTTree::successor(BSTNode *cur)
{
    BSTNode* p=cur->rightChild;
    while(p->leftChild!= nullptr)
    {
        p=p->leftChild;
    }
    return p;
}
/**
 * 找前驱节点
 * @param cur
 * @return
 */
BSTNode *BSTTree::predecessor(BSTNode *cur)
{
    BSTNode* p=cur->leftChild;
    while(p->rightChild!= nullptr)
    {
        p=p->rightChild;
    }
    return p;
}

int main()
{

    string str;
    getline(cin,str);
    BSTTree* tree=new BSTTree;
    tree->init(str);
    tree->inOrder();
    tree->inOrderLine();
    char ch;
    cout<<"输入想要删除的字符: ";
    cin>>ch;
    tree->deleteNode(ch);
    tree->inOrder();
    tree->inOrderLine();
    delete(tree);
}

菜单

分享

二叉排序树的增删改查

删除操作详解

整个程序的代码和测试main方法

评论

资源汇总

Idea编辑器版块装订区域过宽的问题

Jackson中序列化器的设置

阻塞队列批量写入数据库实现

自建Syncthing中继服务器和发现服务器

利用SpringDataRedis操作Redis数据，比RedisTemplate更方便

Aria2搭建指南(基于Ubuntu22.04)

在Ubuntu22.04下配置MYSQL-8.0.33主从复制

SpringBoot打包瘦身

利用Jenkins实现自动化构建Maven项目