入门二叉搜索树的世界

﹏ヽ暗。殇╰゛Y 2022-08-13 11:51 85阅读 0赞

# 入门二叉搜索树的世界 #

## 1. 二叉搜索树的概念 ##

二叉搜索树，二叉查找树，二叉排序树说的都是一个概念。这篇博文中我们称其为二叉搜索树。二叉搜索树指的是一棵空树，或者具有下列性质的二叉树：

1）弱左字数不空，则左子树上所有节点的值均小于根节点的值；

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

3）左、右子树也分别为二叉搜索树；

## 2. 二叉搜索树的程序实现 ##

#include <iostream>
    
    using namespace std;
    
    struct node
    {
        int data;
        node *left;
        node *right;
    };
    
    node *root=NULL;
    
    node * insert(node *currentNode, int key)  //插入节点函数，currentNode是当前节点，key是需要插入的值
    {
        if(currentNode==NULL)  //如果当前节点为空，那么要么是叶子，要么是空树的情况
        {
            currentNode=new node;  //申请一个节点空间
            currentNode->data=key;
            currentNode->left=currentNode->right=NULL;  //其子代指向空
            if(root==NULL)  //如果根节点为空，那么就是一个空树插入数据的情况
                root=currentNode;  //那么就直接把该节点作为根节点即可
        }
        else
        {
            if(key<currentNode->data)  //需要插入的值比节点小
                currentNode->left=insert(currentNode->left, key);
            else  //需要插入的值比节点大
                currentNode->right=insert(currentNode->right, key);
        }
        return currentNode;
    }
    
    
    void print(node *currentNode)  //中序遍历，输出的是递增序列
    {
        if(currentNode!=NULL)
        {
            if(currentNode->left!=NULL)
                print(currentNode->left);
            cout<<currentNode->data<<' ';  //中序遍历
            if(currentNode->right!=NULL)
                print(currentNode->right);
        }
    }
    
    
    node * search(node *currentNode, int x)  //查找元素，currentNode是当前节点，不能是root，x是需要查找的值
    {
        node *result=NULL;
        if(currentNode!=NULL)
        {
            if(currentNode->data==x)
                result=currentNode;
            else if(x<currentNode->data)
                result=search(currentNode->left, x);
            else
                result=search(currentNode->right, x);
        }
        return result;
    }
    
    node * findParent(node *currentNode, int x)
    {
        node *result=NULL;
        if(currentNode!=NULL)
        {
            if(x<currentNode->data && currentNode->left!=NULL)  //一旦进入if，就意味中需要找的父节点一定在根节点的左子树中
            {
                if(x==currentNode->left->data)
                    result=currentNode;
                else
                {
                    result=findParent(currentNode->left, x);  //继续寻找左子树
                    if(result==NULL)
                        result=findParent(currentNode->right, x);  //如果左子树没有，则寻找右子树
                }
            }
    
            if(x>currentNode->data && currentNode->right!=NULL)  //一旦进入if，就意味中需要找的父节点一定在根节点的右子树中
            {
                if(x==currentNode->right->data)
                    result=currentNode;
                else
                {
                    result=findParent(currentNode->left, x);  //继续寻找左子树
                    if(result==NULL)
                        result=findParent(currentNode->right, x);  //如果左子树没有，则寻找右子树
                }
            }
        }
        return result;
    }
    
    
    void deleteNode(int x)
    {
        node *parent=findParent(root, x);
        node *dNode=search(root, x);
        if(dNode==NULL)
        {
            cout<<"Not Found!"<<endl;
            return;
        }
    
        if(dNode->left==NULL && dNode->right==NULL)  //需要删除的节点是叶子节点
        {
            if(parent==NULL)
                root=NULL;
            else
            {
                if(dNode==parent->left)
                    parent->left=NULL;  //删除节点直接令它为空，不像链表中就比较复杂
                else
                    parent->right=NULL;
            }
        }
    
        else if(dNode->left==NULL)  //需要删除的节点只有左子树
        {
            if(parent==NULL)
                root=NULL;
            else
            {
                if(dNode==parent->left)
                    parent->left=NULL;
                else
                    parent->right=NULL;
            }
        }
    
        else if(dNode->right==NULL)  //需要删除的节点只有右子树
        {
            if(parent==NULL)
                root=NULL;
            else
            {
                if(dNode==parent->left)
                    parent->left=NULL;
                else
                    parent->right=NULL;
            }
        }
    
        else  //如果删除节点左子树右子树都有。
            //首先，找到删除节点的直接后继节点和后继节点的父节点；
            //然后，让后继节点替换掉删除节点，注意这里要先把删除节点的左右子树复制给后继节点的子树，再把删除节点的父节点作为后继节点的父节点
            //最后，在把后继节点的父节点的左子树（即后继节点原来的位置）删除，即可。
        {
            node *newNode=dNode->right;
            node *newNodeParent=NULL;
            while(newNode->left!=NULL)  //找到删除节点的直接后继节点，也就是删除节点的右子树中最左的那个
            {
                newNodeParent=newNode;
                newNode=newNode->left;
            }
    
            if(newNode!=dNode->left)
                newNode->left=dNode->left;
            if(newNode!=dNode->right)
                newNode->right=dNode->right;
            if(parent==NULL)
                root=newNode;
            else
            {
                if(dNode==parent->left)
                    parent->left=newNode;
                else
                    parent->right=newNode;
            }
            if(newNodeParent!=NULL)
                newNodeParent->left=NULL;
        }
    
    }
    
    int main()
    {
        int dataArray[12]={15,6,18,3,7,17,20,2,4,13,9,21};
        int length=12;
    
        //新建一个二叉搜索树
        for(int i=0; i<length; i++)  //构建二叉搜索树是一个不断插入节点的过程
        {
            insert(root, dataArray[i]);
        }
    
        //打印二叉搜索树 中序遍历
        print(root);
        cout<<endl;
    
        //查找元素
        node *result=search(root, 15);
        if(result!=NULL)
            cout<<"Found!"<<endl;
        else
            cout<<"None!"<<endl;
    
        //找到一个值的父节点
        result=findParent(root, 4);  //这儿若是根节点，则返回空，否则都是可以找到的。数组的第一个元素就是根节点
        if(result!=NULL)
            cout<<"Found!  "<<result->data<<endl;  //可以输出根节点
        else
            cout<<"None!"<<endl;
    
        //删除节点
        deleteNode(4);  //删除叶子节点
        print(root);
        cout<<endl;
    
        deleteNode(21);  //删除只有右子树节点
        print(root);
        cout<<endl;
    
        deleteNode(13);  //删除只有左子树节点
        print(root);
        cout<<endl;
    
        deleteNode(15);  //6,18,15//删除左右子树都有的节点
        print(root);
        cout<<endl;
    
        return 0;
    }

删除节点是其中最为复杂的，而在删除中最为复杂的就是删除左右子树都有的节点。具体的做法在注释中已经详细说明，发现网上大神的一副图来展示这个删除的过程，说的特别好，粘贴过来~~嘻嘻。

![SouthEast][]

参考链接：

http://www.cnblogs.com/aiyelinglong/archive/2012/03/27/2419972.html

http://blog.csdn.net/lvsi12/article/details/8232052

[SouthEast]: /images/20220810/895844276e454be99b8d9c16a6db3768.png