EC08-增加一个指向双亲结点的 parent 指针，输出所有结点到根结点的路径¶

在二叉树的结点结构中增加一个指向双亲结点的 parent 指针。设计算法，从每个叶结点出发，沿 parent 指针向上遍历到根结点，输出所有结点到根结点的路径。

代码实现¶

C
// 二叉树节点结构定义
typedef struct BTNode {
    char data;                    // 节点数据
    struct BTNode *lchild;        // 左子节点指针
    struct BTNode *rchild;        // 右子节点指针
    struct BTNode *parent;        // 父节点指针
} BTNode, *BiTree;

// 函数 fun：为二叉树的每个节点设置父节点指针
// 参数：p - 当前节点，q - 当前节点的父节点
void fun(BiTree p, BiTree q) {
    // 递归终止条件：如果当前节点为空，则返回
    if (p != NULL) {
        p->parent = q;           // 设置当前节点的父节点指针
        q = p;                   // 更新父节点为当前节点

        // 递归处理左子树和右子树
        fun(p->lchild, q);
        fun(p->rchild, q);
    }
}

// 函数 allpath：输出从每个节点到根节点的路径
// 参数：p - 当前节点
void allpath(BiTree p) {
    // 递归终止条件：如果当前节点为空，则返回
    if (p != NULL) {
        BiTree q = p;            // 从当前节点开始向上追溯

        // 沿着父节点指针向上追溯到根节点，并输出路径
        while (q != NULL) {
            printf("%c ", q->data);  // 输出当前节点数据
            q = q->parent;           // 移动到父节点
        }
        printf("\n");               // 换行，表示一条完整路径

        // 递归处理左子树和右子树的所有节点
        allpath(p->lchild);
        allpath(p->rchild);
    }
}

代码逻辑解析¶

1. 数据结构增强¶

在原有二叉树节点基础上增加 parent 指针： - lchild：指向左子节点 - rchild：指向右子节点
- parent：指向父节点 - 这种结构称为父节点指针二叉树

2. fun 函数 - 设置父节点指针¶

C
// 核心逻辑
p->parent = q;  // 当前节点的父节点设为 q
q = p;          // 更新 q 为当前节点，作为子节点的父节点

遍历方式：前序遍历（根-左-右） - 先为当前节点设置父节点 - 再递归为左右子树节点设置父节点

3. allpath 函数 - 输出路径¶

C
// 路径追溯逻辑
while (q != NULL) {
    printf("%c ", q->data);  // 输出节点数据
    q = q->parent;           // 向父节点移动
}

处理流程： - 对每个节点，从该节点开始向上追溯到根节点 - 输出追溯路径上的所有节点 - 递归处理所有节点

时间复杂度分析¶

1. fun 函数时间复杂度¶

需要访问每个节点 exactly 一次
每次操作为常数时间
时间复杂度：O(n)

2. allpath 函数时间复杂度¶

这是算法的关键部分，需要仔细分析：

设二叉树有 n 个节点，对于每个节点： - 叶子节点：需要追溯到根节点，路径长度为树的高度 h - 内部节点：同样需要追溯到根节点

总追溯步数分析： - 每条从叶子到根的路径上的节点都会被访问 - 如果有 k 个叶子节点，每条路径平均长度为 h - 总追溯步数约为 n × h（在最坏情况下）

但更精确的分析： - 每个节点在所有路径中被访问的次数等于该节点到叶子节点的路径数 - 根节点在所有 n 条路径中都被访问 - 总的访问次数为所有节点深度之和

对于完全二叉树：O(n log n) 对于一般情况：O(n²)（退化为链表时）

3. 总体时间复杂度¶

O(n²)（最坏情况）

空间复杂度分析¶

1. 额外空间使用¶

没有使用额外的数据结构
只使用了常量级别的局部变量

2. 递归调用栈空间¶

递归深度取决于树的高度 h
最好情况（平衡树）：O(log n)
最坏情况（链表）：O(n)

3. 总体空间复杂度¶

O(h)，其中 h 是树的高度在最坏情况下为 O(n)

较难理解部分的说明¶

1. fun 函数的参数传递机制¶

C
// 调用示例
fun(root, NULL); // 根节点的父节点为 NULL

// 递归过程中的参数变化
// 第一层：fun(root, NULL) → root->parent = NULL
// 第二层：fun(root->lchild, root) → root->lchild->parent = root
// 第三层：fun(root->lchild->lchild, root->lchild) → ...

2. 图解说明¶

假设二叉树结构如下：

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

fun 函数执行后：

Text Only
1 2 3 4 5	`A(NULL) // parent = NULL / \ B(A) C(A) // parent = A / / \ D(B) E(C) F(C) // parent 分别指向父节点`

allpath 函数输出：

Text Only
1 2 3 4 5 6	`节点 A: A 节点 B: B A 节点 D: D B A 节点 C: C A 节点 E: E C A 节点 F: F C A`

延伸知识点¶

1. 改进版本 - 使用栈避免递归¶

C
// 非递归版本的路径输出
void allpathIterative(BiTree root) {
    if (root == NULL) return;

    Stack* stack = createStack(); // 假设有栈实现
    push(stack, root);

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

        // 输出从当前节点到根的路径
        BiTree current = node;
        Stack* pathStack = createStack();

        // 收集路径节点
        while (current != NULL) {
            push(pathStack, current);
            current = current->parent;
        }

        // 输出路径
        while (!isEmpty(pathStack)) {
            BiTree pathNode = pop(pathStack);
            printf("%c ", pathNode->data);
        }
        printf("\n");

        // 将子节点入栈
        if (node->rchild) push(stack, node->rchild);
        if (node->lchild) push(stack, node->lchild);
    }
}

2. 路径收集版本¶

C
// 收集所有路径到数组中
void collectAllPaths(BiTree node, char** paths, int* pathCount) {
    if (node == NULL) return;

    // 构造当前节点到根的路径
    char* path = (char*)malloc(MAX_PATH_LENGTH * sizeof(char));
    int len = 0;
    BiTree current = node;

    // 从当前节点向上追溯
    while (current != NULL) {
        path[len++] = current->data;
        current = current->parent;
    }

    // 反转路径（从根到当前节点）
    for (int i = 0; i < len/2; i++) {
        char temp = path[i];
        path[i] = path[len-1-i];
        path[len-1-i] = temp;
    }

    path[len] = '\0';
    paths[*pathCount] = path;
    (*pathCount)++;

    // 递归处理子节点
    collectAllPaths(node->lchild, paths, pathCount);
    collectAllPaths(node->rchild, paths, pathCount);
}

3. 双向遍历应用¶

C
// 利用 parent 指针实现双向遍历
BiTree findLCA(BiTree node1, BiTree node2) {
    // 将 node1 到根的路径标记
    BiTree current = node1;
    while (current != NULL) {
        current->visited = 1; // 假设有标记位
        current = current->parent;
    }

    // 从 node2 向上找第一个被标记的节点
    current = node2;
    while (current != NULL && !current->visited) {
        current = current->parent;
    }

    // 清除标记
    BiTree temp = node1;
    while (temp != NULL) {
        temp->visited = 0;
        temp = temp->parent;
    }

    return current; // 最近公共祖先
}

4. 实际应用场景¶

文件系统路径：显示文件的完整路径
DOM 树遍历：网页元素的 CSS 选择器路径
异常堆栈跟踪：函数调用链的回溯
家族关系分析：人员关系网的追溯
版本控制系统：Git 提交历史的追溯

5. 性能优化建议¶

C
// 缓存路径结果，避免重复计算
typedef struct {
    BiTree node;
    char* cachedPath;
    UT_hash_handle hh; // 假设使用 uthash
} PathCache;

PathCache* pathCache = NULL;

char* getOrComputePath(BiTree node) {
    PathCache* entry;
    HASH_FIND_PTR(pathCache, &node, entry);

    if (entry == NULL) {
        // 计算并缓存路径
        char* path = computePath(node);
        entry = (PathCache*)malloc(sizeof(PathCache));
        entry->node = node;
        entry->cachedPath = path;
        HASH_ADD_PTR(pathCache, node, entry);
    }

    return entry->cachedPath;
}

这种方法体现了数据结构增强的思想，通过增加额外的指针来优化特定操作的性能，是实际开发中常用的技巧。