构建AVL树
#include <iostream> #include <string> #include<algorithm> #include<stack> #include<string.h> using namespace std; typedef int ElementType; typedef struct TNode* Position; typedef Position BinTree; struct TNode { ElementType Data; BinTree Left; BinTree Right; }; BinTree NewNode(ElementType X) { BinTree tmp = (BinTree)malloc(sizeof(struct TNode)); tmp->Data = X; tmp->Left = tmp->Right = NULL; return tmp; } BinTree RR(BinTree root) {//右右型 BinTree tmp = root->Right; root->Right = tmp->Left; tmp->Left = root; return tmp; } BinTree LL(BinTree root) {//左左型 BinTree tmp = root->Left; root->Left = tmp->Right; tmp->Right = root; return tmp; } BinTree LR(BinTree root) {//左右型（从右至左矫正） root->Left = RR(root->Left);//变为LL return LL(root); } BinTree RL(BinTree root) {//右左型 root->Right = LL(root->Right);//变为RR return RR(root); } int get_heigth(BinTree root) {//得到结点高度 if (!root) return 0; return max(get_heigth(root->Left), get_heigth(root->Right)) + 1; } BinTree Insert(BinTree Root, ElementType X) { if (!Root) { Root = NewNode(X); } else if (X < Root->Data) { Root->Left = Insert(Root->Left, X); if (get_heigth(Root->Left) - get_heigth(Root->Right) == 2) Root = X > Root->Left->Data ? LR(Root) : LL(Root); } else { Root->Right = Insert(Root->Right, X); if (get_heigth(Root->Left) - get_heigth(Root->Right) == -2) //右子树高，根据插入数值大小选择翻转函数 Root = X < Root->Right->Data ? RL(Root) : RR(Root); } return Root; } int main() { int N,L; int i,flag=0; ElementType X; BinTree AVL = NULL; cin >> N; for (i = 0; i < N; i++) { cin >> X; AVL = Insert(AVL, X); } cout << AVL->Data; return 0; }