数据结构实验之查找二：平衡二叉树
Time Limit: 400 ms Memory Limit: 65536 KiB
Problem Description
根据给定的输入序列建立一棵平衡二叉树，求出建立的平衡二叉树的树根。
Input
输入一组测试数据。数据的第1行给出一个正整数N(n <= 20)，N表示输入序列的元素个数；第2行给出N个正整数，按数据给定顺序建立平衡二叉树。
Output
输出平衡二叉树的树根。
Sample Input
588 70 61 96 120
Sample Output
70 提示：本题考查平衡二叉树的特点：树的左子树和右子树的高度差不超过1，所以要通过不断移动结点来使二叉树平衡。 代码实现如下（g++）：
#include#include typedef struct node{ int data,dp; struct node *l,*r;}node;int max(int x,int y)//找最大值{ if(x>y) { return x; } else { return y; }}int deep(node *t)//求树高{ if(t==NULL) { return -1; } else { return t->dp; }}node *LL(node *t)//LL型变换{ node *p; p=t->l;//p是t的左子树 t->l=p->r;//p的右子树连上t的左子树 p->r=t;//p的右子树连上t p->dp=max(deep(p->l),t->dp)+1;//求树的深度 t->dp=max(deep(t->l),deep(t->r))+1; return p;}node *RR(node *t)//RR型变换{ node *p; p=t->r; t->r=p->l; p->l=t;p->dp=max(deep(p->r),t->dp)+1; t->dp=max(deep(t->l),deep(t->r))+1; return p;}node *RL(node *t)//RL型变换{ t->r=LL(t->r);//将其变成RR型 return RR(t);}node *LR(node *t)//LR型变换{ t->l=RR(t->l); return LL(t);};node *create(node *t,int x){ if(t==NULL) { t=(node *)malloc(sizeof(node)); t->l=NULL; t->r=NULL; t->data=x;//树根起始为x t->dp=0;//树深为0 } else if(x data)//重新找树根 { t->l=create(t->l,x); if(deep(t->l)-deep(t->r)>1) { if(x l->data) { t=LL(t); } else { t=LR(t); } } } else if(x>t->data)//重新找树根 { t->r=create(t->r,x); if(deep(t->r)-deep(t->l)>1) { if(x>t->r->data) { t=RR(t); } else { t=RL(t); } } } t->dp=max(deep(t->l),deep(t->r))+1; return t;}int main(){ int n,i,x; scanf("%d",&n); node *h=NULL; for(i=1;n>=i;i++) { scanf("%d",&x); h=create(h,x); } printf("%d\n",h->data); return 0;}/***************************************************Result: AcceptedTake time: 0msTake Memory: 152KB****************************************************/