根据给定的输入序列建立一棵平衡二叉树，求出建立的平衡二叉树的树根。
输入一组测试数据。数据的第1行给出一个正整数N(n <= 20)，N 表示输入序列的元素个数；第2行给出N个正整数，按数据给定顺序建立平衡二叉树。
输出平衡二叉树的树根。
示例程序
#include <iostream> #include <stdlib.h> #include <string.h> #include <stdio.h> using namespace std; struct node { int data; int d; //定义一个用来判读平衡因子的变量，它的范围只能为-1 ~ 1 struct node * l; struct node * r; }; int max(int x, int y) { if(x > y) return x; else return y; } int Deep(struct node * head) //通过递归，返回每一个节点的平衡因子· { if(head == NULL) return -1; return head->d; } //当左左的时候， 也就是在左子树的基础上再插入左子树 struct node * LL(struct node * head) { struct node * p; p = head->l; //定义一个新的节点子树，用来存放原左子树，它将用来构成添加旋转后形成的新的子树 head->l = p->r; //把新的子树的右子树整支来替换掉原子树的左子树 p->r = head; //把变化后的原子树作为新的树的右子树插入进来 p->d = max(Deep(p->l),Deep(p->r)) + 1; head->d = max(Deep(head->l), Deep(head->r)) + 1; return p; }; //当右右的时候， 也就是在原右子树再插入右子树 struct node * RR(struct node * head) { struct node * p; p = head->r; //同上左左的情况，只是把左右子树反过来 head->r = p->l; p->l = head; p->d = max(Deep(p->l), Deep(p->r)) + 1; head->d = max(Deep(head->l), Deep(head->r)) + 1; return p; }; //当左右的时候，也就是在已经平衡的左子树上插入一个右节点 //此时的变换分为两次，首先先把它的左子树进行右右变换，变换完了再以原函数进行左左变换 struct node * LR(struct node * head) { head->l = RR(head->l); head = LL(head); return head; }; //当右左的时候，也就是已经平衡的右子树插入一个左几点 //同上，变换分两次，先左左，再右右 struct node * RL(struct node * head) { head->r = LL(head->r); head = RR(head); return head; }; //收集数据，建立一棵平衡二叉树 struct node * creat(struct node * head, int x) { if(head == NULL) { head = (struct node *)malloc(sizeof(struct node)); head->d = 0; head->data = x; head->l = NULL; head->r = NULL; } else if(x < head->data) { head->l = creat(head->l, x); if(Deep(head->l) - Deep(head->r) > 1) //当左右两个分子树的深度差距大于1的根据要求变换 { if(x < head->l->data) head = LL(head); else head = LR(head); } } else if(x > head->data) { head->r = creat(head->r, x); if(Deep(head->r) - Deep(head->l) > 1) { if(x > head->r->data) head = RR(head); else head = RL(head); } } head->d = max(Deep(head->l), Deep(head->r)) + 1; return head; }; int main() { int n, x; struct node * head = NULL; cin >> n; for(int i = 0; i < n; i++) { cin >> x; head = creat(head, x); } cout << head->data << endl; return 0; }
