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

骑猪看日落 2022-09-25 04:15 124阅读 0赞

## 题目描述 ##

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

## 输入 ##

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

## 输出 ##

输出平衡二叉树的树根。

## 示例输入 ##

5
    88 70 61 96 120

## 示例输出 ##

## 提示 ##

\#include<stdio.h>  
\#include<stdlib.h>  
struct hh  
\{  
int data;  
int d;  
struct hh \*l;  
struct hh \*r;  
\};  
int deep(struct hh \*p)  
\{  
if(p==NULL)  
return -1;  
else  
return p->d;  
\}  
int max(int x,int y)  
\{  
if(x>y)  
return x;  
else  
return y;  
\}  
struct hh \*LL(struct hh \*p)  
\{  
struct hh \*q=p->l;  
p->l=q->r;  
q->r=p;  
q->d=max(deep(q->l),deep(q->r))+1;  
p->d=max(deep(p->l),deep(p->r))+1;  
return q;  
\}  
struct hh \*RR(struct hh \*p)  
\{  
struct hh \*q=p->r;  
p->r=q->l;  
q->l=p;  
q->d=max(deep(q->l),deep(q->r))+1;  
p->d=max(deep(p->l),deep(p->r))+1;  
return q;  
\}  
struct hh \*LR(struct hh \*p)  
\{  
p->l=RR(p->l);  
return LL(p);  
\}  
struct hh \*RL(struct hh \*p)  
\{  
p->r=LL(p->r);  
return RR(p);  
\}  
struct hh \*creat(struct hh \*p,int x)  
\{  
if(p==NULL)  
\{  
p=(struct hh \*)malloc(sizeof(struct hh));  
p->l=NULL;  
p->r=NULL;  
p->data=x;  
p->d=0;  
\}  
else if(x<p->data)  
\{  
p->l=creat(p->l,x);  
if(deep(p->l)-deep(p->r)>1)  
\{  
if(x<p->l->data)  
p=LL(p);  
else  
p=LR(p);  
\}  
\}  
else if(x>p->data)  
\{  
p->r=creat(p->r,x);  
if(deep(p->r)-deep(p->l)>1)  
\{  
if(x>p->r->data)  
p=RR(p);  
else  
p=RL(p);  
\}  
\}  
p->d=max(deep(p->l),deep(p->r))+1;  
return p;  
\}  
int main()  
\{  
struct hh \*p=NULL;  
int n,i,x;  
scanf("%d",&n);  
for(i=0;i<n;i++)  
\{  
scanf("%d",&x);  
p=creat(p,x);  
\}  
printf("%d\\n",p->data);  
return 0;  
\}