EC05-将二叉树的叶子节点从左到右连接成单链表¶

代码实现¶

C
// 函数 link：将二叉树的叶子节点从左到右连接成单链表
// 参数：p - 当前处理的节点，head - 指向链表头节点的指针，tail - 指向链表尾节点的指针
void link(BiTree p, BiTree *head, BiTree *tail) {
    // 递归终止条件：如果当前节点为空，则返回
    if (p != NULL) {
        // 递归处理左子树
        link(p->lchild, head, tail);

        // 递归处理右子树
        link(p->rchild, head, tail);

        // 判断当前节点是否为叶子节点
        if (!p->lchild && !p->rchild) {
            // 如果是叶子节点，则将其加入链表

            if (*head == NULL) {
                // 如果链表为空，当前节点成为链表的第一个节点
                *head = p;  // 设置头节点
                *tail = p;  // 设置尾节点
            } else {
                // 如果链表不为空，将当前节点连接到链表末尾
                (*tail)->rchild = p;  // 将原尾节点的右指针指向当前节点
                p->lchild = *tail;    // 将当前节点的左指针指向前一个节点（形成双向连接）
                *tail = p;            // 更新尾节点为当前节点
            }
        }
    }
}

代码逻辑解析¶

1. 叶子节点定义¶

叶子节点：没有左右子树的节点（p->lchild == NULL && p->rchild == NULL）

2. 算法思路¶

使用后序遍历（左子树 → 右子树 → 根节点）
确保按照从左到右的顺序处理叶子节点
将所有叶子节点通过 rchild 指针连接成单链表

3. 链表构建策略¶

首次连接：第一个叶子节点同时成为链表的头节点和尾节点
后续连接：
将原尾节点的 rchild 指向新叶子节点
将新叶子节点的 lchild 指向前一个节点（形成双向连接）
更新尾节点指针

4. 指针操作说明¶

C
// 双向连接的建立
(*tail)->rchild = p;  // 前一个节点指向当前节点
p->lchild = *tail;    // 当前节点指向前一个节点
*tail = p;            // 更新尾节点

时间复杂度分析¶

1. 节点访问次数¶

算法需要访问二叉树中的每个节点 exactly 一次
设二叉树有 n 个节点，则需要进行 n 次节点处理

2. 每次操作复杂度¶

节点判断（是否为叶子节点）：O(1)
指针操作（链表连接）：O(1)
递归调用开销：O(1)

3. 总体时间复杂度¶

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

空间复杂度分析¶

1. 额外空间使用¶

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

2. 递归调用栈空间¶

递归深度取决于二叉树的高度
最好情况（完全二叉树）：O(log n)
最坏情况（退化为链表）：O(n)

3. 总体空间复杂度¶

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

较难理解部分的说明¶

1. 为什么使用后序遍历？¶

C
// 错误的前序遍历方式
void link_preorder(BiTree p, BiTree *head, BiTree *tail) {
    if (p != NULL) {
        if (!p->lchild && !p->rchild) {
            // 这样会导致叶子节点顺序混乱
            // 因为根节点在左右子树之前被处理
        }
        link_preorder(p->lchild, head, tail);
        link_preorder(p->rchild, head, tail);
    }
}

// 正确的后序遍历方式
void link_postorder(BiTree p, BiTree *head, BiTree *tail) {
    if (p != NULL) {
        link_postorder(p->lchild, head, tail);   // 先处理左子树
        link_postorder(p->rchild, head, tail);   // 再处理右子树
        if (!p->lchild && !p->rchild) {          // 最后处理根节点
            // 这样确保叶子节点按从左到右的顺序被处理
        }
    }
}

2. 图解说明¶

假设二叉树结构如下：

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

叶子节点：D, G, F（从左到右）

遍历过程（后序）：

Text Only

访问顺序：D → B → G → E → F → C → A
叶子处理顺序：D → G → F

链表构建过程：
1. 处理 D：head = D, tail = D
   链表：D

2. 处理 G：tail->rchild = G, G->lchild = D, tail = G
   链表：D ↔ G

3. 处理 F：tail->rchild = F, F->lchild = G, tail = F
   链表：D ↔ G ↔ F

最终结果：
head -> D
D->rchild = G, G->lchild = D
G->rchild = F, F->lchild = G
tail -> F

延伸知识点¶

1. 单向链表版本¶

C
// 只使用右指针构建单向链表
void link_single(BiTree p, BiTree *head, BiTree *tail) {
    if (p != NULL) {
        link_single(p->lchild, head, tail);
        link_single(p->rchild, head, tail);

        if (!p->lchild && !p->rchild) {
            if (*head == NULL) {
                *head = p;
                *tail = p;
            } else {
                (*tail)->rchild = p;
                *tail = p;
            }
        }
    }
}

2. 使用返回值的方式¶

C
// 返回链表的头节点
BiTree link_return(BiTree p) {
    if (p == NULL) return NULL;

    // 递归处理子树
    BiTree left_head = link_return(p->lchild);
    BiTree right_head = link_return(p->rchild);

    // 如果当前节点是叶子节点
    if (!p->lchild && !p->rchild) {
        p->rchild = left_head ? left_head : right_head;
        return p;
    }

    // 连接左右子树的结果
    if (left_head) {
        BiTree temp = left_head;
        while (temp->rchild) temp = temp->rchild;
        temp->rchild = right_head;
        return left_head;
    }

    return right_head;
}

3. 迭代版本（使用栈）¶

C
void link_iterative(BiTree root, BiTree *head, BiTree *tail) {
    if (root == NULL) return;

    *head = NULL;
    *tail = NULL;

    // 使用两个栈模拟后序遍历
    Stack* stack1 = createStack();
    Stack* stack2 = createStack();

    push(stack1, root);

    // 后序遍历的第一步：获得后序序列
    while (!isEmpty(stack1)) {
        BiTree node = pop(stack1);
        push(stack2, node);

        if (node->lchild) push(stack1, node->lchild);
        if (node->rchild) push(stack1, node->rchild);
    }

    // 按后序顺序处理节点
    while (!isEmpty(stack2)) {
        BiTree node = pop(stack2);
        if (!node->lchild && !node->rchild) {
            if (*head == NULL) {
                *head = node;
                *tail = node;
            } else {
                (*tail)->rchild = node;
                node->lchild = *tail;
                *tail = node;
            }
        }
    }
}

4. 扩展应用¶

叶子节点计数¶

C
int countLeaves(BiTree p) {
    if (p == NULL) return 0;
    if (!p->lchild && !p->rchild) return 1;
    return countLeaves(p->lchild) + countLeaves(p->rchild);
}

叶子节点值求和¶

C
int sumLeaves(BiTree p) {
    if (p == NULL) return 0;
    if (!p->lchild && !p->rchild) return p->data;
    return sumLeaves(p->lchild) + sumLeaves(p->rchild);
}

5. 实际应用场景¶

表达式树：将表达式树的叶子节点（操作数）连接起来
文件系统：遍历目录树，将所有文件（叶子节点）连接成列表
语法分析：将语法树中的终结符节点连接起来
数据序列化：按特定顺序提取树中的数据节点

6. 算法优化技巧¶

C
// 带早期终止的优化版本
void link_optimized(BiTree p, BiTree *head, BiTree *tail, int *leaf_count) {
    if (p != NULL) {
        link_optimized(p->lchild, head, tail, leaf_count);
        link_optimized(p->rchild, head, tail, leaf_count);

        if (!p->lchild && !p->rchild) {
            (*leaf_count)++;
            if (*head == NULL) {
                *head = p;
                *tail = p;
            } else {
                (*tail)->rchild = p;
                p->lchild = *tail;
                *tail = p;
            }
        }
    }
}

这个算法体现了树的后序遍历和链表构建的结合，是树操作中的经典问题。通过后序遍历确保了叶子节点按从左到右的正确顺序被处理，同时利用树节点的指针域直接构建链表，避免了额外的空间开销。