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

题目链接：点击打开链接

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

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; typedef int element; struct Tree { element data; int deep; Tree *lchild,*rchild; }; int Max(int a,int b) { return a>b ? a:b; } int Deep(Tree *T) { if(!T) return -1; else return T->deep; } Tree *LL(Tree *T)///右旋 { Tree *p = T->lchild; T->lchild = p->rchild; p->rchild = T; p->deep = Max(Deep(p->lchild),Deep(p->rchild))+1; T->deep = Max(Deep(T->lchild),Deep(T->rchild))+1; return p; } Tree *RR(Tree *T)///左旋 { Tree *p = T->rchild; T->rchild = p->lchild; p->lchild = T; p->deep = Max(Deep(p->lchild),Deep(p->rchild))+1; T->deep = Max(Deep(T->lchild),Deep(T->rchild))+1; return p; } Tree *LR(Tree *T)///先左旋后右旋 { T->lchild = RR(T->lchild); return LL(T); } Tree *RL(Tree *T)///先右旋后左旋 { T->rchild = LL(T->rchild); return RR(T); } Tree *Creat(Tree *T,int n) { if(!T) { T = new Tree; T->data = n; T->deep = 0; T->lchild = T->rchild = NULL; } else { if(n < T->data) { T->lchild = Creat(T->lchild,n); if(Deep(T->lchild)-Deep(T->rchild) > 1) { if(T->lchild->data > n) T = LL(T); else T = LR(T); } } else if(n > T->data) { T->rchild = Creat(T->rchild,n); if(Deep(T->rchild)-Deep(T->lchild) > 1) { if(T->rchild->data < n) T = RR(T); else T = RL(T); } } } T->deep = Max(Deep(T->lchild),Deep(T->rchild)) + 1; return T; } int main() { int n,m; Tree *T = NULL; scanf("%d",&n); for(int i = 0;i < n;i++) { scanf("%d",&m); T = Creat(T,m); } printf("%d\n",T->data); return 0; }