平衡二叉树c++实现

平衡二叉树是一种自平衡的二叉搜索树，它的左右子树的高度差不超过1。下面是平衡二叉树的C++实现：

#include <iostream>
using namespace std;

// 平衡二叉树结点的定义
struct AVLNode {
    int data;           // 数据
    int height;         // 高度
    AVLNode* left;      // 左子树
    AVLNode* right;     // 右子树
    AVLNode(int val) : data(val), height(1), left(nullptr), right(nullptr) {}
};

// 获取结点高度
int getHeight(AVLNode* node) {
    if (node == nullptr) {
        return 0;
    }
    return node->height;
}

// 获取平衡因子
int getBalanceFactor(AVLNode* node) {
    if (node == nullptr) {
        return 0;
    }
    return getHeight(node->left) - getHeight(node->right);
}

// 右旋
AVLNode* rightRotate(AVLNode* node) {
    AVLNode* leftChild = node->left;
    AVLNode* rightGrandChild = leftChild->right;
    leftChild->right = node;
    node->left = rightGrandChild;
    node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
    leftChild->height = max(getHeight(leftChild->left), getHeight(leftChild->right)) + 1;
    return leftChild;
}

// 左旋
AVLNode* leftRotate(AVLNode* node) {
    AVLNode* rightChild = node->right;
    AVLNode* leftGrandChild = rightChild->left;
    rightChild->left = node;
    node->right = leftGrandChild;
    node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
    rightChild->height = max(getHeight(rightChild->left), getHeight(rightChild->right)) + 1;
    return rightChild;
}

// 插入结点
AVLNode* insert(AVLNode* node, int val) {
    if (node == nullptr) {
        return new AVLNode(val);
    }
    if (val < node->data) {
        node->left = insert(node->left, val);
    } else if (val > node->data) {
        node->right = insert(node->right, val);
    } else {
        return node;
    }
    node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
    int balanceFactor = getBalanceFactor(node);
    if (balanceFactor > 1 && val < node->left->data) {
        return rightRotate(node);
    }
    if (balanceFactor < -1 && val > node->right->data) {
        return leftRotate(node);
    }
    if (balanceFactor > 1 && val > node->left->data) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
    if (balanceFactor < -1 && val < node->right->data) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
    return node;
}

// 中序遍历
void inOrder(AVLNode* node) {
    if (node == nullptr) {
        return;
    }
    inOrder(node->left);
    cout << node->data << " ";
    inOrder(node->right);
}

// 测试
int main() {
    AVLNode* root = nullptr;
    int arr[] = { 9, 5, 10, 0, 6, 11, -1, 1, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    for (int i = 0; i < n; i++) {
        root = insert(root, arr[i]);
    }
    inOrder(root);  // 输出：-1 0 1 2 5 6 9 10 11 
    return 0;
}