2020-05-25学习随笔

序言

学习随笔是本人对自己一天的自学回顾，由于本人是非科班出身，不懂很多cs的专业术语，所以难免会有些错误，望各位批评指正，本人定当悉心接受并立即改正。希望自己能够慢慢坚持下去，坚持转行的道路，坚持每天学习的输出。

数据结构

二叉排序树

性质

1.若左子树不为空，则左子树上所有结点的值均小于它根结点的值

2.若右子树不为空，则右子树上所有结点的值均小于它根结点的值

3.左、右子树均为二叉排序树

代码

1.定义

typedef struct BiTNode{
    int data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

2.查找（运用了递归思想）

Status SearchBST(BiTree T,int key,BiTree f,BiTree *p)
//在T中查找key，找到把信息存储在p中，f用来存储T的双亲
{
    if(!T){
        *p=f;
        return FALSE;
    }
    else if(key==T->data){
        *p=T;
        return TURE;
    }
    else if(key<T->data){
        return SearchBST(T->lchild,key,T,p);
        //key比T->data小，就到左子树里面去找
    }
    else return SearchBST(T->rchild,key,T,p); 
        //key比T->data大，就到右子树里面去找
}

3.插入（先查再插）

Status InsertBST(BiTree *T,int key){//插入key
    BiTree p,s;
    if(!SearchBST(*T,key,NULL,&p)){
        s=(BiTree)malloc(sizeof(BiTNode));
        s->data=key;
        s->lchild=s->rchild=NULL;
        //因为没有找到，所以p里面是T双亲的信息
        if(!p) *T=s;//空树
        else if(key<p->data) p->lchild=s;//插在左子树位置
        else p->rchild=s;//插在右子树位置
        return TRUE;
    }
    else return FALSE;
}

4.删除

Status DeleteBST(BiTree *T,int key){
    if(!*T) return FALSE;
    else{
        if(key==T->data) return Delete(T);
        else if(key<T->data) return DeleteBST(&(*T)->lchild,key);
        else return DeleteBST(&(*T)->rchild,key);
    }
}

Status Delete(BiTree *p){
    BiTree q,s;
    if((*p)->rchild==NULL){//p无右子树
        q=*p;
        *p=(*p)->lchild;
        free(q);
    }
    else if((*p)->lchild==NULL){//p无左子树
        q=*p;
        *p=(*p)->rchild;
        free(q);
    }
    else {
        q=*p;
        s=(*p)->lchild;
        while(s->rchild){//一直往右找是为了找到仅次于p的最大值，来代替p
            q=s;//q是s的双亲
            s=s->rchild;
        }
        (*p)->data=s->data;//替代p
        if(q!=*p) q->rchild=s->lchild;//不等的时候s是q的右子树，所以右子树空缺，因为s要没了，所以要找一个来替代s，
        else q->lchild=s->lchild;//相等的时候，s是q的左子树，所以左子树空缺
        free(s);
    }
    return TRUE;
}

树，真的非常非常难