如何基于数组实现二叉树的rotateLeft与rotateRight操作

核心问题分析 #

数组存储的二叉树是完全二叉树的层级序列化，节点索引规则为：左孩子i*2+1，右孩子i*2+2。和基于引用的二叉树不同，旋转操作不能只修改几个节点的指针——因为旋转会改变子树的层级结构，导致原有的索引规则不再适用，必须重新构建子树的数组表示并替换原数组对应部分。

解决方案思路 #

通过递归序列化/反序列化子树，实现旋转逻辑：

1. 从原数组中提取需要旋转的子树及相关子节点集合。
2. 按旋转规则重新组合这些子树，生成旋转后的子树数组。
3. 将旋转后的子树数组写回原数组的对应起始位置。

具体实现（C#） #

辅助函数 #

1. 统计子树节点总数

private int CountSubtreeNodes(int?[] tree, int x)
{
    if (x >= tree.Length || tree[x] == null)
        return 0;
    return 1 + CountSubtreeNodes(tree, 2 * x + 1) + CountSubtreeNodes(tree, 2 * x + 2);
}

2. 将子树序列化到临时数组

private void SerializeSubtree(int?[] tree, int x, int?[] dest, int destIndex)
{
    if (x >= tree.Length || tree[x] == null)
    {
        if (destIndex < dest.Length)
            dest[destIndex] = null;
        return;
    }
    dest[destIndex] = tree[x];
    SerializeSubtree(tree, 2 * x + 1, dest, 2 * destIndex + 1);
    SerializeSubtree(tree, 2 * x + 2, dest, 2 * destIndex + 2);
}

3. 将临时数组反序列化回原数组

private void DeserializeSubtree(int?[] src, int srcIndex, int?[] tree, int treeIndex)
{
    if (srcIndex >= src.Length || src[srcIndex] == null)
    {
        if (treeIndex < tree.Length)
            tree[treeIndex] = null;
        return;
    }
    tree[treeIndex] = src[srcIndex];
    DeserializeSubtree(src, 2 * srcIndex + 1, tree, 2 * treeIndex + 1);
    DeserializeSubtree(src, 2 * srcIndex + 2, tree, 2 * treeIndex + 2);
}

左旋实现 #

public void RotateLeft(int?[] tree, int x)
{
    // 边界检查：当前节点为空或无右孩子
    if (x >= tree.Length || tree[x] == null)
        return;
    int y = 2 * x + 2;
    if (y >= tree.Length || tree[y] == null)
        return;

    // 提取所需子树
    // 原节点x的左子树
    int countXLeft = CountSubtreeNodes(tree, 2 * x + 1);
    int heightXLeft = countXLeft == 0 ? 0 : (int)Math.Ceiling(Math.Log2(countXLeft + 1));
    int?[] subXLeft = new int?[(1 << heightXLeft) - 1];
    SerializeSubtree(tree, 2 * x + 1, subXLeft, 0);

    // y的左子树（旋转后成为x的右子树）
    int countT2 = CountSubtreeNodes(tree, 2 * y + 1);
    int heightT2 = countT2 == 0 ? 0 : (int)Math.Ceiling(Math.Log2(countT2 + 1));
    int?[] subT2 = new int?[(1 << heightT2) - 1];
    SerializeSubtree(tree, 2 * y + 1, subT2, 0);

    // y的右子树
    int countYRight = CountSubtreeNodes(tree, 2 * y + 2);
    int heightYRight = countYRight == 0 ? 0 : (int)Math.Ceiling(Math.Log2(countYRight + 1));
    int?[] subYRight = new int?[(1 << heightYRight) - 1];
    SerializeSubtree(tree, 2 * y + 2, subYRight, 0);

    // 计算旋转后子树的总节点数和数组大小
    int totalNodes = 1 + (1 + countXLeft + countT2) + countYRight;
    int rotatedHeight = totalNodes == 0 ? 0 : (int)Math.Ceiling(Math.Log2(totalNodes + 1));
    int?[] rotatedSub = new int?[(1 << rotatedHeight) - 1];

    // 构建旋转后的子树结构
    rotatedSub[0] = tree[y]; // 新根为y
    rotatedSub[1] = tree[x]; // y的左孩子为原x节点
    // 填充x的左子树到rotatedSub的3号位置（x的左孩子索引）
    DeserializeSubtree(subXLeft, 0, rotatedSub, 3);
    // 填充T2到rotatedSub的4号位置（x的右孩子索引）
    DeserializeSubtree(subT2, 0, rotatedSub, 4);
    // 填充y的原右子树到rotatedSub的2号位置（y的右孩子索引）
    DeserializeSubtree(subYRight, 0, rotatedSub, 2);

    // 将旋转后的子树写回原数组的x起始位置
    DeserializeSubtree(rotatedSub, 0, tree, x);
}

右旋实现（对称逻辑） #

public void RotateRight(int?[] tree, int x)
{
    if (x >= tree.Length || tree[x] == null)
        return;
    int y = 2 * x + 1;
    if (y >= tree.Length || tree[y] == null)
        return;

    // 提取所需子树
    int countXRight = CountSubtreeNodes(tree, 2 * x + 2);
    int heightXRight = countXRight == 0 ? 0 : (int)Math.Ceiling(Math.Log2(countXRight + 1));
    int?[] subXRight = new int?[(1 << heightXRight) - 1];
    SerializeSubtree(tree, 2 * x + 2, subXRight, 0);

    int countT2 = CountSubtreeNodes(tree, 2 * y + 2);
    int heightT2 = countT2 == 0 ? 0 : (int)Math.Ceiling(Math.Log2(countT2 + 1));
    int?[] subT2 = new int?[(1 << heightT2) - 1];
    SerializeSubtree(tree, 2 * y + 2, subT2, 0);

    int countYLeft = CountSubtreeNodes(tree, 2 * y + 1);
    int heightYLeft = countYLeft == 0 ? 0 : (int)Math.Ceiling(Math.Log2(countYLeft + 1));
    int?[] subYLeft = new int?[(1 << heightYLeft) - 1];
    SerializeSubtree(tree, 2 * y + 1, subYLeft, 0);

    // 构建旋转后的子树
    int totalNodes = 1 + countYLeft + (1 + countT2 + countXRight);
    int rotatedHeight = totalNodes == 0 ? 0 : (int)Math.Ceiling(Math.Log2(totalNodes + 1));
    int?[] rotatedSub = new int?[(1 << rotatedHeight) - 1];

    rotatedSub[0] = tree[y]; // 新根为y
    rotatedSub[2] = tree[x]; // y的右孩子为原x节点
    // 填充x的右子树到rotatedSub的5号位置（x的右孩子索引）
    DeserializeSubtree(subXRight, 0, rotatedSub, 5);
    // 填充T2到rotatedSub的4号位置（x的左孩子索引）
    DeserializeSubtree(subT2, 0, rotatedSub, 4);
    // 填充y的原左子树到rotatedSub的1号位置（y的左孩子索引）
    DeserializeSubtree(subYLeft, 0, rotatedSub, 1);

    // 写回原数组
    DeserializeSubtree(rotatedSub, 0, tree, x);
}

使用示例 #

针对你提供的原数组[1,4,2,5,6,null,3,null,null,null,null,null,null,10,20]，若要将根节点（索引0，值1）执行左旋，调用RotateLeft(tree, 0)后，原数组会更新为预期的[2,1,3,4,null,10,20,5,6,null,null,null,null,null,null]。

注意事项 #

• 数组大小需足够容纳旋转后的子树，若原数组不足，需提前扩容。
• 递归方式确保了所有层级的子节点都被正确处理，解决了迭代实现时无法遍历所有子节点的问题。

内容的提问来源于stack exchange，提问作者Базакин Егор