数据结构之平衡二叉树详解-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构之平衡二叉树详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

平衡二叉树的定义：

平衡二叉树（balanced binary tree)

又称AVL树（Adelson-Velskii and Landis)

一棵平衡二叉树或者是空树，或者是具有下列性质的二叉排序树：

１，左子树与右子树的高度之差的绝对值小于等于１；

２，左子树和右子树也是平衡二叉排序树．

为了方便起见，给每个结点附加一个数字，给出该结点左子树与右子树的高度差．这个数字称为结点的平衡因子（ＢＦ）．

平衡因子　＝　结点左子树的高度　－　结点右子树的高度

根据平衡二叉树的定义，平衡二叉树上所有结点的平衡因子只能是-1,0,或1.

例：

平衡二叉树,数据结构和算法,数据结构,算法,图论

对于一棵有n个结点的AVL树，其高度保持在O(log2^n)数量级

失衡二叉排序树的分析与调整

当我们在一个平衡二叉排序树上插入一个结点时，有可能导致失衡，不再是一个平衡二叉排序树，即出现平衡因子绝对值大于１的结点．

平衡二叉树,数据结构和算法,数据结构,算法,图论

如果在一棵ＡＶＬ树中插入一个新结点后造成失衡，则必须重新调整树的结构，使之恢复平衡

平衡调整的四种类型：

平衡二叉树,数据结构和算法,数据结构,算法,图论

具体的调整为：

平衡二叉树,数据结构和算法,数据结构,算法,图论

调整原则为：１）降低高度　２）保持二叉排序树的性质

规律：按照二叉排序树的性质，挑选３个值的中间值作为调整后的根结点，最小值为根结点的左孩子，最大值为根结点的右孩子．

例：ＬＬ型

平衡二叉树,数据结构和算法,数据结构,算法,图论

例：ＲＬ型

平衡二叉树,数据结构和算法,数据结构,算法,图论

ＲＲ型和ＬＲ型和上面类似，就不多介绍了，总之，一个总的原则，就是调整后必须保证１）降低高度　２）保持二叉排序树的性质

还是那句话，只要知道调整类型，就可以确定Ａ，Ｂ，Ｃ三个顶点的位置，中间值为根结点，最大值为右孩子，最小值为左孩子，确定好后，别的结点就很容易根据二叉排序树的特点找到各自的位置，网上看了很多左旋，右旋，左右旋，头都晕．只要知道这个规律，不用管什么旋，也不用死记硬背还怕忘．随时碰到随时都可以马上上手．

接下来用代码来实现一个平衡二叉树的建立：

例题：输入关键字序列(16,3,7,11,9,26,18,14,15),创建一个平衡二叉树

第一个方法是给结点加了一个parent域，方便查找，不过感觉挺麻烦的，每次调整都要给parent域赋值，不过这个代码在有多个失衡点时会挑选最小代价树的失衡点，不管失衡点是不是根结点都是通用的文章来源地址https://www.toymoban.com/news/detail-779250.html

#include <stdio.h>
#include <stdlib.h>
#define MAXINT 10000
#define MAXSIZE 10
typedef struct BBTnode{
    int data;//这里为了方便，直接用int,没有用结构体．
    int balance;//平衡因子
    struct BBTnode* lchild;
    struct BBTnode* rchild;
    struct BBTnode* parent;
}BBTnode,*BBTree;
BBTree MinBalance;//最小失衡结点地址
int k = 0;
int i = 0;
BBTree SearchBBT(BBTree T, int m, char* arr)//计算从某点出发，到指定数字的路径
{
    if(!T || T->data == m)
    {
        return T;
    }
    else if(m < T->data)
    {
        arr[k++] = 'L';
        return SearchBBT(T->lchild, m, arr);
    }
    else
    {
        arr[k++] = 'R';
        return SearchBBT(T->rchild, m, arr);
    }

}

int CountNodes(BBTree T)//计算树中的结点数，比较失衡结点树的大小，选择较小的树（当不止一个失衡点时）
{
    if(!T)
    {
        return 0;
    }
    return CountNodes(T->lchild) + CountNodes(T->rchild) + 1;
}

int DepthBBT(BBTree T)//计算平衡二叉树的深度
{
    int m, n;
    if(!T)
    {
        return 0;
    }
    else
    {
        m = DepthBBT(T->lchild) + 1;//左边的深度
        n = DepthBBT(T->rchild) + 1;//右边的深度
    }
    if(m > n)return m;//取较大值
    else return n;
}


void OrderBBT(BBTree* T, BBTree Unbalance[MAXSIZE])//中序遍历二叉排序树,更新各结点平衡因子，把所有失衡点存储起来
{
    if(*T == NULL)return;
    else
    {
        OrderBBT(&(*T)->lchild,Unbalance);
        (*T)->balance = abs(DepthBBT((*T)->lchild) - DepthBBT((*T)->rchild));//计算该结点平衡因子，左边深度－右边深度再取绝对值
        if((*T)->balance>1)
        {
            Unbalance[i++] = *T;
        }
        OrderBBT(&(*T)->rchild,Unbalance);
    }
}

void AddBBT(BBTree* T, int m, BBTree parent)//二叉排序树的递归添加元素
{
    if(!(*T))
    {
        *T = malloc(sizeof(BBTnode));
        (*T)->data = m;
        (*T)->lchild = NULL;
        (*T)->rchild = NULL;
        (*T)->balance = 0;
        (*T)->parent = parent;
    }
    else if(m < (*T)->data)
    {
        AddBBT(&(*T)->lchild, m, *T);
    }
    else
    {
        AddBBT(&(*T)->rchild, m, *T);

    }
}


void creatBBT(BBTree* T)//创建平衡二叉排序树，实际上就是给一个空树添加元素
{
    int input = 1;
    BBTree A,B,C;//定义图示中表示的三个顶点
    while(input)
    {
        printf("请依次输入数字序列，输入完毕以0结束:>");
        scanf("%d",&input);
        if(input == 0)break;
        AddBBT(T, input,*T);
        MinBalance = 0;//重置最小平衡因子为空
        int temp = MAXINT;
        int j;
        BBTree Unbalance[MAXSIZE] = {0};//定义一个失衡结点数组，用来存放当前树中存在的失衡结点
        i = 0;//重置数组Unbalance的下标为0开始
        OrderBBT(T,Unbalance);//更新平衡因子，得到平衡因子数组Unbalance
        for(j = 0; j < MAXSIZE; j++)//从数组Unbalance找出最小失衡因子，并返回该地址到MinBalance
        {
            if(!Unbalance[j])break;
            if(CountNodes(Unbalance[j]) < temp)
            {
                temp = CountNodes(Unbalance[j]);
                MinBalance = Unbalance[j];
            }
        }
        char ChoiceType[MAXSIZE] = {0};//选择调整类型的数组（ＬＬ，ＲＲ．ＬＲ，ＲＬ）
        k = 0;//重置SearchBBT里的k变量
        SearchBBT(MinBalance, input, ChoiceType);//得到从失衡点出发到添加结点间的路径
        if(ChoiceType[0] == 'L' && ChoiceType[1] == 'L')//ＬＬ型调整
        {
            A = MinBalance;
            B = MinBalance->lchild;
            C = MinBalance->lchild->lchild;
            if(A->parent)//如果这个失衡点不是根结点
            {
                if(A->data < A->parent->data)A->parent->lchild = B;
                else A->parent->rchild = B;
            }
            else *T = B;

            A->lchild = B->rchild;
            if(B->rchild)B->rchild->parent = A;
            B->rchild = A;
            B->parent = A->parent;
            A->parent = B;

        }
        else if(ChoiceType[0] == 'R' && ChoiceType[1] == 'R')//ＲＲ型调整
        {
            A = MinBalance;
            B = MinBalance->rchild;
            C = MinBalance->rchild->rchild;
            if(A->parent)//如果这个失衡点不是根结点
            {
                if(A->data < A->parent->data)A->parent->lchild = A->rchild;
                else A->parent->rchild = A->rchild;
            }
            else *T = B;//如果是根结点，那么根结点变成调整后的根结点
            A->rchild = B->lchild;
            if(B->lchild)B->lchild->parent = A;
            B->lchild = A;
            B->parent = A->parent;
            A->parent = B;



        }
        else if(ChoiceType[0] == 'L' && ChoiceType[1] == 'R')//ＬＲ型调整
        {
            A = MinBalance;
            B = MinBalance->lchild;
            C = MinBalance->lchild->rchild;
            if(A->parent)//如果这个失衡点不是根结点
            {
                if(A->data < A->parent->data)A->parent->lchild = C;
                else A->parent->rchild = C;
            }
            else *T = C;
            B->rchild = C->lchild;
            if(C->lchild)C->lchild->parent =B;
            A->lchild = C->rchild;
            if(C->rchild)C->rchild->parent = A;
            C->rchild = A;
            C->lchild = B;
            C->parent = A->parent;
            A->parent = C;
            B->parent = C;

        }
        else if(ChoiceType[0] == 'R' && ChoiceType[1] == 'L')//ＲＬ型调整
        {
            A = MinBalance;
            B = MinBalance->rchild;
            C = MinBalance->rchild->lchild;
            if(A->parent)//如果这个失衡点不是根结点
            {
                if(A->data < A->parent->data)A->parent->lchild = C;
                else A->parent->rchild = C;
            }
            else *T = C;
            A->rchild = C->lchild;
            if(C->lchild)C->lchild->parent = A;
            B->lchild = C->rchild;
            if(C->rchild)C->rchild->parent = B;
            C->lchild = A;
            C->rchild = B;
            C->parent = A->parent;
            A->parent = C;
            B->parent = C;
        }
    }
    BBTree arr[MAXSIZE] = {0};//这个只为为了下面这个OrderBBT函数能运行，没有别的意义
    OrderBBT(T,arr);
}
void printBBT(BBTree T)//中序输出二叉排序树，得到的是一个递增数列
{
    if(T == NULL)return;
    else
    {
        printBBT(T->lchild);
        printf("%d号结点平衡因子为%d\n",T->data,T->balance);
        printBBT(T->rchild);
    }
}

int main()
{
    BBTree T = NULL;//定义二叉排序树Ｔ
    creatBBT(&T);//创建二叉排序树
    printBBT(T);//输出创建好的二叉排序树
    return 0;
}

到了这里，关于数据结构之平衡二叉树详解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！