EC11-层次遍历二叉树并交换每个节点的左右子树¶

代码实现¶

C
// 函数 level：层次遍历二叉树并交换每个节点的左右子树
void level(BiTree bt) {
    // 创建队列用于层次遍历
    BiTree que[maxsize];  // 队列数组
    int front = 0, rear = 0;  // 队列的头指针和尾指针

    // 如果二叉树非空，则开始处理
    if (bt != NULL) {
        que[++rear] = bt;  // 将根节点入队

        // 当队列不为空时继续处理
        while (front != rear) {
            bt = que[++front];  // 出队一个节点

            // 交换当前节点的左右子树
            BiTree temp = bt->lchild;    // 临时保存左子树
            bt->lchild = bt->rchild;     // 将右子树赋给左子树
            bt->rchild = temp;           // 将临时保存的左子树赋给右子树

            // 将交换后的左右子节点入队（注意顺序）
            if (bt->lchild != NULL) {    // 原来的右子树（现在在左边）
                que[++rear] = bt->lchild;
            }
            if (bt->rchild != NULL) {    // 原来的左子树（现在在右边）
                que[++rear] = bt->rchild;
            }
        }
    }
}

代码逻辑解析¶

1. 算法核心思想¶

使用层次遍历（广度优先搜索）访问二叉树的每个节点
对每个访问到的节点，交换其左右子树
利用队列实现层次遍历的先进先出特性

2. 队列操作机制¶

C
// 队列的基本操作
入队：que[++rear] = node;  // 尾指针先自增，然后插入元素
出队：node = que[++front]; // 头指针先自增，然后取出元素
队空条件：front == rear

3. 子树交换过程¶

C
// 交换左右子树的标准三步法
BiTree temp = bt->lchild;  // 1. 保存左子树
bt->lchild = bt->rchild;   // 2. 右子树赋给左子树
bt->rchild = temp;         // 3. 原左子树赋给右子树

4. 遍历顺序¶

层次顺序：从上到下，从左到右
处理顺序：先处理父节点，再处理子节点

时间复杂度分析¶

1. 节点访问次数¶

每个节点恰好被访问一次
每个节点的左右子树交换操作为常数时间

2. 队列操作复杂度¶

入队操作：O(1)
出队操作：O(1)
总的队列操作次数等于节点数

3. 总体时间复杂度¶

O(n)，其中 n 是二叉树中节点的总数

空间复杂度分析¶

1. 队列空间使用¶

队列大小取决于二叉树的宽度
最好情况（完全二叉树）：O(n/2) ≈ O(n)
最坏情况（完全二叉树最后一层）：O(2^h) 其中 h 是树的高度

2. 额外变量空间¶

只使用了常量级别的额外变量（front, rear, temp）

3. 总体空间复杂度¶

O(w)，其中 w 是二叉树的最大宽度在最坏情况下为 O(n)

较难理解部分的说明¶

1. 为什么入队时要检查交换后的子节点？¶

C
// 关键理解：交换后左右子树的位置发生了变化
交换前：左子树在 bt->lchild，右子树在 bt->rchild
交换后：右子树在 bt->lchild，左子树在 bt->rchild

// 因此入队时：
if (bt->lchild != NULL)  // 实际上是原来的右子树
    que[++rear] = bt->lchild;
if (bt->rchild != NULL)  // 实际上是原来的左子树
    que[++rear] = bt->rchild;

2. 图解说明¶

假设原始二叉树：

Text Only
1 2 3 4 5	`A / \ B C / \ / \ D E F G`

处理过程：

Text Only

初始队列：[A]
步骤1：处理 A
- 交换 A 的左右子树：B ↔ C
- 入队 B 和 C（原顺序）
队列：[B, C]

步骤2：处理 B  
- 交换 B 的左右子树：D ↔ E
- 入队 D 和 E（原顺序）
队列：[C, D, E]

步骤3：处理 C
- 交换 C 的左右子树：F ↔ G  
- 入队 F 和 G（原顺序）
队列：[D, E, F, G]

步骤4-7：处理叶子节点 D,E,F,G
- 叶子节点没有子树，交换无效果

最终结果：

Text Only
1 2 3 4 5	`A / \ C B / \ / \ G F E D`

延伸知识点¶

1. 递归版本实现¶

C
// 递归实现镜像翻转
void mirrorRecursive(BiTree root) {
    if (root == NULL) return;

    // 交换当前节点的左右子树
    BiTree temp = root->lchild;
    root->lchild = root->rchild;
    root->rchild = temp;

    // 递归处理左右子树
    mirrorRecursive(root->lchild);
    mirrorRecursive(root->rchild);
}

2. 后序遍历版本¶

C
// 后序遍历实现（自底向上）
void mirrorPostOrder(BiTree root) {
    if (root == NULL) return;

    // 先处理子树
    mirrorPostOrder(root->lchild);
    mirrorPostOrder(root->rchild);

    // 再交换当前节点
    BiTree temp = root->lchild;
    root->lchild = root->rchild;
    root->rchild = temp;
}

3. 非递归栈实现¶

C
// 使用栈的前序遍历实现
void mirrorWithStack(BiTree root) {
    if (root == NULL) return;

    Stack* stack = createStack();
    push(stack, root);

    while (!isEmpty(stack)) {
        BiTree node = pop(stack);

        // 交换左右子树
        BiTree temp = node->lchild;
        node->lchild = node->rchild;
        node->rchild = temp;

        // 注意入栈顺序：先右后左（因为栈是后进先出）
        if (node->rchild != NULL) push(stack, node->rchild);
        if (node->lchild != NULL) push(stack, node->lchild);
    }
}

4. 完整功能版本¶

C
// 带返回值的镜像函数
BiTree mirrorTree(BiTree root) {
    if (root == NULL) return NULL;

    // 创建新节点
    BiTree newRoot = (BiTree)malloc(sizeof(BTNode));
    newRoot->data = root->data;

    // 递归创建镜像子树（左右互换）
    newRoot->lchild = mirrorTree(root->rchild);
    newRoot->rchild = mirrorTree(root->lchild);

    return newRoot;
}

5. 实际应用场景¶

图像处理：图片的水平翻转
界面布局：UI 元素的镜像显示
数据结构转换：将表达式树转换为相反的计算顺序
游戏开发：地图或场景的镜像渲染
编译器优化：语法树的对称变换

6. 算法变体¶

C
// 只交换指定层级的节点
void mirrorLevel(BiTree root, int targetLevel) {
    if (root == NULL || targetLevel < 1) return;

    Queue* queue = createQueue();
    enqueue(queue, root);
    int currentLevel = 1;

    while (!isEmpty(queue) && currentLevel <= targetLevel) {
        int levelSize = size(queue);

        for (int i = 0; i < levelSize; i++) {
            BiTree node = dequeue(queue);

            if (currentLevel == targetLevel) {
                // 交换指定层级的节点
                BiTree temp = node->lchild;
                node->lchild = node->rchild;
                node->rchild = temp;
            } else {
                // 继续入队下一层节点
                if (node->lchild) enqueue(queue, node->lchild);
                if (node->rchild) enqueue(queue, node->rchild);
            }
        }
        currentLevel++;
    }
}

7. 性能对比分析¶

实现方式	时间复杂度	空间复杂度	优点	缺点
层次遍历	O(n)	O(w)	直观易懂	需要额外队列空间
递归前序	O(n)	O(h)	代码简洁	可能栈溢出
递归后序	O(n)	O(h)	自底向上	可能栈溢出
栈实现	O(n)	O(h)	避免递归	代码稍复杂

这个算法体现了层次遍历和树的结构变换的经典应用，是二叉树操作中的基础问题之一。