5-8 平衡二叉树的根 (25分)
将给定的一系列数字插入初始为空的AVL树,请你输出最后生成的AVL树的根结点的值。
输入格式:
输入的第一行给出一个正整数NN(\le 20≤20),随后一行给出NN个不同的整数,其间以空格分隔。
输出格式:
在一行中输出顺序插入上述整数到一棵初始为空的AVL树后,该树的根结点的值。
输入样例1:
5
88 70 61 96 120
输出样例1:
70
#include<bits/stdc++.h> using namespace std; struct node { int data,h; node*l,*r; }; int deep(node*root) { if(root==NULL)return -1; else return root->h; } node* LL(node*root) { node* p = root->l; root->l = p->r; p->r = root; p ->h = max(deep(p->r),deep(p->l))+1; root->h = max(deep(root->l),deep(root->r))+1; return p; } node* RR(node *root) { node*p = root->r; root->r = p->l; p->l = root; p ->h = max(deep(p->r),deep(p->l))+1; root->h = max(deep(root->l),deep(root->r))+1; return p; } node* LR(node*root) { root->l = RR(root->l); return LL(root) ; } node* RL(node*root) { root->r = LL(root->r) ; return RR(root); } node* build(node*root,int num) { if(root==NULL) { node*p = new node; p->data = num; p->l = NULL; p->h = 0; p->r = NULL; return p; } if(num<root->data) { root->l = build(root->l,num); if(deep(root->l)-deep(root->r)>1) { if(num<root->l->data) { root = LL(root); } else { root = LR(root); } } } else { root->r= build(root->r,num); if(deep(root->r)-deep(root->l)>1) { if(num>root->r->data) { root = RR(root); } else { root = RL(root); } } } root->h = max(deep(root->l),deep(root->r))+1; return root; } int main() { node*root = NULL; int n; cin>>n; for(int i=1; i<=n; i++) { int num; cin>>num; root = build(root,num); } cout<<root->data<<endl; return 0; }