用c++实现平衡二叉树的生成插入和删除

平衡二叉树是一种特殊的二叉搜索树，它的左右子树的高度差不超过1。常见的平衡二叉树有AVL树、红黑树等。

以下是用C++实现平衡二叉树的生成、插入和删除的示例代码：

#include <iostream>

using namespace std;

// 定义平衡二叉树节点结构体
struct Node {
    int value;
    int height;
    Node* left;
    Node* right;
    Node(int v) : value(v), height(1), left(nullptr), right(nullptr) {}
};

// 获取节点高度
int getHeight(Node* node) {
    return node ? node->height : 0;
}

// 获取节点平衡因子
int getBalanceFactor(Node* node) {
    return node ? getHeight(node->left) - getHeight(node->right) : 0;
}

// 更新节点高度
void updateHeight(Node* node) {
    node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
}

// 左旋
Node* leftRotate(Node* node) {
    Node* newRoot = node->right;
    node->right = newRoot->left;
    newRoot->left = node;
    updateHeight(node);
    updateHeight(newRoot);
    return newRoot;
}

// 右旋
Node* rightRotate(Node* node) {
    Node* newRoot = node->left;
    node->left = newRoot->right;
    newRoot->right = node;
    updateHeight(node);
    updateHeight(newRoot);
    return newRoot;
}

// 平衡节点
Node* balance(Node* node) {
    if (!node) return nullptr;
    updateHeight(node);
    int bf = getBalanceFactor(node);
    if (bf > 1) {
        if (getBalanceFactor(node->left) < 0) {
            node->left = leftRotate(node->left);
        }
        return rightRotate(node);
    } else if (bf < -1) {
        if (getBalanceFactor(node->right) > 0) {
            node->right = rightRotate(node->right);
        }
        return leftRotate(node);
    }
    return node;
}

// 插入节点
Node* insertNode(Node* root, int value) {
    if (!root) {
        return new Node(value);
    }
    if (value < root->value) {
        root->left = insertNode(root->left, value);
    } else {
        root->right = insertNode(root->right, value);
    }
    return balance(root);
}

// 查找节点
Node* searchNode(Node* root, int value) {
    if (!root) return nullptr;
    if (root->value == value) {
        return root;
    } else if (value < root->value) {
        return searchNode(root->left, value);
    } else {
        return searchNode(root->right, value);
    }
}

// 查找最小节点
Node* findMinNode(Node* root) {
    while (root->left) {
        root = root->left;
    }
    return root;
}

// 删除节点
Node* deleteNode(Node* root, int value) {
    if (!root) return nullptr;
    if (value < root->value) {
        root->left = deleteNode(root->left, value);
    } else if (value > root->value) {
        root->right = deleteNode(root->right, value);
    } else {
        if (!root->left && !root->right) {
            delete root;
            root = nullptr;
        } else if (!root->left || !root->right) {
            Node* child = root->left ? root->left : root->right;
            *root = *child;
            delete child;
        } else {
            Node* minNode = findMinNode(root->right);
            root->value = minNode->value;
            root->right = deleteNode(root->right, minNode->value);
        }
    }
    return balance(root);
}

// 中序遍历
void inOrderTraversal(Node* root) {
    if (!root) return;
    inOrderTraversal(root->left);
    cout << root->value << " ";
    inOrderTraversal(root->right);
}

int main() {
    Node* root = nullptr;
    root = insertNode(root, 5);
    root = insertNode(root, 2);
    root = insertNode(root, 8);
    root = insertNode(root, 1);
    root = insertNode(root, 4);
    root = insertNode(root, 6);
    root = insertNode(root, 9);
    root = insertNode(root, 3);
    root = insertNode(root, 7);
    inOrderTraversal(root); // 1 2 3 4 5 6 7 8 9
    cout << endl;
    root = deleteNode(root, 5);
    inOrderTraversal(root); // 1 2 3 4 6 7 8 9
    cout << endl;
    return 0;
}

以上代码实现了平衡二叉树的生成、插入和删除功能，并且采用了AVL算法来保证树的平衡。其中，balance函数用来平衡节点，insertNode函数用来插入节点，searchNode函数用来查找节点，findMinNode函数用来查找最小节点，deleteNode函数用来删除节点，inOrderTraversal函数用来中序遍历树。