C语言编程题二叉树遍历

1、前序遍历

二叉树的前序遍历是一种遍历策略，按照根节点→左子树→右子树的顺序访问所有节点。这种方法首先访问根节点，然后遍历左子树，最后遍历右子树。

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

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

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 前序遍历
void preorderTraversal(Node* root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

// 释放二叉树节点的内存
void freeTree(Node* root) {
    if (root == NULL) return;
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

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

    // 输出前序遍历结果
    printf("前序遍历: ");
    preorderTraversal(root);
    printf("\n");

    // 释放内存
    freeTree(root);

    return 0;
}

2、中序遍历

二叉树的中序遍历（Inorder traversal）是另一种深度优先的遍历方法，其遍历顺序为：先遍历左子树，然后访问根节点，最后遍历右子树。中序遍历对于二叉搜索树特别有用，因为这种遍历方式会按照节点的键值（Key）升序访问所有节点。

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

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

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 中序遍历
void inorderTraversal(Node* root) {
    if (root == NULL) return;
    inorderTraversal(root->left);
    printf("%d ", root->data);
    inorderTraversal(root->right);
}

// 释放二叉树节点的内存
void freeTree(Node* root) {
    if (root == NULL) return;
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

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

    // 输出中序遍历结果
    printf("中序遍历: ");
    inorderTraversal(root);
    printf("\n");

    // 释放内存
    freeTree(root);

    return 0;
}

3、后序遍历

二叉树的后序遍历（Postorder traversal）是一种深度优先的遍历方法，主要特点是首先遍历所有子节点，最后才访问根节点。首先递归地后序遍历左子树，然后递归地后序遍历右子树，最后访问当前的根节点。

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

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

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 后序遍历
void postorderTraversal(Node* root) {
    if (root == NULL) return;
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    printf("%d ", root->data);
}

// 释放二叉树节点的内存
void freeTree(Node* root) {
    if (root == NULL) return;
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

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

    // 输出后序遍历结果
    printf("后序遍历: ");
    postorderTraversal(root);
    printf("\n");

    // 释放内存
    freeTree(root);

    return 0;
}