二叉树遍历算法详解：先序、中序、后序遍历及C语言实现

引言

二叉树是一种重要的数据结构，在计算机科学领域有着广泛的应用。遍历二叉树是常见的操作之一，它指的是按照一定的规则访问二叉树中的每个节点，并且每个节点只被访问一次。

本文将介绍二叉树的三种基本遍历方式：先序遍历、中序遍历和后序遍历，并提供使用C语言实现的代码示例，帮助你理解和掌握二叉树遍历算法。

二叉树的遍历方式

1. 先序遍历 (Preorder Traversal)

先序遍历的规则是：

1. 访问根节点。
2. 先序遍历左子树。
3. 先序遍历右子树。

2. 中序遍历 (Inorder Traversal)

中序遍历的规则是：

1. 中序遍历左子树。
2. 访问根节点。
3. 中序遍历右子树。

3. 后序遍历 (Postorder Traversal)

后序遍历的规则是：

1. 后序遍历左子树。
2. 后序遍历右子树。
3. 访问根节点。

C语言实现

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

const int MAXN = 100010; // 最大节点个数

typedef struct _binary_treeNode {
    int data;  // 数据域
    int left;  // 左孩子所在的下标，-1表示无左子树
    int right; // 右孩子所在的下标，-1表示无右子树
} biTree;

biTree t[MAXN];
unsigned n; // 实际节点个数

void preOrderTraversal(int root) {
    if (root == -1) {
        return;
    }
    
    printf('%d ', t[root].data);
    preOrderTraversal(t[root].left);
    preOrderTraversal(t[root].right);
}

void inOrderTraversal(int root) {
    if (root == -1) {
        return;
    }
    
    inOrderTraversal(t[root].left);
    printf('%d ', t[root].data);
    inOrderTraversal(t[root].right);
}

void postOrderTraversal(int root) {
    if (root == -1) {
        return;
    }
    
    postOrderTraversal(t[root].left);
    postOrderTraversal(t[root].right);
    printf('%d ', t[root].data);
}

int main() {
    scanf('%u', &n);
    
    for (unsigned i = 0; i < n; i++) {
        scanf('%d', &(t[i].data));
        scanf('%d', &(t[i].left));
        scanf('%d', &(t[i].right));
    }
    
    printf('先序遍历序列: ');
    preOrderTraversal(0);
    printf('
');
    
    printf('中序遍历序列: ');
    inOrderTraversal(0);
    printf('
');
    
    printf('后序遍历序列: ');
    postOrderTraversal(0);
    printf('
');
    
    return 0;
}

代码解释

• biTree 结构体定义了二叉树节点的结构，包括数据域 data，左孩子指针 left 和右孩子指针 right。
• t 是一个 biTree 类型的数组，用于存储二叉树的节点信息，使用静态链表的方式存储。
• n 表示二叉树的节点总数。
• preOrderTraversal, inOrderTraversal 和 postOrderTraversal 函数分别实现了先序、中序和后序遍历算法，使用递归的方式实现。
• main 函数中，首先读取二叉树的节点信息，然后分别调用三个遍历函数进行遍历，并输出遍历结果。

总结

本文介绍了二叉树的三种基本遍历方式，并提供了使用C语言实现的代码示例。掌握二叉树的遍历算法对于理解和应用二叉树这种数据结构至关重要。