C语言数据结构二叉树先序、中序、后序及层次四种遍历

C语言数据结构二叉树四种遍历

什么是二叉树

二叉树是一种非常重要的数据结构，在计算机科学中具有广泛的应用。它由节点和边组成，每个节点最多有两个子节点。二叉树有许多种遍历方法，可以用来查找节点、在树中插入新节点、删除节点等操作。

二叉树遍历

二叉树遍历是指对二叉树的节点进行访问，有4种遍历方式：

• 先序遍历（Preorder Traversal）
• 中序遍历（Inorder Traversal）
• 后序遍历（Postorder Traversal）
• 层次遍历（Breadth-First Traversal）

下面我们将分别介绍每一种遍历方式。

先序遍历

先序遍历是指先访问根节点，再访问左子树和右子树。具体步骤如下：

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

代码实现如下：

void pre_order_traversal(tree_node *tree) {
  if (tree != NULL) {
    visit(tree);
    pre_order_traversal(tree->left);
    pre_order_traversal(tree->right);
  }
}

其中，visit()函数表示对当前节点的操作。下面是一个示例函数：

void visit(tree_node *node) {
  printf("%d ", node->value);
}

中序遍历

中序遍历是指先访问左子树，再访问根节点和右子树。具体步骤如下：

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

代码实现如下：

void in_order_traversal(tree_node *tree) {
  if (tree != NULL) {
    in_order_traversal(tree->left);
    visit(tree);
    in_order_traversal(tree->right);
  }
}

后序遍历

后序遍历是指先访问左子树，再访问右子树和根节点。具体步骤如下：

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

代码实现如下：

void post_order_traversal(tree_node *tree) {
  if (tree != NULL) {
    post_order_traversal(tree->left);
    post_order_traversal(tree->right);
    visit(tree);
  }
}

层次遍历

层次遍历是指按照节点的层次顺序依次访问每个节点。具体步骤如下：

1. 将根节点放入队列
2. 取出队列中的第一个节点，访问该节点
3. 将该节点的左右节点（如果有）放入队列
4. 重复步骤2和3，直到队列为空

代码实现如下：

void breadth_first_traversal(tree_node *tree) {
  queue *q = new_queue();
  if (tree != NULL) {
    enqueue(q, tree);
  }
  while (!is_empty(q)) {
    tree_node *node = dequeue(q);
    visit(node);
    if (node->left != NULL) {
      enqueue(q, node->left);
    }
    if (node->right != NULL) {
      enqueue(q, node->right);
    }
  }
}

示例

下面是一个创建二叉树并遍历的示例程序。该程序创建了一个如下所示的二叉树：

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

然后分别使用先序遍历、中序遍历、后序遍历、层次遍历的方法输出结果。

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

typedef struct tree_node tree_node;
struct tree_node {
  int value;
  tree_node *left;
  tree_node *right;
};

tree_node *new_node(int value) {
  tree_node *node = malloc(sizeof(tree_node));
  node->value = value;
  node->left = NULL;
  node->right = NULL;
  return node;
}

tree_node *build_tree() {
  tree_node *root = new_node(1);
  root->left = new_node(2);
  root->right = new_node(3);
  root->left->left = new_node(4);
  root->left->right = new_node(5);
  root->right->left = new_node(6);
  root->right->right = new_node(7);
  return root;
}

void visit(tree_node *node) {
  printf("%d ", node->value);
}

void pre_order_traversal(tree_node *tree) {
  if (tree != NULL) {
    visit(tree);
    pre_order_traversal(tree->left);
    pre_order_traversal(tree->right);
  }
}

void in_order_traversal(tree_node *tree) {
  if (tree != NULL) {
    in_order_traversal(tree->left);
    visit(tree);
    in_order_traversal(tree->right);
  }
}

void post_order_traversal(tree_node *tree) {
  if (tree != NULL) {
    post_order_traversal(tree->left);
    post_order_traversal(tree->right);
    visit(tree);
  }
}

void breadth_first_traversal(tree_node *tree) {
  queue *q = new_queue();
  if (tree != NULL) {
    enqueue(q, tree);
  }
  while (!is_empty(q)) {
    tree_node *node = dequeue(q);
    visit(node);
    if (node->left != NULL) {
      enqueue(q, node->left);
    }
    if (node->right != NULL) {
      enqueue(q, node->right);
    }
  }
}

int main() {
  tree_node *tree = build_tree();
  printf("pre-order traversal:\n");
  pre_order_traversal(tree);
  printf("\n");
  printf("in-order traversal:\n");
  in_order_traversal(tree);
  printf("\n");
  printf("post-order traversal:\n");
  post_order_traversal(tree);
  printf("\n");
  printf("breadth-first traversal:\n");
  breadth_first_traversal(tree);
  printf("\n");
  return 0;
}

输出结果如下：

pre-order traversal:
1 2 4 5 3 6 7 
in-order traversal:
4 2 5 1 6 3 7 
post-order traversal:
4 5 2 6 7 3 1 
breadth-first traversal:
1 2 3 4 5 6 7