C语言数据结构系列篇：二叉树的遍历

二叉树（Binary Tree）是一种树形结构，它由一个根节点和两个子树组成，这两个子树都是二叉树，被称为左子树和右子树。二叉树有许多用途，例如用来存储有序列表或具有层级关系的信息等等。本篇将详细讲解二叉树的遍历。

二叉树的遍历

二叉树的遍历即将二叉树中的节点按照某种顺序，一次访问每一个节点。常见的二叉树遍历方式有前序遍历、中序遍历和后序遍历。下面分别对这三种遍历方式进行讲解。

前序遍历

前序遍历是指先访问当前节点的值，然后再访问左子树和右子树。换句话说，遍历顺序为 当前节点 -> 左子树 -> 右子树。

前序遍历的递归算法如下：

void preorder_traversal(BinaryTree *node) {
  if (node != NULL) {
    printf("%d ", node->value);          // 1. 访问当前节点
    preorder_traversal(node->leftChild); // 2. 前序遍历左子树
    preorder_traversal(node->rightChild);// 3. 前序遍历右子树
  }
}

例如，对于下面一棵二叉树：

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

按照前序遍历的顺序，遍历结果为： 1 2 4 5 3 6 7

中序遍历

中序遍历是指先访问左子树，然后访问当前节点的值，最后访问右子树。换句话说，遍历顺序为 左子树 -> 当前节点 -> 右子树。

中序遍历的递归算法如下：

void inorder_traversal(BinaryTree *node) {
  if (node != NULL) {
    inorder_traversal(node->leftChild);   // 1. 中序遍历左子树
    printf("%d ", node->value);           // 2. 访问当前节点
    inorder_traversal(node->rightChild);  // 3. 中序遍历右子树
  }
}

例如，对于下面一棵二叉树：

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

按照中序遍历的顺序，遍历结果为：4 2 5 1 6 3 7

后序遍历

后序遍历是指先访问左子树，然后访问右子树，最后访问当前节点的值。换句话说，遍历顺序为 左子树 -> 右子树 -> 当前节点。

后序遍历的递归算法如下：

void postorder_traversal(BinaryTree *node) {
  if (node != NULL) {
    postorder_traversal(node->leftChild);   // 1. 后序遍历左子树
    postorder_traversal(node->rightChild);  // 2. 后序遍历右子树
    printf("%d ", node->value);            // 3. 访问当前节点
  }
}

例如，对于下面一棵二叉树：

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

按照后序遍历的顺序，遍历结果为：4 5 2 6 7 3 1

示例

下面是一个示例程序，使用上述三种遍历方式遍历二叉树：

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

typedef struct treeNode TreeNode;
struct treeNode {
  int value;
  TreeNode *leftChild;
  TreeNode *rightChild;
};

TreeNode* new_tree_node(int value) {
  TreeNode *newNode = (TreeNode*)malloc(sizeof(TreeNode));
  newNode->value = value;
  newNode->leftChild = NULL;
  newNode->rightChild = NULL;
  return newNode;
}

void preorder_traversal(TreeNode *node) {
  if (node != NULL) {
    printf("%d ", node->value);
    preorder_traversal(node->leftChild);
    preorder_traversal(node->rightChild);
  }
}

void inorder_traversal(TreeNode *node) {
  if (node != NULL) {
    inorder_traversal(node->leftChild);
    printf("%d ", node->value);
    inorder_traversal(node->rightChild);
  }
}

void postorder_traversal(TreeNode *node) {
  if (node != NULL) {
    postorder_traversal(node->leftChild);
    postorder_traversal(node->rightChild);
    printf("%d ", node->value);
  }
}

int main() {
  TreeNode *root = new_tree_node(1);
  root->leftChild = new_tree_node(2);
  root->rightChild = new_tree_node(3);
  root->leftChild->leftChild = new_tree_node(4);
  root->leftChild->rightChild = new_tree_node(5);
  root->rightChild->leftChild = new_tree_node(6);
  root->rightChild->rightChild = new_tree_node(7);

  printf("Preorder Traversal:\n");
  preorder_traversal(root);

  printf("\nInorder Traversal:\n");
  inorder_traversal(root);

  printf("\nPostorder Traversal:\n");
  postorder_traversal(root);

  return 0;
}

运行结果：

Preorder Traversal:
1 2 4 5 3 6 7
Inorder Traversal:
4 2 5 1 6 3 7
Postorder Traversal:
4 5 2 6 7 3 1

以上就是二叉树的遍历的完整攻略。