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

野性酷女 2022-07-12 05:08 174阅读 0赞

think:  
1 今天学习了平衡二叉树的知识，感觉还是不理解，自己照着部分模板敲了代码，但是也不知道自己的学习方法对不对，不知道自己是不是有点拔苗助长的滋味，数据结构树的部分，从最开始的二叉树的遍历，到搜索二叉树，再到现在的平衡二叉树，感觉自己有很多细节并没有理解，很多时候感觉可能只会用一些模板，而对其深刻的思想却领悟的并不透彻，数据结构从开始的线性表，感觉自己并没有脚踏实地的一步一步走坚固，或许自己最初应该从指针开始打下坚固的地基，否则感觉自己愈行愈艰难，知识体系的建立犹如不断抛出自己手中的锚，将之前接触到学习到的知识与自己当前学习的知识联系起来，逐渐得到一种融会贯通的效果。下面进入联系题目的空间吧。

[sdut原题链接][sdut]

数据结构实验之查找二：平衡二叉树  
Time Limit: 400MS Memory Limit: 65536KB

Problem Description  
根据给定的输入序列建立一棵平衡二叉树，求出建立的平衡二叉树的树根。

Input  
输入一组测试数据。数据的第1行给出一个正整数N(n <= 20)，N表示输入序列的元素个数；第2行给出N个正整数，按数据给定顺序建立平衡二叉树。

Output  
输出平衡二叉树的树根。

Example Input  
5  
88 70 61 96 120

Example Output  
70

Hint

Author  
xam

以下为accepted建议参考代码

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #define Max(a, b) (a > b? a: b)
    typedef struct node
    {
        int Data;
        int Hight;//树高
        struct node *left;
        struct node *right;
    } AVLTree;
    int GetHight(AVLTree *T)
    {
        if(T)
            return T->Hight;
        else
            return 0;
    }
    AVLTree * SingleLeftRotation(AVLTree *A)
    {   /* A必须有一个左子结点B*/
        /* 将A与B左单旋，更新A与B的高度，返回新的根结点*/
        AVLTree *B = A->left;
        A->left = B->right;
        B->right = A;
        A->Hight = Max(GetHight(A->left), GetHight(A->right)) + 1;
        B->Hight = Max(GetHight(B->left), A->Hight) + 1;
        return B;
    }
    AVLTree * SingleRightRotation(AVLTree *A)
    {
        /* A必须有一个右子结点B*/
        /* 讲A与B做右单旋，更新A与B的高度，返回新的根结点B*/
        AVLTree *B = A->right;
        A->right = B->left;
        B->left = A;
        A->Hight = Max(GetHight(A->left), GetHight(A->right)) + 1;
        B->Hight = Max(GetHight(B->left), A->Hight) + 1;
        return B;
    }
    AVLTree * DoubleLeftRightRotation(AVLTree *A)
    {   /* A必须有一个左子结点B， 且B必须有一个右子结点C*/
        /* 将A， B， C做两次单旋，返回新的根结点C*/
    
        /* 将B与C做右单旋， C被返回*/
        A->left = SingleRightRotation(A->left);
        /* 将A与C做左单旋， C被返回*/
        return SingleLeftRotation(A);
    }
    AVLTree * DoubleRightLeftRotation(AVLTree *A)
    {   /* A必须有一个右子结点B， 且B必须有一个左子结点C*/
        /* 将A， B， C做两次单旋，返回新的根结点C*/
    
        /* 将B与C做左单旋， C被返回*/
        A->right = SingleLeftRotation(A->right);
        /* 将A与C做右单旋， C被返回*/
        return SingleRightRotation(A);
    }
    AVLTree * Insert(AVLTree *T, int x)//将x插入AVL树中，并且返回调整后的AVL树
    {
        if(T == NULL)
        {
            T = (AVLTree *)malloc(sizeof(AVLTree));
            T->Data = x;
            T->Hight = 1;
            T->left = T->right = NULL;
        }
        else if(x < T->Data)
        {
            T->left = Insert(T->left, x);
            if(GetHight(T->left) - GetHight(T->right) == 2)
            {
                if(x < T->left->Data)
                    T = SingleLeftRotation(T);
                else
                    T = DoubleLeftRightRotation(T);
            }
        }
        else if(x > T->Data)
        {
            T->right = Insert(T->right, x);
            if(GetHight(T->left) - GetHight(T->right) == -2)
            {
                if(x > T->right->Data)
                    T = SingleRightRotation(T);
                else
                    T = DoubleRightLeftRotation(T);
            }
        }
        T->Hight = Max(GetHight(T->left), GetHight(T->right)) + 1;
        return T;
    }
    int main()
    {
        int n, i, x;
        AVLTree *root = NULL;//定义和初始化
        scanf("%d", &n);
        for(i = 0; i < n; i++)
        {
            scanf("%d", &x);
            root = Insert(root, x);//插入
        }
        printf("%d\n", root->Data);//输出最终AVL树的根结点
        return 0;
    }
    
    
    /***************************************************
    User name: jk160630
    Result: Accepted
    Take time: 0ms
    Take Memory: 108KB
    Submit time: 2017-02-12 14:59:55
    ****************************************************/

一下为accepted代码—有疑问数据

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #define Max(a, b) (a > b? a: b)
    typedef struct node
    {
        int Data;
        int Hight;//树高
        struct node *left;
        struct node *right;
    } AVLTree;
    int GetHight(AVLTree *T)
    {
        if(T)
            return T->Hight;
        else
            return 0;
    }
    AVLTree * SingleLeftRotation(AVLTree *A)
    {   /* A必须有一个左子结点B*/
        /* 将A与B左单旋，更新A与B的高度，返回新的根结点*/
        AVLTree *B = A->left;
        A->left = B->right;
        B->right = A;
        A->Hight = Max(GetHight(A->left), GetHight(A->right)) + 1;
        B->Hight = Max(GetHight(B->left), A->Hight) + 1;
        return B;
    }
    AVLTree * SingleRightRotation(AVLTree *A)
    {
        /* A必须有一个右子结点B*/
        /* 讲A与B做右单旋，更新A与B的高度，返回新的根结点B*/
        AVLTree *B = A->right;
        A->right = B->left;
        B->left = A;
        A->Hight = Max(GetHight(A->left), GetHight(A->right)) + 1;
        B->Hight = Max(GetHight(B->left), A->Hight) + 1;
        return B;
    }
    AVLTree * DoubleLeftRightRotation(AVLTree *A)
    {   /* A必须有一个左子结点B， 且B必须有一个右子结点C*/
        /* 将A， B， C做两次单旋，返回新的根结点C*/
    
        /* 将B与C做右单旋， C被返回*/
        A->left = SingleRightRotation(A->left);
        /* 将A与C做左单旋， C被返回*/
        return SingleLeftRotation(A);
    }
    AVLTree * DoubleRightLeftRotation(AVLTree *A)
    {   /* A必须有一个右子结点B， 且B必须有一个左子结点C*/
        /* 将A， B， C做两次单旋，返回新的根结点C*/
    
        /* 将B与C做左单旋， C被返回*/
        A->right = SingleLeftRotation(A->right);
        /* 将A与C做右单旋， C被返回*/
        return SingleRightRotation(A);
    }
    AVLTree * Insert(AVLTree *T, int x)//将x插入AVL树中，并且返回调整后的AVL树
    {
        if(T == NULL)
        {
            T = (AVLTree *)malloc(sizeof(AVLTree));
            T->Data = x;
            T->Hight = 1;
            T->left = T->right = NULL;
        }
        else if(x < T->Data)
        {
            T->left = Insert(T->left, x);
            if(GetHight(T->left) - GetHight(T->right) == 2)
            {
                if(x < T->left->Data)
                    T = SingleLeftRotation(T);
                else
                    T = DoubleLeftRightRotation(T);
            }
        }
     ///else if(x > T->Data)
        else
        {
            T->right = Insert(T->right, x);
            if(GetHight(T->left) - GetHight(T->right) == -2)
            {
                if(x > T->right->Data)
                    T = SingleRightRotation(T);
                else
                    T = DoubleRightLeftRotation(T);
            }
        }
        T->Hight = Max(GetHight(T->left), GetHight(T->right)) + 1;
        return T;
    }
    int main()
    {
        int n, i, x;
        AVLTree *root = NULL;//定义和初始化
        scanf("%d", &n);
        for(i = 0; i < n; i++)
        {
            scanf("%d", &x);
            root = Insert(root, x);//插入
        }
        printf("%d\n", root->Data);//输出最终AVL树的根结点
        return 0;
    }
    
    
    /***************************************************
    User name: jk160630
    Result: Accepted
    Take time: 0ms
    Take Memory: 116KB
    Submit time: 2017-02-12 15:01:15
    ****************************************************/

疑问数据：  
5  
88 70 61 96 96（存在重复元素）

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    struct Tree{
        int x, h;
        Tree *left;
        Tree *right;
    }*root;
    
    int get_h(Tree *rt);
    Tree * insert_x(Tree *rt, int x);
    Tree * L_L(Tree *rt);
    Tree * R_R(Tree *rt);
    Tree * L_R(Tree *rt);
    Tree * R_L(Tree *rt);
    void del_meo(Tree *rt);
    
    int main(){
        int n, i, x;
        while(~scanf("%d", &n)){
            root = NULL;
            for(i = 0; i < n; i++){
                scanf("%d", &x);
                root = insert_x(root, x);
            }
            printf("%d\n", root->x);
            del_meo(root);
        }
        return 0;
    }
    int get_h(Tree *rt){
        if(rt == NULL) return 0;
        else return rt->h;
    }
    Tree * insert_x(Tree *rt, int x){
        if(rt == NULL){
            rt = new Tree;
            rt->x = x;
            rt->h = 1;
            rt->left = rt->right = NULL;
        }
        else if(x < rt->x){
            rt->left = insert_x(rt->left, x);
            if(get_h(rt->left) - get_h(rt->right) == 2){
                if(x < (rt->left)->x)
                    rt = L_L(rt);
                else
                    rt = L_R(rt);
            }
        }
        else if(x > rt->x){
            rt->right = insert_x(rt->right, x);
            if(get_h(rt->left) - get_h(rt->right) == -2){
                if(x > (rt->right)->x)
                    rt = R_R(rt);
                else
                    rt = R_L(rt);
            }
        }
        rt->h = max(get_h(rt->left), get_h(rt->right)) + 1;
        return rt;
    }
    Tree * L_L(Tree *rt){
        Tree *a = rt, *b = rt->left;
        a->left = b->right;
        b->right = a;
        a->h = max(get_h(a->left), get_h(a->right)) + 1;
        b->h = max(get_h(b->left), get_h(b->right)) + 1;
        return b;
    }
    Tree * R_R(Tree *rt){
        Tree *a = rt, *b = rt->right;
        a->right = b->left;
        b->left = a;
        a->h = max(get_h(a->left), get_h(a->right)) + 1;
        b->h = max(get_h(b->left), get_h(b->right)) + 1;
        return b;
    }
    Tree * L_R(Tree *rt){
        Tree *a = rt;
        Tree *b = a->left;
        Tree *c = b->right;
    
        b->right = c->left;
        a->left = c->right;
        c->left = b;
        c->right = a;
    
        a->h = max(get_h(a->left), get_h(a->right)) + 1;
        b->h = max(get_h(b->left), get_h(b->right)) + 1;
        c->h = max(get_h(c->left), get_h(c->right)) + 1;
    
        return c;
    }
    Tree * R_L(Tree *rt){
        Tree *a = rt;
        Tree *b = a->right;
        Tree *c = b->left;
    
        b->left = c->right;
        a->right = c->left;
        c->left = a;
        c->right = b;
    
        a->h = max(get_h(a->left), get_h(a->right)) + 1;
        b->h = max(get_h(b->left), get_h(b->right)) + 1;
        c->h = max(get_h(c->left), get_h(c->right)) + 1;
    
        return c;
    }
    void del_meo(Tree *rt){
        if(rt){
            del_meo(rt->left);
            del_meo(rt->right);
            delete rt;
        }
        return;
    }

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2006/pid/3374