DS二叉排序树之创建和插入

﹏ヽ暗。殇╰゛Y 2023-10-04 14:38 11阅读 0赞

#### 文章目录 ####

*  题目
 *  实现思路
 *  代码

--------------------

## 题目 ##

给出一个数据序列，建立二叉排序树，并实现插入功能

对二叉排序树进行中序遍历，可以得到有序的数据序列

> 输入

第一行输入t，表示有t个数据序列

第二行输入n，表示首个序列包含n个数据

第三行输入n个数据，都是自然数且互不相同，数据之间用空格隔开

第四行输入m，表示要插入m个数据

从第五行起，输入m行，每行一个要插入的数据，都是自然数且和前面的数据不等

以此类推输入下一个示例

> 输出

第一行输出有序的数据序列，对二叉排序树进行中序遍历可以得到

从第二行起，输出插入第m个数据后的有序序列，输出m行

以此类推输出下一个示例的结果

--------------------

样例输入  
1  
6  
22 33 55 66 11 44  
3  
77  
50  
10  
样例输出  
11 22 33 44 55 66  
11 22 33 44 55 66 77  
11 22 33 44 50 55 66 77  
10 11 22 33 44 50 55 66 77

## 实现思路 ##

> 未完待续

## 代码 ##

#include<iostream>
    #include<cstring>
    using namespace std;
    
    #define ok 1
    #define error -1
    int a[1000];
    
    typedef struct BiTNode{
        
        int data;
        struct BiTNode * lchild, * rchild;
        BiTNode():data(-1),lchild(NULL),rchild(NULL){
        }
    }BiTNode, *BiTree;
    
    /***
     * T 指向排序二叉树的根
     * key 为要查找的元素
     * 若查找成功，P指向该元素的节点，并返回ok
     * 若查找失败，p指向查找路径上方问的最后一个节点，
     * 并返回false，指针f指向T的双亲，其初始调用职位NULL
     * */
    int SearchBST(BiTree T, int key, BiTree f, BiTree *p){
        
        if(!T){
        
            *p = f;
            return error;
        }
        else if( T->data == key ){
        
            *p = T;
            return ok;
        }
        else if( key < T->data ){
        
            SearchBST(T->lchild, key, T, p);
        }
        else if( key>T->data){
        
            SearchBST(T->rchild, key, T, p);
        }
    }
    
    int insert(BiTree *T, int e){
        
        BiTree p = NULL;
        if( SearchBST(*T,e,NULL, &p)==error ){
        
            BiTree s = new BiTNode;
            s->data = e;
            if(!p){
        
                *T = s;
            }else if( e<p->data ){
        
                p->lchild = s;
            }else if( e>p->data ){
        
                p->rchild = s;
            }
            return ok;
        }
        return error;
    }
    void midOrder(BiTree T){
        
        if(!T){
        
            return ;
        }
        // cout<<"1"<<endl;
        midOrder(T->lchild);
        cout<<T->data<<' ';
        midOrder(T->rchild);
    }
    
    int Delete(BiTree *p){
        
        BiTree q,s;
        if(!(*p)->lchild && !(*p)->rchild ){
        
            *p = NULL;
        }else if( !(*p)->lchild ){
        
            //左子树为空，只需用结点 p 的右子树根结点代替结点 p 即可；
            q = *p;
            *p = (*p)->rchild;
            delete q;
        }else if( !(*p)->rchild ){
        
            //右子树为空，只需用结点 p 的左子树根结点代替结点 p 即可；
            q = *p;
            *p = (*p)->lchild;
            delete q;
        }else{
        
            // 都不空
            q = *p;
            s = (*p)->lchild;
            while(s->rchild){
        
                q = s;
                s = s->rchild;
            }
            (*p)->data = s->data;
            if( q != *p ){
        
                q->rchild = s->lchild;
            }else{
        
                q->lchild = s->lchild;
            }
            delete s;
        }
        return ok;
    }
    int DELBST(BiTree *T, int key){
        
        if(!(*T)){
        
            return error;
        }
        if( key== (*T)->data ){
        
            Delete (T);
            return ok;
        }else if( key < (*T)->data ){
        
            DELBST((&(*T)->lchild), key);
        }else{
        
            DELBST((&(*T)->rchild), key);
        }
    }
    
    int main(){
        
       int t;
       cin>>t;
       while(t--){
        
           memset(a,0,sizeof(a));
           int len;
           cin>>len;
           BiTree T = NULL;
           for(int i=0; i<len; i++){
        
               cin>>a[i];
               insert(&T,a[i]);
           }
           midOrder(T);
           cout<<endl;
          int op;
          cin>>op;
          while(op--){
        
              int temp;
              cin>>temp;
              insert(&T, temp );
            // DELBST(&T,temp);
              midOrder(T);
            
              cout<<endl;
          }
       }
       return 0;
    }