如何用C++实现每个节点关联另一棵AVL树的AVL树结构

嗨，我来帮你搞定这个嵌套AVL树的实现！咱们从需求拆解到代码落地一步步来，保证你能看懂～

首先得明确这个「树中树」的核心逻辑：

• 外层AVL树：每个节点存储input.txt第一列的数字，并且每个节点会关联一棵独立的AVL树。
• 内层AVL树：对应外层节点的第二列数字集合，每个外层节点的内层树只存自己对应的第二列数据。

为了复用代码，咱们用模板实现通用的AVL树，这样不管是第一列还是第二列的数字，都能共用一套AVL树的插入、平衡逻辑。

先写通用的AVL节点和树类，这是整个结构的核心：

#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <algorithm> // 用于max函数

using namespace std;

// 通用AVL节点模板
template <typename T>
struct AVLNode {
    T key;
    AVLNode* left;
    AVLNode* right;
    int height;

    AVLNode(T val) : key(val), left(nullptr), right(nullptr), height(1) {}
};

// 通用AVL树模板类
template <typename T>
class AVLTree {
private:
    AVLNode<T>* root;

    // 获取节点高度，空节点高度为0
    int height(AVLNode<T>* node) {
        return node ? node->height : 0;
    }

    // 计算平衡因子：左子树高度 - 右子树高度
    int getBalanceFactor(AVLNode<T>* node) {
        return node ? height(node->left) - height(node->right) : 0;
    }

    // 右旋转操作，修复左左型失衡
    AVLNode<T>* rightRotate(AVLNode<T>* y) {
        AVLNode<T>* x = y->left;
        AVLNode<T>* T2 = x->right;

        x->right = y;
        y->left = T2;

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

        return x;
    }

    // 左旋转操作，修复右右型失衡
    AVLNode<T>* leftRotate(AVLNode<T>* x) {
        AVLNode<T>* y = x->right;
        AVLNode<T>* T2 = y->left;

        y->left = x;
        x->right = T2;

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

        return y;
    }

    // 递归插入节点，同时维护AVL树的平衡
    AVLNode<T>* insertRecursive(AVLNode<T>* node, T key) {
        // 第一步：普通BST插入逻辑
        if (!node) return new AVLNode<T>(key);

        if (key < node->key)
            node->left = insertRecursive(node->left, key);
        else if (key > node->key)
            node->right = insertRecursive(node->right, key);
        else // 不允许重复key，若需要支持重复可修改此处逻辑
            return node;

        // 第二步：更新当前节点的高度
        node->height = 1 + max(height(node->left), height(node->right));

        // 第三步：计算平衡因子，判断是否失衡
        int balance = getBalanceFactor(node);

        // 四种失衡情况的修复
        // 左左型
        if (balance > 1 && key < node->left->key)
            return rightRotate(node);

        // 右右型
        if (balance < -1 && key > node->right->key)
            return leftRotate(node);

        // 左右型
        if (balance > 1 && key > node->left->key) {
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }

        // 右左型
        if (balance < -1 && key < node->right->key) {
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }

        return node;
    }

    // 递归查找节点
    AVLNode<T>* searchRecursive(AVLNode<T>* node, T key) {
        if (!node || node->key == key)
            return node;

        if (key < node->key)
            return searchRecursive(node->left, key);
        else
            return searchRecursive(node->right, key);
    }

    // 递归中序遍历（用于测试）
    void inorderRecursive(AVLNode<T>* node) {
        if (node) {
            inorderRecursive(node->left);
            cout << node->key << " ";
            inorderRecursive(node->right);
        }
    }

    // 递归释放内存
    void deleteRecursive(AVLNode<T>* node) {
        if (node) {
            deleteRecursive(node->left);
            deleteRecursive(node->right);
            delete node;
        }
    }

public:
    AVLTree() : root(nullptr) {}

    ~AVLTree() {
        deleteRecursive(root);
    }

    // 对外的插入接口
    void insert(T key) {
        root = insertRecursive(root, key);
    }

    // 对外的查找接口
    AVLNode<T>* search(T key) {
        return searchRecursive(root, key);
    }

    // 中序遍历输出（升序）
    void inorderTraversal() {
        inorderRecursive(root);
        cout << endl;
    }

    // 获取根节点，用于自定义遍历
    AVLNode<T>* getRoot() {
        return root;
    }
};

外层节点需要同时存储第一列数字和对应的内层AVL树，咱们定义一个结构体，并且重载比较运算符（因为AVL树需要比较节点大小）：

struct OuterNodeData {
    int firstCol;
    AVLTree<int> innerTree; // 存储对应第二列的数字

    // 重载比较运算符，让AVL树可以按第一列数字排序
    bool operator<(const OuterNodeData& other) const {
        return firstCol < other.firstCol;
    }

    bool operator>(const OuterNodeData& other) const {
        return firstCol > other.firstCol;
    }

    bool operator==(const OuterNodeData& other) const {
        return firstCol == other.firstCol;
    }
};

接下来是核心的文件读取和树构建逻辑：逐行读取两个数字，判断外层树中是否存在对应第一列的节点，存在则插入第二列数字到内层树，不存在则新建外层节点并插入：

int main() {
    AVLTree<OuterNodeData> outerTree;
    ifstream inputFile("input.txt");
    string line;

    if (!inputFile.is_open()) {
        cerr << "无法打开input.txt文件，请检查路径是否正确！" << endl;
        return 1;
    }

    while (getline(inputFile, line)) {
        istringstream iss(line);
        int first, second;
        if (iss >> first >> second) {
            // 构造用于查找的临时数据
            OuterNodeData searchData;
            searchData.firstCol = first;

            // 在外层树中查找是否存在该第一列数字
            AVLNode<OuterNodeData>* foundNode = outerTree.search(searchData);

            if (foundNode) {
                // 找到对应节点，将第二列数字插入内层树
                foundNode->key.innerTree.insert(second);
            } else {
                // 未找到，新建外层节点并插入
                OuterNodeData newData;
                newData.firstCol = first;
                newData.innerTree.insert(second);
                outerTree.insert(newData);
            }
        } else {
            cerr << "跳过无效行：" << line << endl;
        }
    }

    inputFile.close();

    // 测试：遍历外层树，同时输出每个节点的内层树数据
    auto traverseNestedTree = [](AVLNode<OuterNodeData>* node) {
        if (!node) return;
        traverseNestedTree(node->left);
        cout << "第一列数字：" << node->key.firstCol << "，对应的第二列数字：";
        node->key.innerTree.inorderTraversal();
        traverseNestedTree(node->right);
    };

    cout << "嵌套AVL树的内容：" << endl;
    traverseNestedTree(outerTree.getRoot());

    return 0;
}

• 重复值处理：当前代码不允许AVL树中存在重复key，如果你的需求支持第一列或第二列有重复数字，可以修改insertRecursive函数，比如允许重复插入，或者在节点中添加计数字段统计重复次数。
• 内存管理：代码中已经实现了AVL树的析构函数，会递归释放所有节点内存，避免内存泄漏。
• 类型扩展：如果第一列或第二列不是int类型，只需修改模板参数，同时确保对应类型重载了比较运算符即可。
• 性能优化：如果input.txt数据量极大，可以考虑将递归插入改为迭代式，避免栈溢出；也可以先批量读取所有数据再构建树，减少IO开销。

内容的提问来源于stack exchange，提问作者lefteris