将给定的一系列数字插入初始为空的AVL树，请你输出最后生成的AVL树的根结点的值。
输入的第一行给出一个正整数N（≤），随后一行给出N个不同的整数，其间以空格分隔。
在一行中输出顺序插入上述整数到一棵初始为空的AVL树后，该树的根结点的值。
#include <stdio.h>#include <stdlib.h>struct node{ int data,shen; struct node*l,*r;};int max(int a,int b){ return a>b?a:b;}int shendu(struct node*p){ if (p==NULL){ return -1; } return p->shen;}struct node *zuozuo(struct node*p){ struct node*q; q=p->l; p->l=q->r; q->r=p; q->shen=max(shendu(q->l),p->shen)+1; p->shen=max(shendu(p->l),shendu(p->r))+1; return q;}struct node *youyou(struct node *p){ struct node *q; q=p->r; p->r=q->l; q->l=p; q->shen=max(shendu(q->r),p->shen)+1; p->shen=max(shendu(p->l),shendu(p->r))+1; return q;}struct node *zuoyou(struct node*p){ p->l=youyou(p->l); return zuozuo(p);}struct node *youzuo(struct node*p){ p->r=zuozuo(p->r); return youyou(p);}struct node *creat(struct node*p,int n){ if (p==NULL){ p=(struct node*)malloc(sizeof(struct node)); p->l=NULL; p->r=NULL; p->data=n; p->shen=0; } else if (n<p->data){ p->l=creat(p->l,n); if (shendu(p->l)-shendu(p->r)>1){ if (n<p->l->data){ p=zuozuo(p); } else{ p=zuoyou(p); } } } else if (n>p->data){ p->r=creat(p->r,n); if (shendu(p->r)-shendu(p->l)>1){ if (n>p->r->data){ p=youyou(p); } else{ p=youzuo(p); } } } p->shen=max(shendu(p->l),shendu(p->r))+1; return p;}int main(){ int n,m; scanf("%d",&n); struct node*p=NULL; for (int i=0;i<n;i++){ scanf("%d",&m); p=creat(p,m); } printf("%d\n",p->data); return 0;}
转载于:https://www.cnblogs.com/linguiquan/p/8934029.html
