平衡二叉树&二叉排序树

算法库：

#include <stdio.h>
#include <malloc.h>
typedef int KeyType;                    //定义关键字类型
typedef char InfoType;
typedef struct node                     //记录类型
{
    KeyType key;                        //关键字项
    int bf;                             //平衡因子
    InfoType data;                      //其他数据域
    struct node* lchild, * rchild;        //左右孩子指针
} BSTNode;
void LeftProcess(BSTNode*& p, int& taller)
//对以指针p所指结点为根的二叉树作左平衡旋转处理,本算法结束时,指针p指向新的根结点
{
    BSTNode* p1, * p2;
    if (p->bf == 0)           //原本左、右子树等高,现因左子树增高而使树增高
    {
        p->bf = 1;
        taller = 1;
    }
    else if (p->bf == -1)     //原本右子树比左子树高,现左、右子树等高
    {
        p->bf = 0;
        taller = 0;
    }
    else                    //原本左子树比右子树高,需作左子树的平衡处理
    {
        p1 = p->lchild;       //p指向*p的左子树根结点
        if (p1->bf == 1)      //新结点插入在*b的左孩子的左子树上,要作LL调整
        {
            p->lchild = p1->rchild;
            p1->rchild = p;
            p->bf = p1->bf = 0;
            p = p1;
        }
        else if (p1->bf == -1)    //新结点插入在*b的左孩子的右子树上,要作LR调整
        {
            p2 = p1->rchild;
            p1->rchild = p2->lchild;
            p2->lchild = p1;
            p->lchild = p2->rchild;
            p2->rchild = p;
            if (p2->bf == 0)          //新结点插在*p2处作为叶子结点的情况
                p->bf = p1->bf = 0;
            else if (p2->bf == 1)     //新结点插在*p2的左子树上的情况
            {
                p1->bf = 0;
                p->bf = -1;
            }
            else                    //新结点插在*p2的右子树上的情况
            {
                p1->bf = 1;
                p->bf = 0;
            }
            p = p2;
            p->bf = 0;            //仍将p指向新的根结点,并置其bf值为0
        }
        taller = 0;
    }
}
void RightProcess(BSTNode*& p, int& taller)
//对以指针p所指结点为根的二叉树作右平衡旋转处理,本算法结束时,指针p指向新的根结点
{
    BSTNode* p1, * p2;
    if (p->bf == 0)           //原本左、右子树等高,现因右子树增高而使树增高
    {
        p->bf = -1;
        taller = 1;
    }
    else if (p->bf == 1)      //原本左子树比右子树高,现左、右子树等高
    {
        p->bf = 0;
        taller = 0;
    }
    else                    //原本右子树比左子树高,需作右子树的平衡处理
    {
        p1 = p->rchild;       //p指向*p的右子树根结点
        if (p1->bf == -1)     //新结点插入在*b的右孩子的右子树上,要作RR调整
        {
            p->rchild = p1->lchild;
            p1->lchild = p;
            p->bf = p1->bf = 0;
            p = p1;
        }
        else if (p1->bf == 1) //新结点插入在*p的右孩子的左子树上,要作RL调整
        {
            p2 = p1->lchild;
            p1->lchild = p2->rchild;
            p2->rchild = p1;
            p->rchild = p2->lchild;
            p2->lchild = p;
            if (p2->bf == 0)          //新结点插在*p2处作为叶子结点的情况
                p->bf = p1->bf = 0;
            else if (p2->bf == -1)    //新结点插在*p2的右子树上的情况
            {
                p1->bf = 0;
                p->bf = 1;
            }
            else                    //新结点插在*p2的左子树上的情况
            {
                p1->bf = -1;
                p->bf = 0;
            }
            p = p2;
            p->bf = 0;            //仍将p指向新的根结点,并置其bf值为0
        }
        taller = 0;
    }
}
int InsertAVL(BSTNode*& b, KeyType e, int& taller)
/*若在平衡的二叉排序树b中不存在和e有相同关键字的结点,则插入一个
  数据元素为e的新结点,并返回1,否则返回0。若因插入而使二叉排序树
  失去平衡,则作平衡旋转处理,布尔变量taller反映b长高与否*/
{
    if (b == NULL)         //原为空树,插入新结点,树“长高”,置taller为1
    {
        b = (BSTNode*)malloc(sizeof(BSTNode));
        b->key = e;
        b->lchild = b->rchild = NULL;
        b->bf = 0;
        taller = 1;
    }
    else
    {
        if (e == b->key)              //树中已存在和e有相同关键字的结点则不再插入
        {
            taller = 0;
            return 0;
        }
        if (e < b->key)               //应继续在*b的左子树中进行搜索
        {
            if ((InsertAVL(b->lchild, e, taller)) == 0) //未插入
                return 0;
            if (taller == 1)          //已插入到*b的左子树中且左子树“长高”
                LeftProcess(b, taller);
        }
        else                        //应继续在*b的右子树中进行搜索
        {
            if ((InsertAVL(b->rchild, e, taller)) == 0) //未插入
                return 0;
            if (taller == 1)          //已插入到b的右子树且右子树“长高”
                RightProcess(b, taller);
        }
    }
    return 1;
}
void DispBSTree(BSTNode* b) //以括号表示法输出AVL
{
    if (b != NULL)
    {
        printf("%d", b->key);
        if (b->lchild != NULL || b->rchild != NULL)
        {
            printf("(");
            DispBSTree(b->lchild);
            if (b->rchild != NULL) printf(",");
            DispBSTree(b->rchild);
            printf(")");
        }
    }
}
void LeftProcess1(BSTNode*& p, int& taller)  //在删除结点时进行左处理
{
    BSTNode* p1, * p2;
    if (p->bf == 1)
    {
        p->bf = 0;
        taller = 1;
    }
    else if (p->bf == 0)
    {
        p->bf = -1;
        taller = 0;
    }
    else        //p->bf=-1
    {
        p1 = p->rchild;
        if (p1->bf == 0)          //需作RR调整
        {
            p->rchild = p1->lchild;
            p1->lchild = p;
            p1->bf = 1;
            p->bf = -1;
            p = p1;
            taller = 0;
        }
        else if (p1->bf == -1)    //需作RR调整
        {
            p->rchild = p1->lchild;
            p1->lchild = p;
            p->bf = p1->bf = 0;
            p = p1;
            taller = 1;
        }
        else                    //需作RL调整
        {
            p2 = p1->lchild;
            p1->lchild = p2->rchild;
            p2->rchild = p1;
            p->rchild = p2->lchild;
            p2->lchild = p;
            if (p2->bf == 0)
            {
                p->bf = 0;
                p1->bf = 0;
            }
            else if (p2->bf == -1)
            {
                p->bf = 1;
                p1->bf = 0;
            }
            else
            {
                p->bf = 0;
                p1->bf = -1;
            }
            p2->bf = 0;
            p = p2;
            taller = 1;
        }
    }
}
void RightProcess1(BSTNode*& p, int& taller) //在删除结点时进行右处理
{
    BSTNode* p1, * p2;
    if (p->bf == -1)
    {
        p->bf = 0;
        taller = -1;
    }
    else if (p->bf == 0)
    {
        p->bf = 1;
        taller = 0;
    }
    else        //p->bf=1
    {
        p1 = p->lchild;
        if (p1->bf == 0)          //需作LL调整
        {
            p->lchild = p1->rchild;
            p1->rchild = p;
            p1->bf = -1;
            p->bf = 1;
            p = p1;
            taller = 0;
        }
        else if (p1->bf == 1)     //需作LL调整
        {
            p->lchild = p1->rchild;
            p1->rchild = p;
            p->bf = p1->bf = 0;
            p = p1;
            taller = 1;
        }
        else                    //需作LR调整
        {
            p2 = p1->rchild;
            p1->rchild = p2->lchild;
            p2->lchild = p1;
            p->lchild = p2->rchild;
            p2->rchild = p;
            if (p2->bf == 0)
            {
                p->bf = 0;
                p1->bf = 0;
            }
            else if (p2->bf == 1)
            {
                p->bf = -1;
                p1->bf = 0;
            }
            else
            {
                p->bf = 0;
                p1->bf = 1;
            }
            p2->bf = 0;
            p = p2;
            taller = 1;
        }
    }
}
void Delete2(BSTNode* q, BSTNode*& r, int& taller)
//由DeleteAVL()调用,用于处理被删结点左右子树均不空的情况
{
    if (r->rchild == NULL)
    {
        q->key = r->key;
        q = r;
        r = r->lchild;
        free(q);
        taller = 1;
    }
    else
    {
        Delete2(q, r->rchild, taller);
        if (taller == 1)
            RightProcess1(r, taller);
    }
}
int DeleteAVL(BSTNode*& p, KeyType x, int& taller) //在AVL树p中删除关键字为x的结点
{
    int k;
    BSTNode* q;
    if (p == NULL)
        return 0;
    else if (x < p->key)
    {
        k = DeleteAVL(p->lchild, x, taller);
        if (taller == 1)
            LeftProcess1(p, taller);
        return k;
    }
    else if (x > p->key)
    {
        k = DeleteAVL(p->rchild, x, taller);
        if (taller == 1)
            RightProcess1(p, taller);
        return k;
    }
    else            //找到了关键字为x的结点,由p指向它
    {
        q = p;
        if (p->rchild == NULL)        //被删结点右子树为空
        {
            p = p->lchild;
            free(q);
            taller = 1;
        }
        else if (p->lchild == NULL)   //被删结点左子树为空
        {
            p = p->rchild;
            free(q);
            taller = 1;
        }
        else                        //被删结点左右子树均不空
        {
            Delete2(q, q->lchild, taller);
            if (taller == 1)
                LeftProcess1(q, taller);
            p = q;
        }
        return 1;
    }
}

int main()
{
    BSTNode* b = NULL;
    int i, j, k;
    KeyType a[] = { 16,3,7,11,9,26,18,14,15 }, n = 9;
    printf(" 创建一棵AVL树:\n");
    for (i = 0; i < n; i++)
    {
        printf("   第%d步,插入%d元素:", i + 1, a[i]);
        InsertAVL(b, a[i], j);
        DispBSTree(b);
        printf("\n");
    }
    printf("   AVL:");
    DispBSTree(b);
    printf("\n");



    printf(" 删除结点:\n");
    k = 11;
    printf("   删除结点%d:", k);
    DeleteAVL(b, k, j);
    printf("   AVL:");
    DispBSTree(b);
    printf("\n");
    k = 9;
    printf("   删除结点%d:", k);
    DeleteAVL(b, k, j);
    printf("   AVL:");
    DispBSTree(b);
    printf("\n");
    k = 15;
    printf("   删除结点%d:", k);
    DeleteAVL(b, k, j);
    printf("   AVL:");
    DispBSTree(b);
    printf("\n\n");
    return 0;
}

示意图：

创建一棵AVL树
第1步，插入16元素16
第2步，插入3元素16（3）
第3步，插入7元素7（3，16）
第4步，插入11元素7（3，16（11））
第5步，插入9元素7（3，11（9，16））
第6步，插入26元素11（7（3，9），16（，26））
第7步，插入18元素11（7（3，9），18（16，26））
第8步，插入14元素11（7（3，9），18（16（14），26））
第9步，插入15元素11（7（3，9），18（15（14，16），26））
AVL11（7（3，9），18（15（14，16），26））

删除结点
删除结点11：AVL9（7（3），18（1504，16），26））
删除结点9：AVL15（7（3，14），18（16，26））
删除结点15：AVL.14（7（3），18（16，26））

二叉排序树

算法库

#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
typedef int KeyType;     //定义关键字类型
typedef char InfoType;
typedef struct node                 //记录类型
{
    KeyType key;                    //关键字项
    InfoType data;                 //其他数据域
    struct node* lchild, * rchild;  //左右孩子指针
}BSTNode;
int path[MaxSize];      //全局变量,用于存放路径
void DispBST(BSTNode* b);    //函数说明
int InsertBST(BSTNode*& p, KeyType k) //在以*p为根节点的BST中插入一个关键字为k的节点
{
    if (p == NULL)      //原树为空, 新插入的记录为根节点
    {
        p = (BSTNode*)malloc(sizeof(BSTNode));
        p->key = k; p->lchild = p->rchild = NULL;
        return 1;
    }
    else if (k == p->key)
        return 0;
    else if (k < p->key)
        return InsertBST(p->lchild, k); //插入到*p的左子树中
    else
        return InsertBST(p->rchild, k);  //插入到*p的右子树中
}
BSTNode* CreatBST(KeyType A[], int n)
//由数组A中的关键字建立一棵二叉排序树
{
    BSTNode* bt = NULL;            //初始时bt为空树
    int i = 0;
    while (i < n)
    {
        if (InsertBST(bt, A[i]) == 1)  //将A[i]插入二叉排序树T中
        {
            printf("    第%d步,插入%d:", i + 1, A[i]);
            DispBST(bt); printf("\n");
            i++;
        }
    }
    return bt;                  //返回建立的二叉排序树的根指针
}
void Delete1(BSTNode* p, BSTNode*& r)
//当被删*p节点有左右子树时的删除过程
{
    BSTNode* q;
    if (r->rchild != NULL)
        Delete1(p, r->rchild); //递归找最右下节点
    else      //找到了最右下节点*r
    {
        p->key = r->key;   //将*r的关键字值赋给*p
        q = r;
        r = r->lchild;   //将*r的双亲节点的右孩子节点改为*r的左孩子节点
        free(q);    //释放原*r的空间
    }
}
void Delete(BSTNode*& p)
//从二叉排序树中删除*p节点
{
    BSTNode* q;
    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
        Delete1(p, p->lchild); //*p节点既有左子树又有右子树的情况
}
int DeleteBST(BSTNode*& bt, KeyType k)
//在bt中删除关键字为k的节点
{
    if (bt == NULL) return 0;  //空树删除失败
    else
    {
        if (k < bt->key)
            return DeleteBST(bt->lchild, k);  //递归在左子树中删除关键字为k的节点
        else if (k > bt->key)
            return DeleteBST(bt->rchild, k);  //递归在右子树中删除关键字为k的节点
        else         //k=bt->key的情况
        {
            Delete(bt);  //调用Delete(bt)函数删除*bt节点
            return 1;
        }
    }
}
void SearchBST1(BSTNode* bt, KeyType k, KeyType path[], int i)
//以非递归方式输出从根节点到查找到的节点的路径
{
    int j;
    if (bt == NULL)
        return;
    else if (k == bt->key) //找到了节点
    {
        path[i + 1] = bt->key; //输出其路径
        for (j = 0; j <= i + 1; j++)
            printf("%3d", path[j]);
        printf("\n");
    }
    else
    {
        path[i + 1] = bt->key;
        if (k < bt->key)
            SearchBST1(bt->lchild, k, path, i + 1);  //在左子树中递归查找
        else
            SearchBST1(bt->rchild, k, path, i + 1);  //在右子树中递归查找
    }
}
int SearchBST2(BSTNode* bt, KeyType k)
//以递归方式输出从根节点到查找到的节点的路径
{
    if (bt == NULL)
        return 0;
    else if (k == bt->key)
    {
        printf("%3d", bt->key);
        return 1;
    }
    else if (k < bt->key)
        SearchBST2(bt->lchild, k);  //在左子树中递归查找
    else
        SearchBST2(bt->rchild, k);  //在右子树中递归查找
    printf("%3d", bt->key);
}

void DispBST(BSTNode* bt)
//以括号表示法输出二叉排序树bt
{
    if (bt != NULL)
    {
        printf("%d", bt->key);
        if (bt->lchild != NULL || bt->rchild != NULL)
        {
            printf("(");
            DispBST(bt->lchild);
            if (bt->rchild != NULL)
                printf(",");
            DispBST(bt->rchild);
            printf(")");
        }
    }
}
KeyType predt = -32767; //predt为全局变量,保存当前节点中序前趋的值,初值为-∞
int JudgeBST(BSTNode* bt) //判断bt是否为BST
{
    int b1, b2;
    if (bt == NULL)
        return 1;
    else
    {
        b1 = JudgeBST(bt->lchild);
        if (b1 == 0 || predt >= bt->key)
            return 0;
        predt = bt->key;
        b2 = JudgeBST(bt->rchild);
        return b2;
    }
}
int main()
{
    BSTNode* bt;
    KeyType k = 6;
    int a[] = { 4,9,0,1,8,6,3,5,2,7 }, n = 10;
    printf("(1)创建一棵BST树:");
    printf("\n");
    bt = CreatBST(a, n);
    printf("    括号表示BST:"); DispBST(bt); printf("\n");
    printf("(2)判断：bt%s\n", (JudgeBST(bt) ? "是一棵BST" : "不是一棵BST"));
    printf("(3)a.查找%d关键字(递归,顺序):", k); SearchBST1(bt, k, path, -1);
    printf("   b.查找%d关键字(非递归,逆序):", k); SearchBST2(bt, k);
    printf("\n(4)删除并输出操作:\n");
    printf("   原BST:"); DispBST(bt); printf("\n");
    printf("   删除节点4:");
    DeleteBST(bt, 4);
    DispBST(bt); printf("\n");
    printf("   删除节点5:");
    DeleteBST(bt, 5);
    DispBST(bt);
    printf("\n");
    return 0;
}

示意图：

运行即可