c语言 手写平衡二叉树（一）

定义结构体

struct Person
{
//父节点
    struct Person* parent;
    //左子节点
    struct Person* lchild;
    //右子节点
    struct Person* rchild;
    int m;
};

struct ABLtree
{//保存根节点信息
    struct Person* root;
};

初始化根节点

struct ABLtree* init_tree()
{
//在堆区开辟一个ABLtree大小的空间
    struct ABLtree* tree = malloc(sizeof(struct ABLtree));
    //开辟失败返回NULL
    if (!tree)
    {
        return NULL;
    }
    //初始化根节点为NULL并返回
    tree->root = NULL;
    return tree;
}

添加节点

//比较函数，返回两者的差值
int compare(struct Person* p1, struct Person* p2)
{
    return ((p1->m) - (p2->m));
}
//添加节点函数，内部调用
void insertPerson(struct Person* tree, struct Person* data, int(*compare)(struct Person*, struct Person*))
{
//如果当前节点大于插入的节点
    if (compare(tree, data) > 0)
    {//if当前节点的左节点为空
        if (NULL==tree->lchild)
        {//把数据赋值给节点的左子节点
            tree->lchild = data;
            //把当前节点赋值给数据的父节点
            data->parent = tree;
            //返回
            return;
        }
        //不为空，则把数据的左子节点传入函数
        insertPerson(tree->lchild, data, compare);
    }
    else {
    //if当前节点的右节点为空
        if (NULL==tree->rchild)
        {
        //把数据赋值给节点的右子节点
            tree->rchild = data;
        //把当前节点赋值给数据的父节点
            data->parent = tree;
            //返回
            return;
        }
        //不为空，则把数据的右子节点传入函数
        insertPerson(tree->rchild, data, compare);
    }

}
//添加节点函数，外部调用
void initer(struct ABLtree* mytree, struct Person* data, int(*compare)(struct Person*, struct Person*))
{
//判断ABLtree是否NULL
    if (!tree)
    {
        return;
    }
    //判断插入的数据是否NULL
    if (!data)
    {
        return;
    }
    //判断比较函数是否NULL
    if (!compare)
    {
        return;
    }
    //如果根节点为空，把新添加的数据赋值给根节点，并返回
    if (!mytree->root)
    {
        mytree->root = data;
        return;
    }
    //利用递归添加子节点
    insertPerson((mytree->root), data, compare);
    //调节平衡
    mytree->root=Adjtree(mytree->root);

}

调节平衡

//计算树的高度
int getHight(struct Person* p)
{
//如果节点不存在，返回0
    if (!p)
    {
        return 0;
    }
    //计算左节点高度
    int m = getHight(p->lchild);
    //计算右节点高度
    int n = getHight(p->rchild);
    //左节点和右节点中的最大值+1
    return m > n ? ++m : ++n;
}
//向右旋转
struct Person* rightHand(struct Person* data)
{
//记录当前节点
    struct Person* temp = data;
    //把当前节点的左节点赋值给当前节点
    data = data->lchild;
    //修改当前节点的父指向
    data->parent = temp->parent;
//记录修改后当前节点的右指向
    struct Person* myrchild = data->rchild;
    //把当前节点右指向赋值给以前节点的左指向
    temp->lchild = data->rchild;
    //如果不为空，修改父指向
    if (data->rchild)
    {
        myrchild->parent = temp;
    }
        //把以前节点赋值给当前节点的右节点
    data->rchild = temp;
        //修改以前节点的父指向
    temp->parent = data;
    //返回修改后的节点
    return data;
}
//向左旋转
struct Person* leftHand(struct Person* data)
{
    //记录当前节点
    struct Person* temp = data;
    //把当前节点的右节点赋值给当前节点
    data = data->rchild;
    //修改当前节点的父指向
    data->parent = temp->parent;
//记录修改后当前节点的左指向
    struct Person* mylchild = data->lchild;
    //把当前节点左指向赋值给以前节点的右指向
    temp->rchild = data->lchild;
    //如果不为空，修改父指向
    if (mylchild)
    {
        mylchild->parent = temp;
    }
    //把以前节点赋值给当前节点的左节点
    data->lchild = temp;
    //修改以前节点的父指向
    temp->parent = data;
    //返回修改后的节点
    return data;
}
struct Person* Adjtree(struct Person* tree)
{
//如果节点为空，返回
    if (NULL == tree)
    {
        return NULL;
    }
    //左节点或右节点有一个不为空才进行判断
    if (NULL != tree->lchild || NULL != tree->rchild)
    {
    //把左右节点传入函数
    tree->lchild=Adjtree(tree->lchild);
        tree->rchild=Adjtree(tree->rchild);
        //计算左右节点的高度
        int l = getHight(tree->lchild);
        int r = getHight(tree->rchild);
        //判断左右节点的高度，如果左节点比右节高度多于1，进行旋转
        if ((l - r) > 1)
        {//比较子节点的左右节点高度
            struct Person* data = tree->lchild;
            int ll = getHight(data->lchild);
            int rr = getHight(data->rchild);
            //如果右节点大于左节点
            if (rr > ll)
            {//左旋一次
                tree->lchild=leftHand(data);
            }
            //右旋一次
            tree=rightHand(tree);
        }else//判断左右节点的高度，如果右节点比左节高度多于1，进行旋转
        if ((r - l) > 1)
        {//比较子节点的左右节点高度
            struct Person* data = tree->rchild;
            int ll = getHight(data->lchild);
            int rr = getHight(data->rchild);
            //如果左节点大于右节点
            if (ll > rr)
            {
            //右旋一次
                tree->rchild=rightHand(data);
            }
            //左旋一次
            tree=leftHand(tree);
        }
    }
    //返回修改后的节点
    return tree;
}