C语言树状结构遍历

在C语言中，树状结构的遍历主要有三种方式：前序遍历（Pre-order Traversal）、中序遍历（In-order Traversal）和后序遍历（Post-order Traversal）。每种遍历方法的实现方式稍有不同，下面分别介绍这三种遍历方式。

树节点结构

首先，定义一个树节点的结构：

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

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

前序遍历

前序遍历的顺序是：访问根节点、遍历左子树、遍历右子树。

void preOrderTraversal(struct TreeNode* root) {
    if (root == NULL) return;

    printf("%d ", root->data);  // 访问根节点
    preOrderTraversal(root->left);  // 遍历左子树
    preOrderTraversal(root->right); // 遍历右子树
}

中序遍历

中序遍历的顺序是：遍历左子树、访问根节点、遍历右子树。

void inOrderTraversal(struct TreeNode* root) {
    if (root == NULL) return;

    inOrderTraversal(root->left);   // 遍历左子树
    printf("%d ", root->data);      // 访问根节点
    inOrderTraversal(root->right);  // 遍历右子树
}

后序遍历

后序遍历的顺序是：遍历左子树、遍历右子树、访问根节点。

void postOrderTraversal(struct TreeNode* root) {
    if (root == NULL) return;

    postOrderTraversal(root->left);   // 遍历左子树
    postOrderTraversal(root->right);  // 遍历右子树
    printf("%d ", root->data);        // 访问根节点
}

示例

创建一个简单的二叉树并进行遍历示例：

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

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

// 前序遍历函数
void preOrderTraversal(struct TreeNode* root) {
    if (root == NULL) return;

    printf("%d ", root->data);  // 访问根节点
    preOrderTraversal(root->left);  // 遍历左子树
    preOrderTraversal(root->right); // 遍历右子树
}

// 中序遍历函数
void inOrderTraversal(struct TreeNode* root) {
    if (root == NULL) return;

    inOrderTraversal(root->left);   // 遍历左子树
    printf("%d ", root->data);      // 访问根节点
    inOrderTraversal(root->right);  // 遍历右子树
}

// 后序遍历函数
void postOrderTraversal(struct TreeNode* root) {
    if (root == NULL) return;

    postOrderTraversal(root->left);   // 遍历左子树
    postOrderTraversal(root->right);  // 遍历右子树
    printf("%d ", root->data);        // 访问根节点
}

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

// 释放树的内存
void freeTree(struct TreeNode* root) {
    if (root == NULL) return;
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

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("前序遍历: ");
    preOrderTraversal(root);
    printf("\n");

    // 中序遍历
    printf("中序遍历: ");
    inOrderTraversal(root);
    printf("\n");

    // 后序遍历
    printf("后序遍历: ");
    postOrderTraversal(root);
    printf("\n");

    // 释放内存
    freeTree(root);

    return 0;
}

以上代码展示了如何在C语言中实现树的前序、中序和后序遍历。