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

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

Time Limit: 400MS Memory limit: 65536K

题目描述

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

输入

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

输出

输出平衡二叉树的树根。

示例输入

5 88 70 61 96 120

示例输出

70

提示

#include<bits/stdc++.h> using namespace std; struct node { int data; int high; struct node *l; struct node *r; }; int max(int x,int y) { if(x>y) { return x; } else return y; } int deep(struct node *T) { if(!T) return -1; else return T->high; } struct node *ll(struct node *root) { struct node *p; p=root->l; root->l=p->r; p->r=root; p->high=max(deep(p->l),deep(p->r))+1; root->high=max(deep(root->l),deep(root->r))+1; return p; }; struct node *rr(struct node *root) { struct node *p; p=root->r; root->r=p->l; p->l=root; p->high=max(deep(p->l),deep(p->r))+1; root->high=max(deep(root->l),deep(root->r))+1; return p; }; struct node *rl(struct node *root) { root->l=rr(root->l); return ll(root); }; struct node *lr(struct node *root) { root->r=ll(root->r); return rr(root); }; struct node *creat(struct node *root,int e) { if(!root) { root=new node; root->data=e; root->high=0; root->l=NULL; root->r=NULL; } else if(root->data>e) { root->l=creat(root->l,e); if(deep(root->l)-deep(root->r)>1) { if(e<root->l->data) root=ll(root); else root=rl(root); } } else if(root->data<e) { root->r=creat(root->r,e); if(deep(root->r)-deep(root->l)>1) { if(e>root->r->data) { root=rr(root); } else root=lr(root); } } root->high=max(deep(root->l),deep(root->r))+1; return root; }; int main() { int n; int num; cin>>n; struct node *root; root=NULL; for(int i=0;i<n;i++) { cin>>num; root=creat(root,num); } cout<<root->data<<endl; return 0; }