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

原创 2017年12月13日 20:07:04

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

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

1.调整方法

(1)插入点位置必须满足二叉查找树的性质,即任意一棵子树的左结点都小于根结点,右结点大于根结点

(2)找出插入结点后不平衡的最小二叉树进行调整,如果是整个树不平衡,才进行整个树的调整。

2.调整方式

(1)LL型

LL型:插入位置为左子树的左结点,进行向右旋转


由于在A的左孩子B的左子树上插入结点F,使A的平衡因子由1变为2,成为不平衡的最小二叉树根结点。此时A结点顺时针右旋转,旋转过程中遵循“旋转优先”的规则,A结点替换D结点成为B结点的右子树,D结点成为A结点的左孩子。
(2)RR型
RR型:插入位置为右子树的右孩子,进行向左旋转

由于在A的右子树C的右子树插入了结点F,A的平衡因子由-1变为-2,成为不平衡的最小二叉树根结点。此时,A结点逆时针左旋转,遵循“旋转优先”的规则,A结点替换D结点成为C的左子树,D结点成为A的右子树。

(3)LR型
LR型:插入位置为左子树的右孩子,要进行两次旋转,先左旋转(RR型),再右旋转(LL型);第一次最小不平衡子树的根结点先不动,调整插入结点所在的子树,第二次再调整最小不平衡子树。

由于在A的左子树B的右子树上插入了结点F,A的平衡因子由1变为了2,成为不平衡的最小二叉树根结点。第一次旋转A结点不动,先将B的右子树的根结点D向左上旋转提升到B结点的位置,然后再把该D结点向右上旋转提升到A结点的位置。
(4)RL型
RL型:插入位置为右子树的左孩子,进行两次调整,先右旋转再左旋转;处理情况与LR类似。



#include <stdio.h>
#include <stdlib.h>
#include <string.h>


typedef int Elemtype;


typedef struct node
{
    Elemtype data;
    int d;
    struct node *lchild,*rchild;
};


int max(int x,int y)
{
    return x>y ? x:y;
}


int Deep(struct node *head)
{
    if (!head)
        return -1;
    else return head->d;
}


struct node *LL(struct node *head)//右旋
{
 struct node *p = head->lchild;
 head->lchild = p->rchild;
 p->rchild = head;
 p->d = max(Deep(p->lchild),Deep(p->rchild))+1;
 head->d = max(Deep(head->lchild),Deep(head->rchild))+1;
 return p;
}


struct node *RR(struct node *head)//左旋
{
 struct node *p = head->rchild;
 head->rchild = p->lchild;
 p->lchild = head;
 p->d = max(Deep(p->lchild),Deep(p->rchild))+1;
 head->d = max(Deep(head->lchild),Deep(head->rchild))+1;
 return p;
}


struct node *LR(struct node *head)
{
  head->lchild = RR(head->lchild);//先做左旋
  return LL(head);//在做右旋
}


struct node *RL(struct node *head)
{
 head->rchild = LL(head->rchild);//先做右旋
 return RR(head);//在做左旋
}
struct node *Creat(struct node *head,int x)
{
    if (head == NULL)
    {
        head = (struct node *)malloc (sizeof (struct node));
        head->data = x;
        head->d = 0;
        head->rchild = head->lchild = NULL;
    }
    else if (head->data > x)
    {
        head->lchild = Creat(head->lchild,x);
        if (Deep(head->lchild)-Deep(head->rchild)>1)
        {
            if (head->lchild->data > x)
                head = LL(head);
            else
                head = LR(head);
        }
    }
    else if (head->data < x)
    {
        head->rchild  = Creat(head->rchild,x);
        if (Deep(head->rchild)-Deep(head->lchild)>1)
        {
            if (head->rchild->data > x)
                head = RL(head);
            else
                head = RR(head);
        }
    }
    head->d = max(Deep(head->lchild),Deep(head->rchild))+1;
    return head;
}


int main()
{
    int n,m;
    scanf ("%d",&n);
    struct node *head = NULL;
    for (int i=0; i<n; i++)
    {
        scanf ("%d",&m);
        head = Creat(head,m);
    }
    printf ("%d\n",head->data);
    return 0;
}



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

题目描述 根据给定的输入序列建立一棵平衡二叉树,求出建立的平衡二叉树的树根。 输入 输入一组测试数据。数据的第1行给出一个正整数N(n 输出 输出平...
  • cui2839255227
  • cui2839255227
  • 2016年08月13日 14:02
  • 178

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

创建平衡二叉树,我们采用依次插入节点的方式进行。而平衡二叉树上插入节点采用递归的方式进行。递归算法如下: (1)      若该树为一空树,那么插入一个数据元素为e的新节点作为平衡二叉树的根节点,树...
  • guoqingshuang
  • guoqingshuang
  • 2015年12月05日 22:50
  • 1889

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

数据结构实验之查找二:平衡二叉树 Time Limit: 400MS Memory limit: 65536K 题目描述 根据给定的输入序列建立一棵平衡二叉树,求出建立的平衡...
  • AC_road
  • AC_road
  • 2015年12月04日 11:27
  • 719

SDTU(3374) 数据结构实验之查找二:平衡二叉树

数据结构实验之查找二:平衡二叉树 Time Limit: 400ms   Memory limit: 65536K   题目描述 根据给定的输入序列建立一棵平衡二叉树,求出建立的平...
  • zheng__jun
  • zheng__jun
  • 2016年08月18日 20:15
  • 449

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

大部分摘自,略有不同http://www.cnblogs.com/You0/p/4459719.html Problem Description根据给定的输入序列建立一棵平衡二叉树,求出建立的平衡二...
  • sdut16szq
  • sdut16szq
  • 2017年02月08日 17:12
  • 68

平衡二叉树的实现原理(代码实现)

平衡二叉树的实现原理(代码实现)
  • qq78442761
  • qq78442761
  • 2017年03月04日 08:53
  • 1187

数据结构实验之二叉树二:遍历二叉树

今天,我复习了一下先序遍历、中序遍历、后序遍历 如果在座的读者不知道什么是的话,可以百度哦!!!!! 数据结构实验之二叉树二:遍历二叉树 Time Limit: 1000MS M...
  • qq_34952846
  • qq_34952846
  • 2016年05月21日 00:11
  • 2445

数据结构实验之二叉树的建立与遍历

数据结构实验之二叉树的建立与遍历 Time Limit: 1000ms   Memory limit: 65536K  有疑问?点这里^_^ 题目描述        已知一个按先序序...
  • LsMrSUN
  • LsMrSUN
  • 2016年08月01日 15:16
  • 552

数据结构中常见的树(BST二叉搜索树、AVL平衡二叉树、RBT红黑树、B-树、B+树、B*树)

BST树        即二叉搜索树:        1.所有非叶子结点至多拥有两个儿子(Left和Right);        2.所有结点存储一个关键字;        3...
  • Sup_Heaven
  • Sup_Heaven
  • 2014年09月16日 12:07
  • 32368

平衡二叉查找树(AVL)的查找、插入、删除

1.平衡二叉查找树
  • lpp0900320123
  • lpp0900320123
  • 2014年09月18日 10:46
  • 5285
内容举报
返回顶部
收藏助手
不良信息举报
您举报文章:数据结构实验之查找二:平衡二叉树
举报原因:
原因补充:

(最多只允许输入30个字)