当前位置: 代码迷 >> 综合 >> PAT1123 Is It a Complete AVL Tree(AVL树完全二叉树)
  详细解决方案

PAT1123 Is It a Complete AVL Tree(AVL树完全二叉树)

热度:11   发布时间:2024-01-16 13:16:43.0

题意:

给出一系列数,要求组成AVL树,最后层序输出,并且判断是否为一个完全二叉树

要点:

这题就是一个AVL树的插入和判断完全二叉树,之前分别都有出现过,AVL树的建立需要记忆。

#include<bits/stdc++.h>
using namespace std;
int cnt=0,n;
bool flag,vis;
vector<int> ans;struct node{int key;node *left,*right;
};node *rotateL(node *root){node *t=root->right;root->right=t->left;t->left=root;return t;
}node *rotateR(node *root){node *t=root->left;root->left=t->right;t->right=root;return t;
}node *rotateLR(node *root){root->left=rotateL(root->left);return rotateR(root);
}node *rotateRL(node *root){root->right=rotateR(root->right);return rotateL(root);
}int getHeight(node *root){if(root==nullptr) return 0;return max(getHeight(root->left),getHeight(root->right))+1;
}node *insert(node *root,int key){if(root==nullptr){root=new node();root->key=key;root->left=root->right=nullptr;}else if(key<root->key){root->left=insert(root->left,key);if(getHeight(root->left)-getHeight(root->right)==2){if(key<root->left->key){root=rotateR(root);}else{root=rotateLR(root);}}}else{root->right=insert(root->right,key);if(getHeight(root->right)-getHeight(root->left)==2){if(key>root->right->key){root=rotateL(root);}else{root=rotateRL(root);}}}return root;
}void print(node *root){queue<node *> que;que.push(root);while(!que.empty()){node *u=que.front();que.pop();if(u!=nullptr){ans.push_back(u->key);que.push(u->left);que.push(u->right);cnt++;}else{if(cnt!=n&&vis){flag=false;vis=false;}}}
}int main(){int temp;scanf("%d",&n);node *root=nullptr;for(int i=0;i<n;i++){scanf("%d",&temp);root=insert(root,temp);}flag=true;vis=true;print(root);for(int i=0;i<ans.size();i++){if(i!=0) printf(" ");printf("%d",ans[i]);}if(flag){printf("\nYES\n");}else{printf("\nNO\n");}return 0;
}

 

  相关解决方案