PAT 1066

#include<cstdio> #include<algorithm> #include<cstring> #include<cstring> #include<iostream> #include<vector> using namespace std; struct Node { Node* lchild; Node* rchild; int data; int h; }; vector<int> in; int gh(Node* root) { if (root == NULL) return 0; else return root->h; } int gb(Node* root) { if (root == NULL) return 0; else return gh(root->lchild) - gh(root->rchild); } void uh(Node* root) { if (root == NULL) return; else root->h = max(gh(root->lchild),gh(root->rchild))+1; } void L(Node* &root) { Node* temp; temp = root->rchild; root->rchild = temp->lchild; temp->lchild = root; uh(root); uh(temp); root = temp; return; } void R(Node* &root) { Node* temp; temp = root->lchild; root->lchild = temp->rchild; temp->rchild = root; uh(root); uh(temp); root = temp; return; } void insert(Node* &root,int a) { if (root == NULL) { root = new Node; root->lchild = root->rchild = NULL; root->h = 1; root->data = a; return; } if (a < root->data) { insert(root->lchild, a); uh(root); if (gb(root) == 2) { if (gb(root->lchild) == 1) R(root); else if (gb(root->lchild) == -1) { L(root->lchild); R(root); } } } else { insert(root->rchild, a); uh(root); if (gb(root) == -2) { if (gb(root->rchild) == -1) L(root); else if (gb(root->rchild) == 1) { R(root->rchild); L(root); } } } } int main() { int n; cin >> n; int temp; for (int i=0;i<n;i++) { cin >> temp; in.push_back(temp); } Node* root = NULL; for (int i=0;i<in.size();i++) { insert(root,in[i]); } cout << root->data; system("pause"); return 0; }