EC10-实现二叉树自下而上、从右到左的层次遍历¶

代码实现¶

C
// 函数 level：实现二叉树自下而上、从右到左的层次遍历
void level(BiTree bt) {
    BiTree que[maxsize]; // 队列，用于层次遍历
    BiTree st[maxsize];  // 栈，用于逆序存储节点
    int front = 0, rear = 0; // 队列的头尾指针
    int top = -1;            // 栈顶指针

    if (bt != NULL) {
        que[++rear] = bt; // 将根节点入队

        // 层次遍历二叉树（自上而下、从左到右）
        while (front != rear) {
            bt = que[++front]; // 出队一个节点
            st[++top] = bt;    // 将该节点压入栈中

            // 注意：先将左子节点入队，再将右子节点入队
            if (bt->lchild != NULL) {
                que[++rear] = bt->lchild;
            }
            if (bt->rchild != NULL) {
                que[++rear] = bt->rchild;
            }
        }

        // 从栈中依次弹出节点并输出，实现自下而上、从右到左的顺序
        while (top != -1) {
            printf("%c ", st[top--]->data); // 弹出栈顶元素并输出
        }
    }
}

代码逻辑解析¶

1. 问题描述¶

目标：实现二叉树的层次遍历，但要求按 自下而上、从右到左 的顺序输出。
方法：
利用队列进行标准的层次遍历（自上而下、从左到右）。
利用栈逆序存储遍历结果，最终实现目标顺序。

2. 算法思路¶

（1）层次遍历部分¶

使用队列 que 实现标准的层次遍历。
按照 自上而下、从左到右 的顺序访问每个节点，并将节点按访问顺序存入栈 st 中。

（2）逆序输出部分¶

由于栈是后进先出的数据结构，因此将层次遍历的结果存入栈中后，再依次弹出即可得到 自下而上、从右到左 的顺序。

3. 数据结构选择¶

队列 que：用于实现标准的层次遍历。
栈 st：用于逆序存储节点，从而实现目标顺序。

4. 遍历顺序分析¶

假设二叉树如下：

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

层次遍历顺序（自上而下、从左到右）：

Text Only
1	`A → B → C → D → E → F`

存入栈中的顺序：

Text Only
1 2 3 4 5 6	`F (栈顶) E D C B A (栈底)`

弹出栈后的输出顺序（自下而上、从右到左）：

Text Only
1	`F → E → D → C → B → A`

时间复杂度分析¶

1. 层次遍历部分¶

每个节点恰好入队一次，出队一次。
时间复杂度为 O(n)，其中 n 是节点总数。

2. 栈操作部分¶

每个节点恰好入栈一次，出栈一次。
时间复杂度为 O(n)。

3. 总体时间复杂度¶

O(n) - 线性时间复杂度

空间复杂度分析¶

1. 队列和栈的空间使用¶

队列 que 和栈 st 各需要存储 n 个节点。
总空间复杂度为 O(n)。

2. 递归调用栈¶

该算法没有递归调用，不需要额外的调用栈空间。

3. 总体空间复杂度¶

O(n)

较难理解部分的说明¶

1. 为什么要用栈？¶

在标准的层次遍历中，节点是按照 自上而下、从左到右 的顺序访问的。为了实现目标顺序（自下而上、从右到左），需要对遍历结果进行逆序处理。栈的后进先出特性正好满足这一需求。

图解说明¶

假设二叉树如下：

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

层次遍历过程： - 第一层：A 入队 → A 出队 → A 入栈 - 第二层：B、C 入队 → B 出队 → B 入栈 → C 出队 → C 入栈 - 第三层：D、E、F 入队 → D 出队 → D 入栈 → E 出队 → E 入栈 → F 出队 → F 入栈

栈的状态：

Text Only
1 2 3 4 5 6	`栈顶：F E D C B 栈底：A`

弹出栈的顺序：

Text Only
1	`F → E → D → C → B → A`

2. 为什么先入队左子节点？¶

在层次遍历中，先入队左子节点是为了保证 自上而下、从左到右 的顺序。这样可以确保栈中存储的节点顺序与目标顺序一致。

延伸知识点¶

1. 其他逆序层次遍历方法¶

方法一：双端队列¶

C
void levelWithDeque(BiTree bt) {
    BiTree deque[maxsize];
    int front = 0, rear = 0;

    if (bt != NULL) {
        deque[rear++] = bt;

        while (front != rear) {
            bt = deque[front++];
            printf("%c ", bt->data);

            // 先入队右子节点，再入队左子节点
            if (bt->rchild != NULL) {
                deque[rear++] = bt->rchild;
            }
            if (bt->lchild != NULL) {
                deque[rear++] = bt->lchild;
            }
        }
    }
}

方法二：递归实现¶

C
void reverseLevelOrder(BiTree root) {
    if (root == NULL) return;

    // 获取树的高度
    int height = getHeight(root);

    // 从最后一层开始，逐层打印
    for (int i = height; i >= 1; i--) {
        printGivenLevel(root, i);
    }
}

void printGivenLevel(BiTree root, int level) {
    if (root == NULL) return;
    if (level == 1) {
        printf("%c ", root->data);
    } else if (level > 1) {
        printGivenLevel(root->rchild, level - 1);
        printGivenLevel(root->lchild, level - 1);
    }
}

int getHeight(BiTree node) {
    if (node == NULL) return 0;
    else {
        int lHeight = getHeight(node->lchild);
        int rHeight = getHeight(node->rchild);
        return (lHeight > rHeight ? lHeight : rHeight) + 1;
    }
}

2. 实际应用场景¶

文件系统：显示目录结构的逆序层次
组织架构：显示层级关系的逆序视图
网络拓扑：显示路由器连接关系的逆序
渲染引擎：从底层到顶层绘制图形

3. 性能优化建议¶

（1）动态数组替代固定大小数组¶

C
// 动态分配队列和栈
BiTree* que = (BiTree*)malloc(sizeof(BiTree) * maxsize);
BiTree* st = (BiTree*)malloc(sizeof(BiTree) * maxsize);

（2）避免重复计算¶

C
// 缓存节点高度，避免重复递归
int* heights = (int*)malloc(sizeof(int) * max_nodes);
memset(heights, -1, sizeof(int) * max_nodes);

int getNodeHeight(BiTree node) {
    if (node == NULL) return 0;
    if (heights[node->id] != -1) return heights[node->id];
    int lHeight = getNodeHeight(node->lchild);
    int rHeight = getNodeHeight(node->rchild);
    heights[node->id] = (lHeight > rHeight ? lHeight : rHeight) + 1;
    return heights[node->id];
}

这种方法体现了利用辅助数据结构实现逆序处理的思想，通过队列和栈的结合巧妙实现了复杂的遍历需求，是算法设计中的经典技巧之一。