平衡二叉树的学习-白红宇

平衡二叉树的学习

阅读量：5081 次

发布时间：2019-06-13

本文共 2630 字，大约阅读时间需要 8 分钟。

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

Time Limit: 400 ms Memory Limit: 65536 KiB

Submit Statistic Discuss

Problem Description

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

Input

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

Output

输出平衡二叉树的树根。

Sample Input

88 70 61 96 120

Sample Output

#include
    
     #include
     
      struct node{
        int data;    int height;//高度    struct node *left, *right;};//节点int N;//元素的个数typedef struct node* Node;int deep(Node T){
        if(T == NULL)return 0;    else return T->height;}Node LL(Node T){
        Node temp;    temp = T->left;    T->left = temp->right;    temp->right = T;     T->height = deep(T->left)>deep(T->right)?deep(T->left)+1:deep(T->right)+1;    temp->height = deep(temp->left)>deep(temp->right)?deep(temp->left)+1:deep(temp->right)+1;    return temp;}Node RR(Node T){
        Node temp;    temp = T->right;    T->right = temp->left;    temp->left = T;     T->height = deep(T->left)>deep(T->right)?deep(T->left)+1:deep(T->right)+1;    temp->height = deep(temp->left)>deep(temp->right)?deep(temp->left)+1:deep(temp->right)+1;    return temp;}Node LR(Node T){
        T ->left = RR(T->left);    T = LL(T);    return T;}Node RL(Node T){
        T->right = LL(T->right);    T = RR(T);    return T;}Node Insert(Node T, int num){
        if(T == NULL)//如果为空    {
            T = (Node)malloc(sizeof(struct node));        T ->data = num;        T->left = NULL;        T->right = NULL;        T->height = 1;    }    if(T->data == num)return T;//如果 不能储存相等的 ，    else if(num < T->data)//如果比他小    {
            T->left = Insert(T->left, num);        if(deep(T->left)-deep(T->right)>1)        {
                if(num
      
       left->data)            {
                    T = LL(T);            }            else            {
                    T = LR(T);            }        }    }    else if(num > T->data)//如果比他大    {
              T->right =  Insert(T->right, num);          if(deep(T->right)- deep(T->left)>1)          {
                  if(num > T->right->data)              {
                      T =RR(T);              }              else              {
                      T =RL(T);              }          }    }    T->height = deep(T->left)>deep(T->right)?deep(T->left)+1:deep(T->right)+1;    return T;}Node Creat(){
        Node T = NULL;    int i;    int num;//插入的数    for(i = 0; i < N; i++)    {
            scanf("%d", &num);        T = Insert(T, num);    }    return T;}int main (){
        Node root = NULL;//根节点    scanf("%d",&N);    root = Creat();    printf("%d", root->data);    return 0;}