[数据结构与算法]数据结构——树（四）（2022考研）

二叉排序树

#include<stdio.h>
#include<stdlib.h>

typedef struct BSTNode{
    int key;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;

BSTNode *BSTsearch1(BSTree T,int e){
    while(T!=NULL){
        if(T->key<e)
            T=T->rchild;
        if(T->key>e)
            T=T->lchild;
        if(T->key==e)
            return T;
    }
    return NULL;
}

BSTNode * BSTsearch2(BSTree T,int e){
    if(T->key==e)
        return T;
    else if(T->key<e)
        return BSTsearch2(T->rchild,e);
    else if(T->key>e)
        return BSTsearch2(T->lchild,e);
    else
        return NULL;
}

int BSTInsert(BSTree &T,int e){
    if(T==NULL){
        T= (BSTNode*)malloc(sizeof (BSTNode));
        T->key=e;
        T->lchild=T->rchild=NULL;
        return 1;
    }
    else if(T->key>e)
        return BSTInsert(T->lchild,e);
    else if(T->key<e)
        return BSTInsert(T->rchild,e);
    else if(T->key==e)
        return 0;
}

void BSTCreate(BSTree &T,int str[],int n){
    T=NULL;
    int i=0;
    while(i<n){
        BSTInsert(T,str[i]);
        i++;
    }
}

下面是习题和部分代码

//习题5.6---判断是否是二叉排序树
int predt=-32767;
int JudgeBST(BSTree T){
    int b1,b2;
    if(T==NULL)
        return 1;
    else{
        b1= JudgeBST(T->lchild);
        if(b1==0 || predt>=T->key)
            return 0;
        predt=T->key;
        b2= JudgeBST(T->rchild);
        return b2;
    }
}

//习题5.7---求结点在二叉树的层次
int SearchLevel(BSTree T,BSTNode *p){
    int n=0;
    BSTree t=T;
    if(T!=NULL){
        n++;
        while(t->key!=p->key){
            if(p->key<t->key)
                t=t->lchild;
            else
                t=t->rchild;
            n++;
        }
    }
    return n;
}

//习题5.8---检测是否是平衡二叉树
void JudgeAVL(BSTree T,int &balance,int &h){
    int bl=0,br=0,hl=0,hr=0;
    if(T==NULL){
        h=0;
        balance=1;
    }
    else if(T->lchild==NULL && T->rchild==NULL){
        h=1;
        balance=1;
    }
    else{
        JudgeAVL(T->lchild,bl,hl);
        JudgeAVL(T->rchild,br,hr);
        h=(hl>hr?hl:hr)+1;
        if(abs(hl-hr)<2)
            balance=bl && br;
        else
            balance=0;
    }
}

//习题5.9---找出二叉排序树的最值
int MinKey(BSTree T){
    while(T->lchild!=NULL)
        T=T->lchild;
    return T->key;
}
int MaxKey(BSTree T){
    while(T->rchild!=NULL)
        T=T->rchild;
    return T->key;
}

//习题5.10---从大到小输出
void OutPut(BSTree T,int e){
    if(T==NULL)
        return;
    if(T->rchild!=NULL)
        OutPut(T->rchild,e);
    if(T->key>=e)
        printf("%d",T->key);
    if(T->lchild!=NULL)
        OutPut(T->lchild,e);
}

//习题5.12---查找第k小元素
BSTNode *SearchSmall(BSTNode *t,int k){
    if(k<1 || k>t->key)
        return NULL;
    if(t->lchild==NULL){
        if(k==1)
            return t;
        else
            return SearchSmall(t->rchild,k-1);
    }
    else{
        if(t->lchild->key==k-1)
            return t;
        if(t->lchild->key>k-1)
            return SearchSmall(t->lchild,k);
        if(t->lchild->key<k-1)
            return SearchSmall(t->rchild,k);
    }
}