数据结构实验之查找二:平衡二叉树
Time Limit: 400MS Memory limit: 65536K
题目描述
根据给定的输入序列建立一棵平衡二叉树,求出建立的平衡二叉树的树根。
输入
输入一组测试数据。数据的第1行给出一个正整数N(n <= 20),N表示输入序列的元素个数;第2行给出N个正整数,按数据给定顺序建立平衡二叉树。
输出
输出平衡二叉树的树根。
示例输入
5 88 70 61 96 120
示例输出
70
提示
来源
xam
示例程序
注意这四种旋转LL,RR,LR,RR,
其实就是两种旋转。
LR可以转化成RR+LL;
RL可以转化成LL+RR;
具体转化过程见上一篇博客。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
int height;
int data;
node *lc;
node *rch;
};
int max(int x,int y)
{
return x>y?x:y;
}
int height (node *p)
{
if(p==NULL)
return -1;
else return p->height;
}
node *LL(node *p2)
{
node *p1;
p1=p2->lc;
p2->lc=p1->rch;
p1->rch=p2;
p2->height=max(height(p2->lc),height(p2->rch))+1;
p1->height=max(height(p1->lc),height(p1->rch))+1;
return p1;
}
node *RR(node *t2)
{
node *t1;
t1=t2->rch;
t2->rch=t1->lc;
t1->lc=t2;
t2->height=max(height(t2->lc),height(t2->rch))+1;
t1->height=max(height(t1->rch),t2->height)+1;
return t1;
}
node *LR(node *p3)
{
p3->lc=RR(p3->lc);
return LL(p3);
}
node *RL(node *t3)
{
t3->rch=LL(t3->rch);
return RR(t3); //此处有return 就相当于有了返回的东西
}
node *Insert(node *root, int x)
{
if(root==NULL)
{
root=new node;
root->data=x;
root->height=0;
root->lc=root->rch=NULL;
}
else if (x<root->data)
{
root->lc=Insert(root->lc,x);
if(height(root->lc)-height(root->rch)==2)
{
if(x<root->lc->data)
root=LL(root); //对于有返回值的函数调用时,一定要有返回的的东西,此处不能写成LL(root)
else root=LR(root);
}
}
else if (x>root->data)
{
root->rch=Insert(root->rch,x);
if(height(root->rch)-height(root->lc)==2)
{
if(x>root->rch->data)
root=RR(root);
else root=RL(root);
}
}
root->height=max(height(root->rch),height(root->lc))+1;
return root;
}
int main()
{
int n,m;
struct node *root=NULL;
cin>>n;
while(n--)
{
cin>>m;
root=Insert(root,m);
}
cout<<root->data<<endl;
return 0;
}