EC06-输出从根节点到每个叶子节点的路径¶

代码实现¶

输出从根节点到每个叶子节点的路径（正序输出）¶

C
// 函数 allpath：输出从根节点到每个叶子节点的路径（正序输出）
// 参数：p - 当前节点指针，st - 存储路径的字符数组，top - 栈顶指针
void allpath(BiTree p, char st[], int *top) {
    // 递归终止条件：如果当前节点不为空
    if (p != NULL) {
        // 将当前节点的数据压入路径栈
        st[++(*top)] = p->data;

        // 判断是否为叶子节点（无左右子树）
        if (!p->lchild && !p->rchild) {
            // 输出从根节点到当前叶子节点的完整路径
            for (int i = 0; i <= *top; i++) {
                printf("%c", st[i]);
            }
            printf("\n"); // 换行，便于区分不同路径
        }

        // 递归处理左子树
        allpath(p->lchild, st, top);

        // 递归处理右子树
        allpath(p->rchild, st, top);

        // 回溯：当前节点处理完毕，从路径栈中弹出
        --(*top);
    }
}

输出从每个叶子节点到根节点的路径（逆序输出）¶

C
// 函数 allpath_reverse：输出从每个叶子节点到根节点的路径（逆序输出）
void allpath_reverse(BiTree p, char st[], int* top) {
    // 递归终止条件：如果当前节点不为空
    if (p != NULL) {
        // 将当前节点的数据压入路径栈
        st[++(*top)] = p->data;

        // 判断是否为叶子节点
        if (!p->lchild && !p->rchild) {
            // 输出从当前叶子节点到根节点的路径（逆序）
            for (int i = *top; i >= 0; i--) {
                printf("%c", st[i]);
            }
            printf("\n");
        }

        // 递归处理左子树
        allpath_reverse(p->lchild, st, top);

        // 递归处理右子树
        allpath_reverse(p->rchild, st, top);

        // 回溯：当前节点处理完毕，从路径栈中弹出
        (*top)--;
    }
}

代码逻辑解析¶

1. 基本思路¶

使用回溯法结合深度优先搜索： - 用数组 st[] 模拟栈，存储从根节点到当前节点的路径 - 用指针 top 记录栈顶位置 - 遇到叶子节点时输出完整路径 - 递归返回时进行回溯操作

2. 关键操作步骤¶

路径记录：

C
st[++(*top)] = p->data;  // 前序：进入节点时记录

叶子节点判断：

C
if (!p->lchild && !p->rchild)  // 左右子树都为空

路径输出： - 正序：for (int i = 0; i <= *top; i++) 从根到叶 - 逆序：for (int i = *top; i >= 0; i--) 从叶到根

回溯操作：

C
--(*top);  // 后序：离开节点时撤销记录

时间复杂度分析¶

1. 访问节点次数¶

每个节点都会被访问一次：O(n)
但叶子节点需要输出路径，路径长度平均为树的高度 h

2. 路径输出成本¶

设有 k 个叶子节点，每个路径平均长度为 h
输出所有路径的总成本：O(k × h)

3. 总体时间复杂度¶

O(n + k × h)，其中： - n 是节点总数 - k 是叶子节点数 - h 是树的高度

在最坏情况下（完全二叉树），k ≈ n/2，h ≈ log n，复杂度为 O(n log n)

空间复杂度分析¶

1. 辅助数组空间¶

st[] 数组大小：O(h)，h 为树的高度

2. 递归调用栈¶

递归深度：O(h)

3. 总体空间复杂度¶

O(h)，最坏情况下为 O(n)

较难理解部分的说明¶

1. 回溯机制的理解¶

C
// 执行过程示例：
//        A
//       / \
//      B   C
//     /   / \
//    D   E   F

/*
执行顺序：
1. A入栈 [A]
2. B入栈 [A,B]  
3. D入栈 [A,B,D] → D是叶子，输出路径 A->B->D
4. D出栈 [A,B]   ← 回溯
5. B出栈 [A]     ← 回溯
6. C入栈 [A,C]
7. E入栈 [A,C,E] → E是叶子，输出路径 A->C->E
8. E出栈 [A,C]   ← 回溯
9. F入栈 [A,C,F] → F是叶子，输出路径 A->C->F
10. F出栈 [A,C]  ← 回溯
11. C出栈 [A]    ← 回溯
12. A出栈 []     ← 回溯完成
*/

2. 正序与逆序输出的区别¶

C
// 假设路径为：A -> B -> D
// 正序输出：A B D (从根到叶)
// 逆序输出：D B A (从叶到根)

延伸知识点¶

1. 查找根到指定节点 x 的路径¶

C
bool findPathToX(BiTree p, char st[], int *top, char x) {
    if (p != NULL) {
        st[++(*top)] = p->data; // 将当前节点值存入路径数组
        if (p->data == x) { // 找到目标节点
            for (int i = 0; i <= *top; i++) {
                printf("%c", st[i]); // 输出从根节点到目标节点的路径
            }
            printf("\n");
            return true; // 找到目标节点，返回 true
        }
        // 递归查找左子树或右子树
        if (findPathToX(p->lchild, st, top, x)) return true;
        if (findPathToX(p->rchild, st, top, x)) return true;
        --(*top); // 回溯，移除当前节点
    }
    return false; // 未找到目标节点
}

2. 查找根到所有节点的路径¶

C
void allPathsToAllNodes(BiTree p, char st[], int *top) {
    if (p != NULL) {
        st[++(*top)] = p->data; // 将当前节点值存入路径数组
        // 输出从根节点到当前节点的路径
        for (int i = 0; i <= *top; i++) {
            printf("%c", st[i]);
        }
        printf("\n");
        allPathsToAllNodes(p->lchild, st, top); // 递归处理左子树
        allPathsToAllNodes(p->rchild, st, top); // 递归处理右子树
        --(*top); // 回溯，移除当前节点
    }
}

3. 使用动态数组的版本¶

C
void allpath_dynamic(BiTree p, char* path, int depth) {
    if (p != NULL) {
        // 动态扩展路径数组
        path = realloc(path, (depth + 1) * sizeof(char));
        path[depth] = p->data;

        // 叶子节点处理
        if (!p->lchild && !p->rchild) {
            for (int i = 0; i <= depth; i++) {
                printf("%c", path[i]);
            }
            printf("\n");
        }

        // 递归处理
        allpath_dynamic(p->lchild, path, depth + 1);
        allpath_dynamic(p->rchild, path, depth + 1);
    }
}

4. 非递归版本（使用栈）¶

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

    Stack* nodeStack = createStack();     // 节点栈
    Stack* pathStack = createStack();     // 路径栈
    push(nodeStack, root);
    pushChar(pathStack, root->data);

    while (!isEmpty(nodeStack)) {
        BiTree node = pop(nodeStack);
        char data = popChar(pathStack);

        // 如果是叶子节点，输出路径
        if (!node->lchild && !node->rchild) {
            // 输出路径栈中的内容
            printPath(pathStack);
        }

        // 将子节点入栈
        if (node->rchild) {
            push(nodeStack, node->rchild);
            pushChar(pathStack, node->rchild->data);
        }
        if (node->lchild) {
            push(nodeStack, node->lchild);
            pushChar(pathStack, node->lchild->data);
        }
    }
}

5. 路径相关的重要概念¶

祖先问题分类： - 路径存在性：判断两节点间是否存在路径 - 最短路径：在树中任意两点间路径唯一且最短 - 公共祖先：找两个节点的最近公共祖先 - 路径和：计算路径上节点值的和

6. 实际应用场景¶

文件系统：显示文件的完整路径
决策树：显示到达某个决策的所有条件
家族树：显示血缘关系路径
导航系统：显示路由路径
编译器：显示语法错误的定位路径

7. 算法优化技巧¶

C
// 带剪枝的版本：如果只需要找到一个路径
bool findFirstPath(BiTree p, char st[], int *top, char target) {
    if (p != NULL) {
        st[++(*top)] = p->data;

        if (p->data == target) {
            // 找到目标，输出并返回
            for (int i = 0; i <= *top; i++) {
                printf("%c ", st[i]);
            }
            return true;
        }

        // 剪枝：只要在任意一个子树中找到就立即返回
        if (findFirstPath(p->lchild, st, top, target) || 
            findFirstPath(p->rchild, st, top, target)) {
            return true;
        }

        --(*top); // 回溯
    }
    return false;
}

这个算法是树遍历和回溯法的经典应用，体现了如何通过递归和栈结构来记录和维护路径信息，是解决树中路径相关问题的基础模板。