输出二叉树中从每个叶子结点到根结点的路径 C语言代码

以下是输出二叉树中从每个叶子节点到根节点的路径的C语言代码：

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树结构体
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 定义栈结构体
struct Stack {
    struct TreeNode **data;   // 存储树节点指针的数组
    int top;    // 栈顶指针
    int size;   // 栈的容量
};

// 初始化栈
struct Stack *stackInit(int size) {
    struct Stack *stack = (struct Stack *)malloc(sizeof(struct Stack));
    stack->data = (struct TreeNode **)malloc(size * sizeof(struct TreeNode *));
    stack->top = -1;
    stack->size = size;
    return stack;
}

// 入栈操作
void stackPush(struct Stack *stack, struct TreeNode *node) {
    if (stack->top == stack->size - 1) return;   // 栈满，无法入栈
    stack->top++;
    stack->data[stack->top] = node;
}

// 出栈操作
struct TreeNode *stackPop(struct Stack *stack) {
    if (stack->top == -1) return NULL;   // 栈空，无法出栈
    struct TreeNode *node = stack->data[stack->top];
    stack->top--;
    return node;
}

// 判断栈是否为空
int isStackEmpty(struct Stack *stack) {
    return stack->top == -1;
}

// 判断节点是否为叶子节点
int isLeafNode(struct TreeNode *node) {
    return node && !node->left && !node->right;
}

// 输出路径
void printPath(struct TreeNode **path, int len) {
    for (int i = len - 1; i >= 0; i--) {
        printf("%d", (*path)->val);
        if (i != 0) printf("->");
        (*path) = (*path)->right;
    }
    printf("\n");
}

// 遍历二叉树，输出所有从叶子节点到根节点的路径
void traverse(struct TreeNode *root) {
    if (!root) return;
    struct Stack *stack = stackInit(1000);   // 初始化栈
    struct TreeNode *path[1000];   // 存储从叶子节点到根节点的路径
    int pathLen = 0;   // 路径长度
    struct TreeNode *prev = NULL;   // 记录上一个访问的节点
    stackPush(stack, root);   // 根节点入栈
    while (!isStackEmpty(stack)) {
        struct TreeNode *node = stack->data[stack->top];
        if (!prev || prev->left == node || prev->right == node) {   // 当前节点是上一个节点的子节点
            if (node->left) stackPush(stack, node->left);   // 左子节点入栈
            if (node->right) stackPush(stack, node->right);   // 右子节点入栈
        } else {
            // 当前节点是上一个节点的父节点，且上一个节点为左子节点或当前节点没有右子节点
            if (isLeafNode(prev)) {
                // 上一个节点是叶子节点，输出路径
                path[pathLen++] = prev;
                printPath(path, pathLen);
                pathLen--;
            }
            stackPop(stack);   // 当前节点出栈
        }
        prev = node;   // 更新上一个访问的节点
    }
    free(stack->data);   // 释放动态分配的内存
    free(stack);
}

int main() {
    // 创建二叉树
    struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->val = 1;
    root->left = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->left->val = 2;
    root->left->left = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->left->left->val = 4;
    root->left->left->left = NULL;
    root->left->left->right = NULL;
    root->left->right = NULL;
    root->right = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->right->val = 3;
    root->right->left = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->right->left->val = 5;
    root->right->left->left = NULL;
    root->right->left->right = NULL;
    root->right->right = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->right->right->val = 6;
    root->right->right->left = NULL;
    root->right->right->right = NULL;

    traverse(root);   // 输出所有从叶子节点到根节点的路径

    // 释放动态分配的内存
    free(root->left->left);
    free(root->left);
    free(root->right->left);
    free(root->right->right);
    free(root->right);
    free(root);

    return 0;
}