二叉搜索树的创建，查找，添加，删除操作

二叉搜索树的创建，查找，添加，删除操作

查找操作

bool searchBst(bstNode *root,int key)
{
    
    if(root==nullptr)
    {
    
        return 0;
    }
    //比较当前值和当前结点的大小、
    else if(key==root->val)
    {
    
        return true;
    }
    else if(key>root->val)
    {
    
        return searchBst(root->right,key);
    }
    else if(key<root->val)
    {
    
        return searchBst(root->left,key);
    }
}

创建和增加操作

//parent指向root的双亲结点，其值初始化为0
//curr 保存查找的结点
//如果查找成功，则curr指向当前结点，并返回为true
//如果未能查找成功，curr指向当前查找路径的最后一个访问的结点并标记为false
bool searchBstNode(bstNode *root,int key,bstNode *parent,bstNode *&curr)
{
    
    if(root==nullptr)
    {
    
        curr=parent;
        return 0;
    }
    //比较当前值和当前结点的大小、
    else if(key==root->val)
    {
    
        curr=root;
        return true;
    }
    else if(key>root->val)
    {
    
        return searchBstNode(root->right,key,root,curr);
    }
    else if(key<root->val)
    {
    
        return searchBstNode(root->left,key,root,curr);
    }
}



//插入平衡二叉树
void insertBst(bstNode *&root,int key)
{
    
    bstNode * curr;
    bstNode *temp;
    //当查找的元素值不存在的时候，执行插入操作
    if(!searchBstNode(root,key,nullptr,curr))
    {
    
        //为结点分配空间
        temp=new bstNode();
        temp->val=key;
        temp->left=temp->right=nullptr;
        //如果curr不存在，则说明当前并没有树存在
        if(!curr)
        {
    
            root=temp;
        }
        else if(key<curr->val)
        {
    
            curr->left=temp;
        }
        else if(key>curr->val)
        {
    
            curr->right=temp;
        }
    }
    else
    {
    
        return;
    }
}

删除操作

void deleteNode(bstNode *&root)
{
    
    bstNode* curr;
    bstNode* temp;
    //判断当前根节点的左右结点是否存在，存在则对应不同的操作需求
    if(!root->left)
    {
    
        curr=root;
        //左节点不存在，则让当前结点指向待删除结点的右节点，哪怕该结点不存在也满足要求
        root=root->right;
        delete(curr);
    }

    else if (!root->right)
    {
    
        curr=root;
        root=root->left;
        delete(curr);
    }
//左右结点都存在
    else{
    
        curr=root;
        //temp指向当前结点的左孩子结点
        //因为左边都比当前结点小
        //那么就要找到左边的最大值
        temp=root->left;
        while(temp->left)
        {
    
            curr=temp;
            temp=temp->right;
        }
        //temp此时指向待删除结点的直接前驱，算法实现的是将待删除结点的直接前驱的值替代被删除结点的值
        root->val=temp->val;

        //当curr不指向root的时候，说明移动过curr,便让temp的左节点等与curr的右节点，因为curr是指向temp的双亲结点
        if(curr!=root)
        {
    
            curr->right=temp->left;
        }
        else
        {
    
            curr->left=temp->left;
        }
        delete temp;
    }
    
}


//二叉搜索树的删除操作
void deleteBst(bstNode *&root,int key)
{
    
    if(!root)
    {
    
        return;
    }

    if(key==(root->val))
    {
    
        //执行删除结点的操作
        deleteNode(root);
        cout<<"删除操作执行成功"<<endl;
    }
    else if(key>root->val)
    {
    
        deleteBst(root->right,key);
    }
    else if(key<root->val)
    {
    
        deleteBst(root->left,key);
    }
}

层序遍历操作

void layerBstTraveral(bstNode *root)
{
    
    if(root==nullptr)
    {
    
        cout<<"当前树并不存在"<<endl;
    }
    queue<bstNode *>que;
    que.push(root);
    while(!que.empty())
    {
    
        bstNode *curr=que.front();
        cout<<curr->val<<" ";
        if(curr->left)
        {
    
            que.push(curr->left);
        }
        if(curr->right)
        {
    
            que.push(curr->right);
        }
        que.pop();
    }
}

代码汇总

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

struct bstNode
{
    
    int val;
    bstNode *left;
    bstNode *right;
};

bool searchBst(bstNode *root,int key)
{
    
    if(root==nullptr)
    {
    
        return 0;
    }
    //比较当前值和当前结点的大小、
    else if(key==root->val)
    {
    
        return true;
    }
    else if(key>root->val)
    {
    
        return searchBst(root->right,key);
    }
    else if(key<root->val)
    {
    
        return searchBst(root->left,key);
    }
}
//parent指向root的双亲结点，其值初始化为0
//curr 保存查找的结点
//如果查找成功，则curr指向当前结点，并返回为true
//如果未能查找成功，curr指向当前查找路径的最后一个访问的结点并标记为false
bool searchBstNode(bstNode *root,int key,bstNode *parent,bstNode *&curr)
{
    
    if(root==nullptr)
    {
    
        curr=parent;
        return 0;
    }
    //比较当前值和当前结点的大小、
    else if(key==root->val)
    {
    
        curr=root;
        return true;
    }
    else if(key>root->val)
    {
    
        return searchBstNode(root->right,key,root,curr);
    }
    else if(key<root->val)
    {
    
        return searchBstNode(root->left,key,root,curr);
    }
}



//插入平衡二叉树
void insertBst(bstNode *&root,int key)
{
    
    bstNode * curr;
    bstNode *temp;
    //当查找的元素值不存在的时候，执行插入操作
    if(!searchBstNode(root,key,nullptr,curr))
    {
    
        //为结点分配空间
        temp=new bstNode();
        temp->val=key;
        temp->left=temp->right=nullptr;
        //如果curr不存在，则说明当前并没有树存在
        if(!curr)
        {
    
            root=temp;
        }
        else if(key<curr->val)
        {
    
            curr->left=temp;
        }
        else if(key>curr->val)
        {
    
            curr->right=temp;
        }
    }
    else
    {
    
        return;
    }
}


//层序遍历BST

void layerBstTraveral(bstNode *root)
{
    
    if(root==nullptr)
    {
    
        cout<<"当前树并不存在"<<endl;
    }
    queue<bstNode *>que;
    que.push(root);
    while(!que.empty())
    {
    
        bstNode *curr=que.front();
        cout<<curr->val<<" ";
        if(curr->left)
        {
    
            que.push(curr->left);
        }
        if(curr->right)
        {
    
            que.push(curr->right);
        }
        que.pop();
    }
}


void deleteNode(bstNode *&root)
{
    
    bstNode* curr;
    bstNode* temp;
    //判断当前根节点的左右结点是否存在，存在则对应不同的操作需求
    if(!root->left)
    {
    
        curr=root;
        //左节点不存在，则让当前结点指向待删除结点的右节点，哪怕该结点不存在也满足要求
        root=root->right;
        delete(curr);
    }

    else if (!root->right)
    {
    
        curr=root;
        root=root->left;
        delete(curr);
    }
//左右结点都存在
    else{
    
        curr=root;
        //temp指向当前结点的左孩子结点
        //因为左边都比当前结点小
        //那么就要找到左边的最大值
        temp=root->left;
        while(temp->left)
        {
    
            curr=temp;
            temp=temp->right;
        }
        //temp此时指向待删除结点的直接前驱，算法实现的是将待删除结点的直接前驱的值替代被删除结点的值
        root->val=temp->val;

        //当curr不指向root的时候，说明移动过curr,便让temp的左节点等与curr的右节点，因为curr是指向temp的双亲结点
        if(curr!=root)
        {
    
            curr->right=temp->left;
        }
        else
        {
    
            curr->left=temp->left;
        }
        delete temp;
    }
    
}


//二叉搜索树的删除操作
void deleteBst(bstNode *&root,int key)
{
    
    if(!root)
    {
    
        return;
    }

    if(key==(root->val))
    {
    
        //执行删除结点的操作
        deleteNode(root);
        cout<<"删除操作执行成功"<<endl;
    }
    else if(key>root->val)
    {
    
        deleteBst(root->right,key);
    }
    else if(key<root->val)
    {
    
        deleteBst(root->left,key);
    }
}

int main()
{
    
    vector<int>a={
    62,88,58,47,35,73,51,99,37,93};
    bstNode *root=nullptr;

    for(auto i:a)
    {
    
        insertBst(root,i);
    }
    cout<<"层序遍历的结果：";
    layerBstTraveral(root);
    cout<<endl;

    cout<<"查找99在树中是否存在: ";
    cout<<searchBst(root,99)<<endl;
    
    cout<<"查找100在树中是否存在: ";
    cout<<searchBst(root,100)<<endl;


    cout<<"删除结点58: ";
    deleteBst(root,58);

    cout<<"层序遍历的结果：";
    layerBstTraveral(root);
    cout<<endl;

}