【数据结构】实现平衡二叉树的各种算法(插入，删除，查找，输出)

前言

首先，博主写这篇文章出于一个目的，就是可以给真心想弄清平衡二叉树的同学一个引导，为什么这样说呢？首先，当今市面上关于数据结构的书讲的都是比较浅显，像平衡二叉树这个知识点一般就只讲了插入算法，极少书籍对平衡二叉树的删除算法进行讲解，所以对于很多朋友来说都很烦恼；其次，网上的资料关于平衡二叉树的算法讲解的也比较少（或者说是很多算法都是有错误的，至少我还没有找到一篇正确的关于平衡二叉树删除算法的代码）。那么，博主下面就给大家讲解平衡二叉树的各种算法，有什么错误也希望大家指出来。

一、定义

我们都知道，一棵二叉查找树要达到性能最优，树形应该是层数越少越好。最理想的二叉树是高度达到最小的二叉树，包括满二叉树和完全二叉树。这一类二叉树在插入或者删除之后维持高度最毒最小的代价较大，故可以使用一种折中方案，即平衡二叉树。

平衡二叉查找树（Balanced Binary Sort Tree，BBST）简称平衡二叉树。平衡二叉树有很多种，其中最著名的是由前苏联数学家Adelse-Velskil 和 Landis 在1962年提出的高度平衡的二叉树，根据科学家的英文名字首字母故平衡二叉树也可简称为AVL树。

平衡二叉树或者是棵空树，或者是具有下列性质的二叉查找树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差的绝对值不超过1。故将二叉树结点的平衡因子（Balance Factor）定义为该结点的左子树的高度减去它的右子树的高度，则平衡二叉树上所有结点的平衡因子只可能为-1,1。只要二叉树上有一个结点的平衡因子的绝对值大于1，那么这棵平衡二叉树就失去了平衡。

二、存储结构

typedef int RcdType;  
typedef int Status;  //Status就是int

/*平衡二叉树结构体*/
typedef struct BBSTNode{
    RcdType data;      //我自己定义RcdType就是int类型
    int bf;            //平衡因子
    BBSTNode *lchild,*rchild;   //左右孩子
}BBSTNode,*BBSTree;</span>

三、接口

(1)根据输入字符串创建一棵平衡二叉树
BBSTree MakeBBSTree();
(2)平衡二叉树插入元素操作
Status InsertAVL(BBSTree &T,RcdType e,Status &taller);
(3)平衡二叉树删除元素操作
Status DeleteAVL(BBSTree &t,Status &shorter);
(4)平衡二叉树查找元素操作
BBSTree SearchAVL(BBSTree T,RcdType e);
(5)求平衡二叉树的深度
int BBSTreeDepth(BBSTree T);
(6)交换所有结点的左右子树
void ExchangeSubTree(BBSTree &T)
(7)递归先序遍历
Status PreOrder_RecTraverse(BBSTree T)；
(8)递归中序遍历
Status InOrder_RecTraverse(BBSTree T);
(9)递归后序遍历
Status LastOrder_RecTraverse(BBSTree T);
(10)非递归先序遍历
void PreOrderTraverse_I(BBSTree T);
(11)非递归中序遍历
void InOrderTraverse_I(BBSTree T);
(12)非递归后序遍历
void LastOrderTraverse_I(BBSTree T);
(13)层次遍历输出二叉树
void LevelOrederTraverse_Print(BBSTree T);
(14)括号表示法输出二叉树
void BraNotationPrint(BBSTree T);

四、接口的实现及其算法

（1）根据输入字符串创建一棵平衡二叉树

实现功能：根据输入的数字序列创建生成一棵平衡二叉树。例如输入(1 2 3 4 5 6 7回车)，然后就会生成一个由1 2 3 4 5 6 7组成的平衡二叉树。主要思想是将输入的序列用存放到一个动态数组（或者说是链表），通过GetInputToArray()函数来将输入的序列转换为数组，然后逐个读取数组中的元素，调用Status InsertAVL(BBSTree &T,Status &taller)函数逐个插入到T中。

初始条件：无

返回值：返回一棵平衡二叉树

调用函数： Array GetInputToArray()；/*获取输入存到数组a*/

Status InsertAVL(BBSTree &T,Status &taller)； /*平衡二叉树的插入操作*/

/*根据输入的字符串建一棵平衡二叉树*/
BBSTree MakeBBSTree( ){
    int i=0;
    Status taller = TRUE;  
    BBSTree T = NULL;
    Array a;
    a = <strong>GetInputToArray();</strong>
    while(a!=NULL){
        taller = TRUE;
        <strong>InsertAVL(T,a->data,taller);</strong>
        a = a->next;
    }
    return T;
}

<span style="font-size:12px;">/*获取输入存到数组a*/
Array GetInputToArray(){
    Array head,p,q;
    char k;
    head = p = q = NULL;
    int m;
    scanf("%d",&m);  //输入数字，赋给m
    p = (ArrayNode*)malloc(sizeof(ArrayNode)); //动态申请内存
    head = p;  //头指针指向第一个元素
    p->data = m;
    k = getchar();  //读取输入完数字的空格键或者是回车键
    while(k!='\n'){    //当按回车键时，输入完成
        scanf("%d",&m);
        q = (ArrayNode*)malloc(sizeof(ArrayNode));
        q->data = m;
        p->next = q;
        p = p->next;
        k = getchar();
    }
    if(p!=NULL){
        p->next = NULL;        //p->next置空，避免指向不相关内存地址
    }
    return head;  //返回存放数据的头指针 
}</span>

（2）平衡二叉树插入元素操作

实现功能：根据输入的数据插入到平衡二叉树T中，使之形成新的平衡二叉树。

思想：(1) 若是空树，则插入结点为根节点，树的高度增加1

(2) 若待插入结点和根节点相等，无需插入

(3) 若插入结点小于根节点，且在左子树上也不存在相等的结点，则在左子树上插入，且插入后的左子树高度增加1，则分情况处理：

1) 原根节点的平衡因子为-1(右子树高于左子树)，则其平衡因子改为0，树的高度不变；

2) 原根节点的平衡因子为0(左右子树高度相等)，则其平衡因子修改为1，树的高度增加1；

3) 原根节点的平衡因子为1(左子树高于右子树)：若左子树根节点的平衡因子为1，则属于LL型，需要进行右旋平衡调整，并在调整后将根节点及其右孩子的平衡因子更改为0，树的高度不变；若左子树根节点的平衡因子为-1，则属于LR型，需要进行先向左，后向右的双向旋转平衡调整，并在调整后修改根节点和其左右孩子的平衡因子，树的高度不变。

(4) 若插入结点大于根节点，且在右子树上不存在相等的结点，则在右子树插入，且当插入之后的右子树高度加1时，则分情况处理：

1) 原根结点的平衡因子是1(左子树高于右子树)，则其平衡因子修改为0，树的高度不变；

2) 原根节点的平衡因子为0(左右子树高度相等)，则其平衡因子修改为-1，树的高度增加1；

3) 原根节点的平衡因子为-1(右子树高于左子树)：若右子树根节点的平衡因子为1，则属于RR型，需要进行两次处理，第一次先进行右旋平衡调整，再左旋平衡调整，并且在旋转处理之后，修改根节点和其左右子树根节点的平衡因子，树的高度不变；若右子树根节点的平衡因子为-1，则属于RL型，需要进行一次左旋处理，并在左旋之后，更新根节点和其左右孩子的平衡因子，树的高度不变。

初始条件：平衡二叉树T，插入元素e，标志标量taller

返回值：插入成功返回TRUE，失败返回FALSE

调用函数：void LeftBalance(BBSTree &T); /*左平衡操作*/

void RightBalance(BBSTree &T)； /*右平衡操作*/

/*平衡二叉树的插入操作*/
Status InsertAVL(BBSTree &T,Status &taller){  //taller就是判断树的高度是否增加，是taller=TRUE，否taller=FALSE
    if(NULL==T){
        T = (BBSTree)malloc(sizeof(BBSTNode));
        T->data = e;
        T->bf = EH; 
        T->lchild = NULL; 
        T->rchild = NULL;
    }else if(e==T->data){ //书中已存在和e相等的结点 
        taller = FALSE; return FALSE;        
    }else if(e<T->data){  //插入到左边
        if(FALSE==InsertAVL(T->lchild,e,taller)) return FALSE;
        if(TRUE==taller){
            switch(T->bf){
                case LH: <strong>LeftBalance(T)</strong>; taller = FALSE; break;
                case EH: T->bf = LH; taller = TRUE; break;
                case RH: T->bf = EH; taller = FALSE; break;
            }
        }
    }else{  //插入到右边
        if(FALSE==InsertAVL(T->rchild,taller)) return FALSE;
        if(TRUE==taller){
            switch(T->bf){
                case LH: T->bf = EH; taller = FALSE; break;
                case EH: T->bf = RH; taller = TRUE; break;
                case RH: <strong>RightBalance(T)</strong>; taller = FALSE; break;
            }
        }
    }
    return TRUE;
}

/*左平衡处理操作*/
void LeftBalance(BBSTree &T){
    BBSTree lc,rd;
    lc = T->lchild;
    switch(lc->bf){
        case LH:
            T->bf = lc->bf = EH; R_Rotate(T); break;
        case RH:
            rd = lc->rchild;
            switch(rd->bf){
                case LH: T->bf = RH; lc->bf = EH; break;
                case EH: T->bf = lc->bf = EH; break;
                case RH: T->bf = EH; lc->bf = LH; break;                
            }
            rd->bf = EH;
            L_Rotate(T->lchild);
            R_Rotate(T);
            break;              
    }
}

/*右平衡处理操作*/
void RightBalance(BBSTree &T){
    BBSTree rd,lc;
    rd=T->rchild;
    switch(rd->bf)
    {
        case RH:
            T->bf=rd->bf=EH; L_Rotate(T); break;
        case LH:
            lc=rd->lchild;
            switch(lc->bf){
                case RH:T->bf=LH;rd->bf=EH;break;
                case EH:T->bf=rd->bf=EH;break;
                case LH:T->bf=EH;rd->bf=RH;break;
            }
            lc->bf=EH;
            R_Rotate(T->rchild);
            L_Rotate(T);
            break;
    }  
}

（3）平衡二叉树删除元素操作
实现功能：根据输入的数据从平衡二叉树T删除，使之形成新的平衡二叉树。

思想：其实删除最主要是一下几点。

(1) 你需要知道的是，删除的分类。

第一类，被删结点是叶子结点，直接把它删除，但需要注意的是，删除之后对于该结点的双亲结点来说，它的高度是降低了。

第二类，被删结点具有一个孩子分支，这时也是直接把它删除，然后把它的孩子替代它，但对于双亲结点来说，它的高度也是降低了。

第三类，是最复杂的，被删结点的左右子树都不为空，这时，我们通常做法就是将这个结点的前驱结点的值替代这个结点，然后删除掉前驱结点。而每一个结点的前驱结点都是该结点左子树上最左的孩子(这点一定要理解，这对于任何结点来说都是成立的)。明白了这点，就可以把这类的删除问题转化为第一类或者是第二类，因为前驱结点已经没有左孩子了，所以它要不为叶子结点，要不为只有右孩子的结点。

(2) 删除完之后，你需要对失去平衡之后的树进行调整。

第一类，被删结点是双亲结点的左孩子，那么，我们删除之后就要判断删除前其双亲结点的平衡因子，无非有三种：EH(0),LH(1),RH(-1)。

a. 看EH类型，如图1，这时，我们删掉结点之后，只需调整双亲的平衡因子为RH(-1)，树的高度不变。

b. 看LH类型，如图2，这时，我们删除结点之后，只需调整双亲的平衡因子为EH( 0 )，树的高度变矮。

c. 看RH类型，这时又分为三种类型：

（i）双亲结点的右孩子的bf为EH（0），如图3a，这时，我们删除之后，只需要对双亲结点进行左旋一次即可，然后，调整根节点的平衡因子为LH( 1 )，根节点的左孩子的平衡因子为RH（-1），树高不变，建议大家画图看看。

（ii）双亲结点的右孩子的bf为RH（-1），如图3b，这时，我们删除之后，同样只对双亲结点进行一次左旋操作，然后，调整根节点的平衡因子为EH（0），根节点的左右孩子的平衡因子因为EH（0），树变矮了。

（iii）双亲结点的右孩子的bf为LH（1），如图3c，这时，我们删除之后，只需要进行右平衡操作即可，树变矮了。

第二类，被删结点是双亲结点的右孩子，类似第一类，删除前其双亲结点的平衡因子也是有三种，下面就不画图了，大家可以参照第一类自己画图

a. 看EH类型，这时，我们删掉结点之后，只需调整双亲的平衡因子为LH（1），树的高度不变。

b. 看RH类型，这时，我们删除结点之后，只需调整双亲的平衡因子为EH( 0 )，树的高度变矮。

c. 看LH类型，这时又分为三种类型：

（i）双亲结点的左孩子的bf为EH（0），这时，我们删除之后，只需要对双亲结点进行右旋一次即可，然后，调整根节点的平衡因子为RH( -1 )，根节点的右孩子的平衡因子为LH（1），树高不变，建议大家画图看看。

（ii）双亲结点的左孩子的bf为LH（1），这时，我们删除之后，同样只对双亲结点进行一次右旋操作，然后，调整根节点的平衡因子为EH（0），根节点的左右孩子的平衡因子因为EH（0），树变矮了。

（iii）双亲结点的左孩子的bf为RH（-1），这时，我们删除之后，只需要进行左平衡操作即可，树变矮了。

初始条件：平衡二叉树T，插入元素e，标志标量taller

返回值：插入成功返回TRUE，失败返回FALSE

调用函数：void LeftBalance(BBSTree &T); /*左平衡操作*/

void RightBalance(BBSTree &T)； /*右平衡操作*/

void L_Rotate(BBSTree &p)； /*左旋调整*/

void R_Rotate(BBSTree &p)； /*右旋调整*/

/*平衡二叉树的删除操作*/ (注意到蓝色的两段代码是相同的)
Status DeleteAVL(BBSTree &T,Status &shorter){         
    if(NULL==T) return FALSE;
    else if(e==T->data){
        BBSTNode *q = NULL;
        if(T->lchild==NULL){  //当孩子左结点为空的时候
            q = T;
            T = T->rchild;
            free(q);
            shorter = TRUE;
        }else if(T->rchild==NULL){  //当孩子的右结点为空的时候
            q = T;
            T = T->lchild;
            free(q);
            shorter = TRUE; 
        } else{      //当结点的左右孩子不为空的时候
            q = T->lchild;
            while(q->rchild){
                q = q->rchild;   //找到前驱结点
            }
            T->data = q->data;   //用前驱结点的值代替要删除的结点的值
            DeleteAVL(T->lchild,q->data,shorter);  //删除前驱结点
            <span style="color:#3333FF;">if(shorter==TRUE){    //进行删除后的平衡调整，因为寻找前驱结点都是向左找，所以此处的平衡调整代码跟左孩子的平衡调整代码是一样的
                switch(T->bf){
                    case EH:
                        T->bf = RH;
                        shorter = FALSE;
                        break;
                    case LH:
                        T->bf = EH;
                        shorter = TRUE;
                        break;
                    case RH:
                        BBSTree rchild = T->rchild;
                        switch(rchild->bf){
                            case EH:
                                L_Rotate(T);
                                T->lchild->bf = RH;
                                T->bf = LH;
                                shorter = FALSE;
                                break;
                            case RH:
                                L_Rotate(T);
                                T->bf = EH;
                                T->lchild->bf = EH;
                                shorter = TRUE;
                                break;
                            case LH:
                                RightBalance(T);
                                shorter = TRUE;
                                break;
                        }
                        break;
                }
            }
        }</span>
    }else if(e<T->data){   //在根节点的左边找
        if(!DeleteAVL(T->lchild,shorter)){
            return FALSE;   //删除操作
        }
        <span style="color:#3333FF;">if(shorter==TRUE){   //平衡操作
            switch(T->bf){
                case EH:
                    T->bf = RH;
                    shorter = FALSE;
                    break;
                case LH:
                    T->bf = EH;
                    shorter = TRUE;
                    break;
                case RH:
                    BBSTree rchild = T->rchild;
                    switch(rchild->bf){
                        case EH:
                            L_Rotate(T);
                            T->bf = LH;
                            T->lchild->bf = RH;
                            shorter = FALSE;
                            break;
                        case RH:
                            L_Rotate(T);
                            T->bf = EH;
                            T->lchild->bf = EH;
                            shorter = TRUE;
                            break;
                        case LH:
                            RightBalance(T);
                            shorter = TRUE;
                            break;
                    }
                    break;
            }
        }</span>
    }else if(e>T->data){  //在根节点的右边找
        if(!DeleteAVL(T->rchild,shorter)){
            return FALSE;        //删除操作
        }
        if(shorter==TRUE){    //平衡操作
            switch(T->bf){
                case EH:
                    T->bf = LH;
                    shorter = FALSE;
                    break;
                case RH:
                    T->bf = EH;
                    shorter = TRUE;
                    break;
                case LH:
                    BBSTree lchild = T->lchild;
                    switch(lchild->bf){
                        case EH:
                            R_Rotate(T);
                            T->bf = RH;
                            T->rchild->bf = LH;
                            shorter = FALSE;
                            break;
                        case LH:
                            R_Rotate(T);
                            T->bf = EH;
                            T->lchild->bf = EH;
                            shorter = TRUE;
                            break;
                        case RH:
                            LeftBalance(T);
                            break;
                    }
                    break;
                break;
            }
        }

    }
    return TRUE;
}

/*左旋调整*/
void L_Rotate(BBSTree &p){
    BBSTree rc = p->rchild;
    p->rchild = rc->lchild;
    rc->lchild = p;
    p = rc;
}

/*右旋调整*/
void R_Rotate(BBSTree &p){
    BBSTree lc = p->lchild;
    p->lchild = lc->rchild;
    lc->rchild = p;
    p = lc;
}

【数据结构】实现平衡二叉树的各种算法(插入，删除，查找，输出)

猜你在找的数据结构相关文章