Binary Search Tree左旋转异常求助：测试结果与预期不符

问题定位 #

你的左旋转逻辑存在多处关键错误，直接导致节点引用丢失、循环引用以及根节点未正确更新，最终出现遍历结果缺失的问题：

1. 父节点引用赋值顺序错误 #

在左旋转代码中，先执行parent.parent = child再执行child.parent = parent.parent——此时parent.parent已经指向child，导致child.parent指向自身，形成循环引用，破坏树结构。

2. 未处理父节点为右子节点的情况 #

仅判断了parent.isLeftChild()的场景，未处理parent作为右子节点的情况，导致grandparent无法正确指向新的子节点child，部分节点脱离树结构。

3. 根节点旋转后未更新 #

左旋转时未处理parent是根节点的场景，新的根节点child无法被设置为树的根，遍历仍从旧根开始，丢失右子树部分节点。

4. 子树节点的父引用未更新 #

移动child的左子树到parent的右子树时，未设置该子树节点的父引用为parent，导致这部分节点的父关系错误。

修复后的旋转方法 #

private void rotate(Node<T> child, Node<T> parent) throws IllegalArgumentException {
    // 右旋转：child是parent的左孩子
    if(child == parent.leftChild) {
        Node<T> childRightSubtree = child.rightChild;
        Node<T> grandparent = parent.parent;

        // 将child的右子树挂载到parent的左子树
        parent.leftChild = childRightSubtree;
        if(childRightSubtree != null) {
            childRightSubtree.parent = parent;
        }

        // 调整parent与child的父子关系
        parent.parent = child;
        child.rightChild = parent;

        // 处理grandparent与child的关系
        child.parent = grandparent;
        if(grandparent != null) {
            if(parent.isLeftChild()) {
                grandparent.leftChild = child;
            } else {
                grandparent.rightChild = child;
            }
        } else {
            // parent是根节点，更新root
            root = child;
            child.parent = null;
        }
    }
    // 左旋转：child是parent的右孩子
    else if(child == parent.rightChild) {
        Node<T> childLeftSubtree = child.leftChild;
        Node<T> grandparent = parent.parent;

        // 将child的左子树挂载到parent的右子树
        parent.rightChild = childLeftSubtree;
        if(childLeftSubtree != null) {
            childLeftSubtree.parent = parent;
        }

        // 调整parent与child的父子关系
        parent.parent = child;
        child.leftChild = parent;

        // 处理grandparent与child的关系
        child.parent = grandparent;
        if(grandparent != null) {
            if(parent.isLeftChild()) {
                grandparent.leftChild = child;
            } else {
                grandparent.rightChild = child;
            }
        } else {
            // parent是根节点，更新root
            root = child;
            child.parent = null;
        }
    }
    // 非法参数处理
    else {
        throw new IllegalArgumentException("Child and parent are not in valid parent-child relationship");
    }
}

验证 #

运行你的test4测试用例：

• 插入序列：2,1,4,3,6,5,7
• 执行左旋转rotate(test.root.rightChild, test.root)
• 修复后层序遍历结果应为：[ 4, 2, 6, 1, 3, 5, 7 ]，与预期一致。

额外优化建议 #

• 变量命名更具语义化（如childLeftSubtree替代left），避免混淆
• 提取左右旋转中重复的逻辑（如grandparent的处理），减少代码冗余

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