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

Time Limit: 400MS  Memory Limit: 65536KB Submit  Statistic

Problem Description

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

Input

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

Output

输出平衡二叉树的树根。

Example Input

5 88 70 61 96 120

Example Output

70 #include<iostream> using namespace std; typedef struct node { int data,deep; struct node *l,*r; }st; int height(st *root) { if(root==NULL) return -1; return root->deep; } st *LLchange(st *root) { st *p; p=root->l; root->l=p->r; p->r=root; p->deep=max(height(p->l),height(p->r))+1; root->deep=max(height(root->l),height(root->r))+1; return p; } st *RRchange(st *root) { st *p; p=root->r; root->r=p->l; p->l=root; p->deep=max(height(p->l),height(p->r))+1; root->deep=max(height(root->l),height(root->r))+1; return p; } st *LRchange(st *root) { root->l=RRchange(root->l); return LLchange(root); } st *RLchange(st *root) { root->r=LLchange(root->r); return RRchange(root); } st *Push(st *root,int k) { if(root==NULL) { root=new st; root->data=k; root->deep=0; root->l=root->r=NULL; } else if(k<root->data) { root->l=Push(root->l,k); if(height(root->l)-height(root->r)==2) { if(k<root->l->data) root=LLchange(root); else root=LRchange(root); } } else if(k>root->data) { root->r=Push(root->r,k); if(height(root->r)-height(root->l)==2) { if(k<root->r->data) root=RLchange(root); else root=RRchange(root); } } root->deep=max(height(root->l),height(root->r))+1; return root; } int main() { int n,k; while(cin>>n) { st *root=NULL; while(n--) { cin>>k; root=Push(root,k); } cout<<root->data<<endl; } return 0; }