定義結(jié)構(gòu)體

struct Person
{
//父節(jié)點(diǎn)
    struct Person* parent;
    //左子節(jié)點(diǎn)
    struct Person* lchild;
    //右子節(jié)點(diǎn)
    struct Person* rchild;
    int m;
};

struct ABLtree
{//保存根節(jié)點(diǎn)信息
    struct Person* root;
};

初始化根節(jié)點(diǎn)

struct ABLtree* init_tree()
{
//在堆區(qū)開辟一個ABLtree大小的空間
    struct ABLtree* tree = malloc(sizeof(struct ABLtree));
    //開辟失敗返回NULL
    if (!tree)
    {
        return NULL;
    }
    //初始化根節(jié)點(diǎn)為NULL并返回
    tree->root = NULL;
    return tree;
}

添加節(jié)點(diǎn)

//比較函數(shù)队腐，返回兩者的差值
int compare(struct Person* p1, struct Person* p2)
{
    return ((p1->m) - (p2->m));
}
//添加節(jié)點(diǎn)函數(shù)跋涣，內(nèi)部調(diào)用
void insertPerson(struct Person* tree, struct Person* data, int(*compare)(struct Person*, struct Person*))
{
//如果當(dāng)前節(jié)點(diǎn)大于插入的節(jié)點(diǎn)
    if (compare(tree, data) > 0)
    {//if當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)為空
        if (NULL==tree->lchild)
        {//把數(shù)據(jù)賦值給節(jié)點(diǎn)的左子節(jié)點(diǎn)
            tree->lchild = data;
            //把當(dāng)前節(jié)點(diǎn)賦值給數(shù)據(jù)的父節(jié)點(diǎn)
            data->parent = tree;
            //返回
            return;
        }
        //不為空逻锐，則把數(shù)據(jù)的左子節(jié)點(diǎn)傳入函數(shù)
        insertPerson(tree->lchild, data, compare);
    }
    else {
    //if當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)為空
        if (NULL==tree->rchild)
        {
        //把數(shù)據(jù)賦值給節(jié)點(diǎn)的右子節(jié)點(diǎn)
            tree->rchild = data;
        //把當(dāng)前節(jié)點(diǎn)賦值給數(shù)據(jù)的父節(jié)點(diǎn)
            data->parent = tree;
            //返回
            return;
        }
        //不為空，則把數(shù)據(jù)的右子節(jié)點(diǎn)傳入函數(shù)
        insertPerson(tree->rchild, data, compare);
    }

}
//添加節(jié)點(diǎn)函數(shù)边篮，外部調(diào)用
void initer(struct ABLtree* mytree, struct Person* data, int(*compare)(struct Person*, struct Person*))
{
//判斷ABLtree是否NULL
    if (!tree)
    {
        return;
    }
    //判斷插入的數(shù)據(jù)是否NULL
    if (!data)
    {
        return;
    }
    //判斷比較函數(shù)是否NULL
    if (!compare)
    {
        return;
    }
    //如果根節(jié)點(diǎn)為空，把新添加的數(shù)據(jù)賦值給根節(jié)點(diǎn)却特，并返回
    if (!mytree->root)
    {
        mytree->root = data;
        return;
    }
    //利用遞歸添加子節(jié)點(diǎn)
    insertPerson((mytree->root), data, compare);
    //調(diào)節(jié)平衡
    mytree->root=Adjtree(mytree->root);

}

調(diào)節(jié)平衡

//計(jì)算樹的高度
int getHight(struct Person* p)
{
//如果節(jié)點(diǎn)不存在救崔，返回0
    if (!p)
    {
        return 0;
    }
    //計(jì)算左節(jié)點(diǎn)高度
    int m = getHight(p->lchild);
    //計(jì)算右節(jié)點(diǎn)高度
    int n = getHight(p->rchild);
    //左節(jié)點(diǎn)和右節(jié)點(diǎn)中的最大值+1
    return m > n ? ++m : ++n;
}
//向右旋轉(zhuǎn)
struct Person* rightHand(struct Person* data)
{
//記錄當(dāng)前節(jié)點(diǎn)
    struct Person* temp = data;
    //把當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)賦值給當(dāng)前節(jié)點(diǎn)
    data = data->lchild;
    //修改當(dāng)前節(jié)點(diǎn)的父指向
    data->parent = temp->parent;
//記錄修改后當(dāng)前節(jié)點(diǎn)的右指向
    struct Person* myrchild = data->rchild;
    //把當(dāng)前節(jié)點(diǎn)右指向賦值給以前節(jié)點(diǎn)的左指向
    temp->lchild = data->rchild;
    //如果不為空惶看，修改父指向
    if (data->rchild)
    {
        myrchild->parent = temp;
    }
        //把以前節(jié)點(diǎn)賦值給當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)
    data->rchild = temp;
        //修改以前節(jié)點(diǎn)的父指向
    temp->parent = data;
    //返回修改后的節(jié)點(diǎn)
    return data;
}
//向左旋轉(zhuǎn)
struct Person* leftHand(struct Person* data)
{
    //記錄當(dāng)前節(jié)點(diǎn)
    struct Person* temp = data;
    //把當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)賦值給當(dāng)前節(jié)點(diǎn)
    data = data->rchild;
    //修改當(dāng)前節(jié)點(diǎn)的父指向
    data->parent = temp->parent;
//記錄修改后當(dāng)前節(jié)點(diǎn)的左指向
    struct Person* mylchild = data->lchild;
    //把當(dāng)前節(jié)點(diǎn)左指向賦值給以前節(jié)點(diǎn)的右指向
    temp->rchild = data->lchild;
    //如果不為空捏顺，修改父指向
    if (mylchild)
    {
        mylchild->parent = temp;
    }
    //把以前節(jié)點(diǎn)賦值給當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)
    data->lchild = temp;
    //修改以前節(jié)點(diǎn)的父指向
    temp->parent = data;
    //返回修改后的節(jié)點(diǎn)
    return data;
}
struct Person* Adjtree(struct Person* tree)
{
//如果節(jié)點(diǎn)為空，返回
    if (NULL == tree)
    {
        return NULL;
    }
    //左節(jié)點(diǎn)或右節(jié)點(diǎn)有一個不為空才進(jìn)行判斷
    if (NULL != tree->lchild || NULL != tree->rchild)
    {
    //把左右節(jié)點(diǎn)傳入函數(shù)
    tree->lchild=Adjtree(tree->lchild);
        tree->rchild=Adjtree(tree->rchild);
        //計(jì)算左右節(jié)點(diǎn)的高度
        int l = getHight(tree->lchild);
        int r = getHight(tree->rchild);
        //判斷左右節(jié)點(diǎn)的高度纬黎，如果左節(jié)點(diǎn)比右節(jié)高度多于1草丧，進(jìn)行旋轉(zhuǎn)
        if ((l - r) > 1)
        {//比較子節(jié)點(diǎn)的左右節(jié)點(diǎn)高度
            struct Person* data = tree->lchild;
            int ll = getHight(data->lchild);
            int rr = getHight(data->rchild);
            //如果右節(jié)點(diǎn)大于左節(jié)點(diǎn)
            if (rr > ll)
            {//左旋一次
                tree->lchild=leftHand(data);
            }
            //右旋一次
            tree=rightHand(tree);
        }else//判斷左右節(jié)點(diǎn)的高度，如果右節(jié)點(diǎn)比左節(jié)高度多于1莹桅，進(jìn)行旋轉(zhuǎn)
        if ((r - l) > 1)
        {//比較子節(jié)點(diǎn)的左右節(jié)點(diǎn)高度
            struct Person* data = tree->rchild;
            int ll = getHight(data->lchild);
            int rr = getHight(data->rchild);
            //如果左節(jié)點(diǎn)大于右節(jié)點(diǎn)
            if (ll > rr)
            {
            //右旋一次
                tree->rchild=rightHand(data);
            }
            //左旋一次
            tree=leftHand(tree);
        }
    }
    //返回修改后的節(jié)點(diǎn)
    return tree;
}