根据给定的输入序列建立一棵平衡二叉树，求出建立的平衡二叉树的树根。
输入一组测试数据。数据的第1行给出一个正整数N(n <= 20)，N表示输入序列的元素个数；第2行给出N个正整数，按数据给定顺序建立平衡二叉树。
输出平衡二叉树的树根。
xam
参考1：http://blog.csdn.net/u010442302/article/details/52713585
参考2：http://blog.csdn.net/flying_star521/article/details/52311038
参考3：http://blog.csdn.net/annfan123/article/details/52201273
#include <bits/stdc++.h> using namespace std; #define Max(a,b)(a>b?a:b) typedef struct node { node*left,*right; int data; int h; } tree; int geth(tree*root)///注意设立一个获得高度的函数,且只要是和获得高度相关的操作都要用，不要直接调用高度 { if(!root) return 0; else return root->h; } tree*ll(tree*root) { tree*q=root->left; root->left=q->right; q->right=root; root->h=Max(geth(root->left),geth(root->right))+1;///注意返回的高度+1 q->h=Max(geth(q->left),geth(q->right))+1; return q; } tree*rr(tree*root) { tree*q=root->right; root->right=q->left; q->left=root; root->h=Max(geth(root->left),geth(root->right))+1; q->h=Max(geth(q->left),geth(q->right))+1; return q; } tree*lr(tree*root) { root->left=rr(root->left);///注意不要写成rr(root->left);否则WA return ll(root); } tree*rl(tree*root) { root->right=ll(root->right); return rr(root); } tree*creat(tree*root,int x) { if(root==NULL) { root=new tree; root->left=root->right=NULL;///为了规范和易读尽量记得写上，不过不写此题也会AC root->data=x; root->h=1; } else if(x<root->data) { root->left=creat(root->left,x); if(geth(root->left)-geth(root->right)>1) { if(x<root->left->data)///注意单旋和双旋的判断条件 root=ll(root);///这是带返回值的函数,注意一定不要只写ll(root)，下同(或者return ll(root)) else root=lr(root); } } else if(root->data<x) { root->right=creat(root->right,x); if(geth(root->right)-geth(root->left)>1) { if(x>root->right->data) root=rr(root); else root=rl(root); } } root->h=Max(geth(root->left),geth(root->right))+1;///记得每次插入点后要让高度提升(?) return root; } int main() { ///std::ios::sync_with_stdio(false); int n,x; tree*root=NULL; scanf("%d",&n); for(int i=0; i<n; i++) { scanf("%d",&x); root=creat(root,x); } printf("%d\n",root->data); return 0; }