数据结构(十)二叉排序树

末蓝、 2022-05-31 03:15 255阅读 0赞

**1、算法流程**

(1)树的构建与插入、查找

二叉排序树主要是通过逐个节点插入的方式进行构建树；每插入一个新节点p的时候，从根节点开始判断key值大小，确定往左走还是往右走，逐步递归，直到走到叶子节点，无路可走了，然后插入该节点；需要注意的是：每个新插入的点，肯定都是叶子节点；另外没有办法一次性构建一整颗树。

(2)求取最大最小值

从树根节点开始，一直往左走，就是最小值；一直往右走，就是最大值

(3)查找P的前驱节点与后继节点

前驱节点：P的左子树里面，数值最大的那个节点；对左子树递归寻找最大值(向右一直走到底)；因此需要先写好步骤(1)求取某个节点下面最大、最小值的函数；

(4)节点删除

分为两种情况：

情况一 如果待删除点P有做左节点，那么就找左子树的前驱节点来替代(存在左节点的情况包含了只有左节点和同时有左右节点两种情况)；

情况二 如果没有左节点，那么表示P要么只有右节点，要么是叶子节点，这两种情况都可以直接用P的右叶子节点来替代P(因为当p是叶子节点的时候，右节点也是为空节点，可以直接与p节点的父节点相连)。

**2、代码实现**

写代码需要更新几个信息：

A、P节点的父节点p\_parent，把p\_parent的孩子指针更改为替换点Q；

B、Q节点的原始父节点q\_parent，要与Q的原始子节点相连；

C、把Q的左右孩子也要更新一下，更新成P原来的左右孩子；

D、如果P是树根，要考虑到树根指针head信息要更新一下；

E、要考虑P与Q刚好是父子情况。

#include <iostream>
    using namespace std;
    class sorting_tree{//二叉排序树,python字典测试
        class node{
    
        public:
            node(int key,string value){
                this->key=key;
                this->value=value;
                left=NULL;
                right=NULL;
            };
            ~node(){};
            node* left;//左右孩子
            node* right;
            int key;
            string value;
        };
    
    public:
    
        sorting_tree(){
            head=NULL;
        };
        ~sorting_tree(){
            if (head)
                delete_tree(head);
        };
        node* head;//树的跟节点
        
    public:
        node * search_last_node(int key)//返回最后一个匹配节点
        {
            node *temp=head;
            while (temp)//一直走到某个节点是叶子节点
            {
                if(temp->key>key&&temp->left)//往左走
                    temp=temp->left;
                else if(temp->key<key&&temp->right)//往右走
                    temp=temp->right;
                else break;//遇到相等的情况搜索结束；遇到无路可走，也是结束搜索
            }
    
            return temp;
    
        }
        void insert(int key,string value)//插入
        {
            node * p=new node(key,value);
            if (!head)
            {
                head=p;
                return;
            }
            node* temp=search_last_node(p->key);
            if(temp->key>p->key)
            {
                temp->left=p;
            }
    
            else if(temp->key<p->key) {
                temp->right = p;
            }
            else
                temp->value=p->value;//节点已经存在的情况
        }
    
        node* search(int key){
            node* temp=search_last_node(key);
            if (temp->key!=key)
            {
                std::cout<<"未找到匹配key值："<<key<<std::endl;
                return NULL;
            }
            return temp;
        }
        void print(node*p){//中序遍历，打印一棵排序树
            if(!p)
                return;
            print(p->left);
            std::cout<<"key:"<<p->key<<"  value:"<<p->value<<std::endl;
            print(p->right);
        }
        void delete_tree(node*p){
            if(!p)
                return;
            delete_tree(p->left);//需要采用后续遍历的方式，否则节点提前被删除，即将出现空指针
            delete_tree(p->right);
            delete p;
    
        }
        node* get_max_node(node *p){//获取最大值
            while (p->right)
            {
                p=p->right;
            }
            return p;
        }
        node*get_min_node(node*p)//获取最小值
        {
            while (p->left)
            {
                p=p->left;
            }
            return p;
        }
        void delete_node(int key){
    
            node *p=head;
            node *p_parent=NULL;//记录key的父节点，一会儿要更新父节点信息
            while (p)//一直走到某个节点是叶子节点
            {
    
                if(p->key>key&&p->left)//往左走
                {
                    p_parent=p;
                    p=p->left;
    
                }
    
                else if(p->key<key&&p->right)//往右走
                {
                    p_parent=p;
                    p=p->right;
                }
                else break;//遇到相等的情况搜索结束；遇到无路可走，也是结束搜索
            }
    
            if(p->key!=key)//没有匹配节点可以删除
                return;
    
    
            if(p->left)
            {
                //找p节点左子树中，数值最大的那个节点,也就是前驱节点
                node*q=p->left;
                node*q_parent=p;
                while (q->right)
                {
                    q_parent=q;
                    q=p->right;
                }
    
                if(p_parent)//确保不是根节点要被删除
                {
                    if (p_parent->left==p)
                    {
                        p_parent->left=q;
                    }
                    else p_parent->right=q;
                }
                else head=q;
    
    
    
                if(q_parent!=p)//q被移走后，其原来的父节点要与其原来的子节点相连
                {
                    q_parent->right=q->right;
                    q->left=p->left;
                }
    
                q->right=p->right;
    
            }
    
            else
            {
                if(p_parent)
                {
                    if (p_parent->left==p)
                    {
                        p_parent->left=p->right;
                    }
                    else p_parent->right=p->right;
                }
                else head=p->right;
    
            }
    
    
    
            delete p;
    
        }
    
        //测试函数
        void main(){
            int key[10]={1,3,2,6,5,4,8,7,9,2};
            string value[10]={"fasa","df","fds","df","fd","fd","f","fdas","d","f"};
            for (int i = 0; i <10 ; ++i) {
                insert(key[i],value[i]);
            }
            print(head);
    
    
            node*p5=search(5);
            if (p5)
                std::cout<<"search key:"<<p5->key<<" value:"<<p5->value<<std::endl;
    
    
            delete_node(6);
            delete_node(5);
            print(head);
    
        }
    };