【平衡二叉树】数据结构实验之查找二：平衡二叉树

平衡二叉树

刚开始接触平衡二叉树，没有什么太多要分析的。博客里有很多大佬们都写的很好。平衡二叉树就是每个节点的子树的高度差不超过1的二叉树。可以快速搜索数值的一种算法，最糟的情况就是一直找到底，但也是log（n）的。还是快很多。

#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#define max(a , b) (a > b ? (a) : (b))
struct tree
{
    int data, d;
    struct tree *ltree, *rtree;
};

int deep(struct tree *root)//计算深度
{
    if(!root)
    {
        return 0;
    }
    else
        return root->d;
}

struct tree *LL(struct tree *root)//LL型，就是右旋。插入的是左树的左儿子。
{
    struct tree *p = root->ltree;
    root->ltree = p->rtree;
    p->rtree = root;
    root->d = max(deep(root->ltree), deep(root->rtree)) + 1;//记住每次旋转之后根位置变化了，要从新计算深度。
    return p;
}

struct tree *RR(struct tree *root)//RR型，就是左旋。插入的是右树的右儿子。
{
    struct tree *p = root->rtree;
    root->rtree = p->ltree;
    p->ltree = root;
    root->d = max(deep(root->ltree), deep(root->rtree)) + 1;//记住每次旋转之后根位置变化了，要从新计算深度。
    return p;
}

struct tree *LR(struct tree *root)//LR型，要先左旋再右旋，插入的是左树的右儿子。
{
    root->ltree = RR(root->ltree);
    root = LL(root);
    return root;
}

struct tree *RL(struct tree *root)//RL型，要先右旋再左旋，插入的事右树的左儿子。
{
    root->rtree = LL(root->rtree);
    root = RR(root);
    return root;
}

struct tree *creat(struct tree *root, int m)
{
    if(!root)
    {
        root = (struct tree *)malloc(sizeof(struct tree));
        root->data = m;
        root->d = 1;//每次生成把深度记为1，当然0也可以（就是要在计算深度的地方要记得改为 return -1；）
        root->ltree = root->rtree = NULL;
        return root;
    }
    else
    {
        if(root->data > m)//插入二叉树的左树
        {
            root->ltree = creat(root->ltree, m);
            if(deep(root->ltree) - deep(root->rtree) > 1)
            {
                if(root->ltree->data > m)//左树的左儿子
                {
                    root = LL(root);
                }
                else//左树的右儿子
                {
                    root = LR(root);
                }
            }
        }
        else//插入二叉树的右树
        {
            root->rtree = creat(root->rtree, m);
            if(deep(root->rtree) - deep(root->ltree) > 1)
            {
                if(root->rtree->data > m)//右树的左儿子
                {
                    root = RL(root);
                }
                else//右树的右儿子
                {
                    root = RR(root);
                }
            }
        }
    }
    root->d = max(deep(root->ltree), deep(root->rtree)) + 1;//计算根的深度。
    return root;
}

int main()
{
    int n, m;
    while(~scanf("%d", &n))
    {
        struct tree *root = NULL;//指针暂时不用的时候要记得初始化为NULL。要不会很恐怖不信你试试。
        while(n--)
        {
            scanf("%d", &m);
            root = creat(root, m);
        }
        printf("%d
", root->data);
    }
    return 0;
}