平衡二叉树

#include <stdio.h> #include <stdlib.h> #include <algorithm> using namespace std; typedef struct bitnode { int data; int d; struct bitnode *lchild, *rchild; }* bitree; int deep(bitree &t) { if(!t) return -1; return t->d; } bitree LL(bitree &t) //单旋转 { bitree q; q = t->lchild; t->lchild = q->rchild; q->rchild = t; q->d = max(deep(q->lchild), deep(q->rchild))+1; t->d = max(deep(t->lchild), deep(t->rchild))+1; return q; } bitree RR(bitree &t)//单旋转 { bitree q; q = t->rchild; t->rchild = q->lchild; q->lchild = t; q->d = max(deep(q->lchild), deep(q->rchild))+1; t->d = max(deep(t->lchild), deep(t->rchild))+1; return q; } bitree LR(bitree &t)//旋转分两步：1.以a为根结点的RR旋转 2.以x为根结点的LL旋转 。 { t->lchild = RR(t->lchild); return LL(t); } bitree RL(bitree &t)//旋转分两步：1.以a为根结点的LL旋转 2.以x为根结点的RR旋转 。 { t->rchild = LL(t->rchild); return RR(t); } bitree Insert(bitree &t, int x) { if(!t) { t = new bitnode; t->lchild = NULL; t->rchild = NULL; t->data = x; t->d = 0; } else if(x<t->data) { t->lchild = Insert(t->lchild, x); if(deep(t->lchild)-deep(t->rchild)>1) { if(x<t->lchild->data) t = LL(t); else t = LR(t); } } else if(x>t->data) { t->rchild = Insert(t->rchild, x); if(deep(t->rchild)-deep(t->lchild)>1) { if(x>t->rchild->data) t = RR(t); else t = RL(t); } } t->d = max(deep(t->lchild), deep(t->rchild))+1; return t; } int main() { int n, i, num; scanf("%d", &n); bitree t; t = NULL; for(i=0; i<n; i++) { scanf("%d", &num); Insert(t, num); } printf("%d\n", t->data); }