vue mongoose boost architecture db2 vue引入组件 bootstrap后台模板 网页后台模板 webpack视频 mysql重新初始化 arraylist删除指定元素 bootstrap文本框 matlab求向量的模 oracle查看所有数据库 cad正在执行命令 后台管理网站模板 python运算 python自学教程 python调用函数 python语言编程 python怎么使用 java读取文件 java数据类型转换 linux磁盘管理 linux的安装 蓝牙运动耳机排行榜 volist phpqrcode winhex教程 linux端口映射 电子商城系统 cubase下载 mac强制重启 js验证码 华为动态照片 德玛上单天赋 小米手环怎么连接手机 c4dr20 python爬取图片 mysql退出命令
当前位置: 首页 > 学习教程  > 编程语言

【剑指紫金港】1123 Is It a Complete AVL Tree 完全AVL树模板

2021/2/13 16:20:20 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

A 1123 Is It a Complete AVL Tree 题目链接 Problem Description An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebal…

A 1123 Is It a Complete AVL Tree

题目链接

Problem Description

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.
1

2
3
4
Now given a sequence of insertions, you are supposed to output the level-order traversal sequence of the resulting AVL tree, and to tell if it is a complete binary tree.

Input

Each input file contains one test case. For each case, the first line contains a positive integer N (≤ 20). Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.

Output

For each test case, insert the keys one by one into an initially empty AVL tree. Then first print in a line the level-order traversal sequence of the resulting AVL tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line. Then in the next line, print YESif the tree is complete, or NOif not.

Sample Input 1:

5
88 70 61 63 65

Sample Output 1:

70 63 88 61 65
YES

Sample Input 2:

8
88 70 61 96 120 90 65 68

Sample Output 2:

88 65 96 61 70 90 120 68
NO

AC代码
代码实现参照《算法笔记》

#include<bits/stdc++.h>
using namespace std;
const int maxn = 25;
int level[maxn],n,key,ind=0,isComplete=1,flag=0;
struct node{
    int v,h;
    node* l;
    node* r;
};
node* newnode(int x){
    node* root = new node;
    root->v=x;
    root->h=1;
    root->l=root->r=NULL;
    return root;
}
int getHeight(node* root){
    if(root==NULL) return 0;
    return root->h;
}
int getBalanceFactor(node* root){
    return getHeight(root->l)-getHeight(root->r);
}
void updataHeight(node* root){
    root->h=max(getHeight(root->l),getHeight(root->r))+1;
}
void L(node* &root){
    node* temp = root->r;
    root->r=temp->l;
    temp->l=root;
    updataHeight(root);
    updataHeight(temp);
    root=temp;
}
void R(node* &root){
    node* temp = root->l;
    root->l=temp->r;
    temp->r=root;
    updataHeight(root);
    updataHeight(temp);
    root=temp;
}
void insert(node* &root,int x){
    if(root==NULL){
        root=newnode(x);
        return ;
    }
    if(x<root->v){
        insert(root->l,x);
        updataHeight(root);
        if(getBalanceFactor(root)==2){
            if(getBalanceFactor(root->l)==1){
                R(root);
            }else if(getBalanceFactor(root->l)==-1){
                L(root->l);
                R(root);
            }
        }
    }else{
        insert(root->r,x);
        updataHeight(root);
        if(getBalanceFactor(root)==-2){
            if(getBalanceFactor(root->r)==-1){
                L(root);
            }else if(getBalanceFactor(root->r)==1){
                R(root->r);
                L(root);
            }
        }
    }
}
void bfs(node* root){
    queue<node*>q;
    q.push(root);
    while(!q.empty()){
        node* now=q.front();
        q.pop();
        level[ind++]=now->v;
        if(now->l!=NULL){
            if(flag) isComplete=0;
            q.push(now->l);
        }else{
            flag=1;
        }
        if(now->r!=NULL){
            if(flag) isComplete=0;
            q.push(now->r);
        }else{
            flag=1;
        }
    }
}
int main(){
    scanf("%d",&n);
    node* root=NULL;
    for(int i=0;i<n;i++){
        scanf("%d",&key);
        insert(root,key);
    }
    bfs(root);
    for(int i=0;i<ind;i++){
        if(i>0) printf(" ");
        printf("%d",level[i]);
    }
    printf("\n%s",isComplete ? "YES" : "NO");
    return 0;
}

本文链接: http://www.dtmao.cc/news_show_700021.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?