二叉排序树

#include<iostream>

using namespace std;

typedef int datatype;
typedef struct node
{
    datatype key;
    struct node *lchild,*rchild;
}bsnode;   // 二叉排序树
typedef bsnode* bstree;  

bstree bssearch(bstree t, datatype x)
{
    //    非递归

    bstree p = t;
    while(p)
    {
        if(x == p->key) return p;
        p = (x<p->key) ? p->lchild : p->rchild ;
    }

    return NULL ;
}


bstree bssearch2( bstree t, datatype x)
{
    //递归

    if(t == NULL || x == t->key)  return t;

    if(x<t->key) return bssearch2(t->lchild,x) ;
    else return bssearch2(t->rchild,x) ;
}


void InsertBstree( bstree * t /* 二级指针*/, datatype x)
{
    bstree f,p;  //  f用于保存新节点的最新插入位置前驱
    p=*t;

    while(p)
    {
        if(x == p->key) return ;// 若二叉树t中已有x ，则无需插入
        f=p;
        p= ( x<p->key ) ? p->lchild : p->rchild;
    }

    p = (bstree) malloc (sizeof(bsnode));
    p->key = x;
    p->lchild=p->rchild=NULL;

    if(*t == NULL ) *t=p; //原树为空
    else if(x<f->key) f->lchild=p;
    else f->rchild=p;
}
 
bstree CreatBstree(int r[], int n)
{
    int i;
    bstree t=NULL;
    for(int i=0;i<n;i++)
        InsertBstree(&t , r[i]);

    return t;

}


void bssearch1(bstree t,datatype x,bstree *f,bstree *p){/*非递归查找*/
    *f=NULL;//记录父结点
    *p=t;
    while(*p){
        if(x==(*p)->key)
            return ;
        *f=*p;
        *p=(x<(*p)->key?(*p)->lchild:(*p)->rchild);
    }
    return ;
}


void mid_print(bstree t)
{
    if(t)
    {
        mid_print(t->lchild);
        printf("%d ",t->key);
        mid_print(t->rchild);
    }

}


bstree DelBstree(bstree t,datatype x){//删除
    bstree p,q,child;
    bssearch1(t,x,&p,&q);//查找

    if(q){
        if(q->lchild==NULL && q->rchild==NULL){//叶结点
            if(p){
                if(p->lchild==q)
                    p->lchild=NULL;
                else
                    p->rchild=NULL;
            }
            else
                t=NULL;//如果q为根结点，t为空
            free(q);//删除后，释放q
        }
        else if(q->rchild==NULL){//q的右孩子为空
            if(p){
                if(p->lchild==q)
                    p->lchild=q->lchild;
                else
                    p->rchild=q->lchild;
            }
            else
                t=q->lchild;
            free(q);
        }
        else if(q->lchild==NULL){//q的左孩子为空
            if(p){
                if(p->lchild==q)
                    p->lchild=q->rchild;
                else
                    p->rchild=q->rchild;
            }
            else
                t=q->rchild;
            free(q);
        }
        else{//q的左孩子、右孩子均不为空
            child=q->rchild;
            while(child->lchild)
                child=child->lchild;//相当于找到q的直接后继
            child->lchild=q->lchild;
            if(p){
                if(p->lchild==q)
                    p->lchild=q->rchild;
                else
                    p->rchild=q->rchild;
            }
            else
                t=q->rchild;
            free(q);
        }
    }
    return t;
}

int main(){

    int arr[]={99,3,2,4,5,2,9,0,5,14,5243,64,67,324,5145};
    bstree t=CreatBstree(arr,15);

     mid_print(t);
    
    cout<<endl;

    t=DelBstree(t,66);

    mid_print(t);
    return 0;
}

二叉排序树

原文：https://www.cnblogs.com/lkfsblogs/p/12976833.html