图书管理系统c++二叉平衡树

二叉平衡树是一种特殊的二叉搜索树，它的左子树和右子树的高度差不超过1。在图书管理系统中，可以使用二叉平衡树来实现动态查找表，用于存储图书的信息。以下是一个示例的C++代码，演示了如何实现图书管理系统中的二叉平衡树：

#include <iostream>
using namespace std;

// 定义二叉平衡树的节点结构
struct Node {
    int key;
    Node* left;
    Node* right;
    int height;
};

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

// 获取两个数中的较大值
int max(int a, int b) {
    return (a > b) ? a : b;
}

// 创建一个新的节点
Node* createNode(int key) {
    Node* newNode = new Node();
    newNode->key = key;
    newNode->left = nullptr;
    newNode->right = nullptr;
    newNode->height = 1;
    return newNode;
}

// 右旋操作
Node* rightRotate(Node* y) {
    Node* x = y->left;
    Node* T2 = x->right;

    // 执行旋转
    x->right = y;
    y->left = T2;

    // 更新节点的高度
    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;

    return x;
}

// 左旋操作
Node* leftRotate(Node* x) {
    Node* y = x->right;
    Node* T2 = y->left;

    // 执行旋转
    y->left = x;
    x->right = T2;

    // 更新节点的高度
    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;

    return y;
}

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

// 插入节点
Node* insertNode(Node* root, int key) {
    // 执行二叉搜索树的插入操作
    if (root == nullptr) {
        return createNode(key);
    }
    if (key < root->key) {
        root->left = insertNode(root->left, key);
    } else if (key > root->key) {
        root->right = insertNode(root->right, key);
    } else {
        return root; // 如果节点已存在，则直接返回
    }

    // 更新节点的高度
    root->height = max(getHeight(root->left), getHeight(root->right)) + 1;

    // 获取节点的平衡因子
    int balanceFactor = getBalanceFactor(root);

    // 平衡维护
    // 左左情况，执行右旋操作
    if (balanceFactor > 1 && key < root->left->key) {
        return rightRotate(root);
    }
    // 右右情况，执行左旋操作
    if (balanceFactor < -1 && key > root->right->key) {
        return leftRotate(root);
    }
    // 左右情况，先对左子树进行左旋操作，再对根节点进行右旋操作
    if (balanceFactor > 1 && key > root->left->key) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }
    // 右左情况，先对右子树进行右旋操作，再对根节点进行左旋操作
    if (balanceFactor < -1 && key < root->right->key) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    return root;
}

// 中序遍历二叉平衡树
void inorderTraversal(Node* root) {
    if (root != nullptr) {
        inorderTraversal(root->left);
        cout << root->key << " ";
        inorderTraversal(root->right);
    }
}

int main() {
    Node* root = nullptr;

    // 插入节点
    root = insertNode(root, 10);
    root = insertNode(root, 20);
    root = insertNode(root, 30);
    root = insertNode(root, 40);
    root = insertNode(root, 50);
    root = insertNode(root, 25);

    // 中序遍历二叉平衡树
    cout << "Inorder traversal of the AVL tree: ";
    inorderTraversal(root);
    cout << endl;

    return 0;
}

这段代码演示了如何使用C++实现一个简单的图书管理系统中的二叉平衡树。你可以根据实际需求进行修改和扩展。