没什么好说的……其实就是插入平衡二叉树的过程，具体实现慕课中已经讲过了，写一下再注意一下输入格式就好了。
#include <iostream> #include <malloc.h> typedef struct AVLNode *AVLTree; struct AVLNode{ int data; // 存值 AVLTree left; // 左子树 AVLTree right; // 右子树 int height; // 树高 }; using namespace std; int Max(int a,int b) { return a>b?a:b; } int Height(AVLTree A) { return A==NULL?-1:A->height; } AVLTree RR(AVLTree A) { AVLTree B = A->right; A->right =B->left; B->left = A; A->height = Max(Height(A->left),Height(A->right))+1; B->height = Max(Height(B->left),A->height)+1; return B; } AVLTree LL(AVLTree A) { AVLTree B = A->left; A->left = B->right; B->right = A; A->height = Max(Height(A->left),Height(A->right))+1; B->height = Max(Height(B->left),A->height)+1; return B; } AVLTree LR(AVLTree A) { A->left = RR(A->left); return LL(A); } AVLTree RL(AVLTree A) { A->right = LL(A->right); return RR(A); } AVLTree Insert(AVLTree T,int x){ if(!T){ // 如果该结点为空，初始化结点 T = (AVLTree)malloc(sizeof(struct AVLNode)); T->data = x; T->left = NULL; T->right = NULL; T->height = 0; }else{ // 否则不为空， if(x < T->data){ // 左子树 T->left = Insert(T->left,x); if(Height(T->left)-Height(T->right)==2){ if(x < T->left->data) T = LL(T); else if(T->left->data < x) T = LR(T); } }else if(T->data < x){ T->right = Insert(T->right,x); if(Height(T->right)-Height(T->left)==2){ if(x < T->right->data) T = RL(T); else if(T->right->data < x) T = RR(T); } } } //更新树高 T->height = Max(Height(T->left),Height(T->right)) + 1; return T; } int main() { AVLTree T = NULL; int n,i; cin>>n; for(i=0;i<n;i++){ int temp; cin>>temp; T = Insert(T,temp); } cout<<T->data; return 0; }