AVL树实现异常：中序遍历无法打印全部节点，附插入代码

嘿，我看你在AVL树插入操作后遇到中序遍历漏节点的问题了，结合你给出的代码片段，咱们来梳理几个最可能的原因和解决办法：

1. 核心问题：缺失插入后的平衡调整逻辑 #

AVL树的核心是插入后必须维护树的平衡，你的代码片段在递归插入左子树后就截断了——没有更新节点高度、检查平衡因子，也没有做旋转操作。如果跳过这一步，插入操作会导致树结构失衡，节点的左右指针或父指针指向错误，直接导致中序遍历无法遍历到所有节点。

你需要在递归插入左右子树后，补充以下步骤：

• 更新当前节点的高度
• 计算平衡因子（左子树高度 - 右子树高度）
• 根据平衡因子判断是否失衡，执行对应的旋转（LL/LR/RR/RL）

给你补全这部分的示例代码：

// 辅助函数：获取节点高度，空节点返回0
int getHeight(avl_node* t) {
    return t == NULL ? 0 : t->height;
}

// 辅助函数：计算平衡因子
int getBalance(avl_node* t) {
    return t == NULL ? 0 : getHeight(t->left) - getHeight(t->right);
}

// 右旋转函数
void rightRotate(avl_node* &t) {
    avl_node* leftChild = t->left;
    avl_node* leftRightChild = leftChild->right;

    // 执行旋转
    leftChild->right = t;
    t->left = leftRightChild;

    // 更新高度
    t->height = max(getHeight(t->left), getHeight(t->right)) + 1;
    leftChild->height = max(getHeight(leftChild->left), getHeight(leftChild->right)) + 1;

    // 更新根节点指针
    t = leftChild;
}

// 左旋转函数
void leftRotate(avl_node* &t) {
    avl_node* rightChild = t->right;
    avl_node* rightLeftChild = rightChild->left;

    // 执行旋转
    rightChild->left = t;
    t->right = rightLeftChild;

    // 更新高度
    t->height = max(getHeight(t->left), getHeight(t->right)) + 1;
    rightChild->height = max(getHeight(rightChild->left), getHeight(rightChild->right)) + 1;

    // 更新根节点指针
    t = rightChild;
}

// 补全后的插入函数
void AVL_Tree::insert(const Tree & x, avl_node* & t){
    if(t == NULL){
        // 注意：叶子节点高度建议设为1，和getHeight的空节点返回0逻辑统一
        avl_node* p = new avl_node(x, NULL, NULL, 1);
        t = p;
        ++size;
        cout << "added new node success" << endl;
    } 
    else if(x < t->element){
        cout << " x < t element" << endl;
        insert(x, t->left);
        
        // 插入左子树后，维护平衡
        t->height = max(getHeight(t->left), getHeight(t->right)) + 1;
        int balance = getBalance(t);

        // LL型失衡
        if(balance > 1 && x < t->left->element){
            rightRotate(t);
        }
        // LR型失衡
        if(balance > 1 && x > t->left->element){
            leftRotate(t->left);
            rightRotate(t);
        }
    }
    else if(x > t->element){
        cout << " x > t element" << endl;
        insert(x, t->right);
        
        // 插入右子树后，维护平衡
        t->height = max(getHeight(t->left), getHeight(t->right)) + 1;
        int balance = getBalance(t);

        // RR型失衡
        if(balance < -1 && x > t->right->element){
            leftRotate(t);
        }
        // RL型失衡
        if(balance < -1 && x < t->right->element){
            rightRotate(t->right);
            leftRotate(t);
        }
    }
    else{
        // 重复元素，根据需求处理，比如不插入
        cout << "element already exists" << endl;
    }
}

2. 检查中序遍历的实现是否正确 #

除了插入的问题，也有可能是中序遍历本身写错了。正确的中序遍历逻辑应该是：

void AVL_Tree::inorderTraversal(avl_node* t){
    if(t == NULL){
        return;
    }
    // 先递归左子树
    inorderTraversal(t->left);
    // 访问当前节点
    cout << t->element << " ";
    // 再递归右子树
    inorderTraversal(t->right);
}

如果你的遍历函数漏掉了递归右子树，或者终止条件错误，也会导致打印不全。

3. 节点高度的一致性问题 #

注意你新建节点时的高度设置，要和getHeight函数的逻辑统一。比如如果getHeight对空节点返回0，那叶子节点的高度应该设为1，这样父节点的高度计算才会正确——否则平衡因子的计算会出错，旋转逻辑不触发，最终导致树结构损坏。

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