c语言大厂面试经典题目：二叉树先序遍历（递归与非递归）及C语言实现

先序遍历是二叉树遍历的一种方式，按照根-左子树-右子树的顺序进行访问。以下是递归和非递归方式的C语言实现：

递归实现：

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

// 定义二叉树节点结构
struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

// 递归先序遍历函数
void preorderTraversalRecursive(struct TreeNode* root) {
    if (root != NULL) {
        // 访问当前节点
        printf("%d ", root->data);
        // 递归遍历左子树
        preorderTraversalRecursive(root->left);
        // 递归遍历右子树
        preorderTraversalRecursive(root->right);
    }
}

// 示例：创建一个二叉树
struct TreeNode* createNode(int data) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

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

    // 递归先序遍历
    printf("递归先序遍历结果: ");
    preorderTraversalRecursive(root);

    return 0;
}

非递归实现（使用栈）：

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 100

// 定义二叉树节点结构
struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

// 定义栈结构
struct Stack {
    int top;
    struct TreeNode* items[MAX_STACK_SIZE];
};

// 初始化栈
void initStack(struct Stack* stack) {
    stack->top = -1;
}

// 入栈
void push(struct Stack* stack, struct TreeNode* item) {
    if (stack->top < MAX_STACK_SIZE - 1) {
        stack->items[++stack->top] = item;
    }
}

// 出栈
struct TreeNode* pop(struct Stack* stack) {
    if (stack->top >= 0) {
        return stack->items[stack->top--];
    }
    return NULL;
}

// 非递归先序遍历函数
void preorderTraversalNonRecursive(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }

    struct Stack stack;
    initStack(&stack);
    push(&stack, root);

    printf("非递归先序遍历结果: ");
    while (stack.top >= 0) {
        struct TreeNode* current = pop(&stack);
        printf("%d ", current->data);

        // 先将右子树入栈，再将左子树入栈
        if (current->right != NULL) {
            push(&stack, current->right);
        }
        if (current->left != NULL) {
            push(&stack, current->left);
        }
    }
}

// 示例：创建一个二叉树
struct TreeNode* createNode(int data) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

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

    // 非递归先序遍历
    preorderTraversalNonRecursive(root);

    return 0;
}

这两个示例分别演示了递归和非递归方式进行二叉树的先序遍历。