数据结构实战

        本节我们来学习二叉树的遍历。二叉树的遍历通常有3种算法：前序遍历、中序遍历和后序遍历。当然，对二叉树来说也可以使用其它的遍历算法，例如从上至下按层级遍历，从左至右或从右至左等等。我们并不打算实现全部的二叉树遍历算法，而只针对前中后这3种算法进行实现。首先来看一下这3种算法的文字描述：

1. 前序遍历算法：
   • 访问当前节点。
   • 使用前序遍历算法访问左孩子节点。
   • 使用前序遍历算法访问右孩子节点。
2. 中序遍历算法：
   • 使用中序遍历算法访问左孩子节点。
   • 访问当前节点。
   • 使用中序遍历算法访问右孩子节点。
3. 后序遍历算法：
   • 使用后序遍历算法访问左孩子节点。
   • 访问当前节点。
   • 使用后序遍历算法访问右孩子节点。

        可见，这3种遍历算法都是基于递归来描述的。所谓的前序、中序和后序，就是访问顺序是当前节点在前、在中间和在后面。

1. 前序：当前节点->左孩子->右孩子
2. 中序：左孩子->当前节点->右孩子
3. 后序：左孩子->右孩子->当前节点

        接下来我们来实现这3种遍历算法：

//前序遍历
void tree_preamble_visit(s_tree *tree, s_node *node)
{
	if (tree == null)
	{
		return;
	}
	if (tree->root == null)
	{
		return;
	}
	if (node == null)
	{
		return;
	}

	//中
	tree->visit_node(node->data);
	//左
	tree_preamble_visit(tree, node->left_child);
	//右
	tree_preamble_visit(tree, node->right_child);
}

//中序遍历
void tree_inorder_visit(s_tree *tree, s_node *node)
{
	if (tree == null)
	{
		return;
	}
	if (tree->root == null)
	{
		return;
	}
	if (node == null)
	{
		return;
	}

	//左
	tree_inorder_visit(tree, node->left_child);
	//中
	tree->visit_node(node->data);
	//右
	tree_inorder_visit(tree, node->right_child);
}

//后序遍历
void tree_postorder_visit(s_tree *tree, s_node *node)
{
	if (tree == null)
	{
		return;
	}
	if (tree->root == null)
	{
		return;
	}
	if (node == null)
	{
		return;
	}

	//左
	tree_postorder_visit(tree, node->left_child);
	//右
	tree_postorder_visit(tree, node->right_child);
	//中
	tree->visit_node(node->data);
}

        假设我们有一个这样的二叉树：

        编写一个main函数来构建这样一棵二叉树，并对其进行前序遍历、中序遍历、后序遍历：

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

//删除整数函数
void free_int(int *i)
{
	if (i != null)
	{
		free(i);
	}
}

//访问整数函数
void visit_int(int *i)
{
	if (i != null)
	{
		printf("%d ", *i);
	}
}

int main(int argc, char **args)
{
	int *t0 = (int *) malloc(sizeof(int));
	int *t1 = (int *) malloc(sizeof(int));
	int *t2 = (int *) malloc(sizeof(int));
	int *t3 = (int *) malloc(sizeof(int));
	int *t4 = (int *) malloc(sizeof(int));
	int *t5 = (int *) malloc(sizeof(int));
	int *t6 = (int *) malloc(sizeof(int));
	int *t7 = (int *) malloc(sizeof(int));
	int *t8 = (int *) malloc(sizeof(int));

	*t0 = 0;
	*t1 = 1;
	*t2 = 2;
	*t3 = 3;
	*t4 = 4;
	*t5 = 5;
	*t6 = 6;
	*t7 = 7;
	*t8 = 8;

	//初始化树
	s_tree tree;
	tree_init(&tree, &visit_int, &free_int);

	s_node *n0 = (s_node *) malloc(sizeof(s_node));
	s_node *n1 = (s_node *) malloc(sizeof(s_node));
	s_node *n2 = (s_node *) malloc(sizeof(s_node));
	s_node *n3 = (s_node *) malloc(sizeof(s_node));
	s_node *n4 = (s_node *) malloc(sizeof(s_node));
	s_node *n5 = (s_node *) malloc(sizeof(s_node));
	s_node *n6 = (s_node *) malloc(sizeof(s_node));
	s_node *n7 = (s_node *) malloc(sizeof(s_node));
	s_node *n8 = (s_node *) malloc(sizeof(s_node));

	tree_init_node(n0, t0);
	tree_init_node(n1, t1);
	tree_init_node(n2, t2);
	tree_init_node(n3, t3);
	tree_init_node(n4, t4);
	tree_init_node(n5, t5);
	tree_init_node(n6, t6);
	tree_init_node(n7, t7);
	tree_init_node(n8, t8);

	//插入根节点
	tree_insert(&tree, null, 0, n0);

	tree_insert(&tree, n0, 0, n1);
	tree_insert(&tree, n0, 1, n2);

	tree_insert(&tree, n1, 0, n3);
	tree_insert(&tree, n1, 1, n4);

	tree_insert(&tree, n2, 0, n5);
	tree_insert(&tree, n2, 1, n6);

	tree_insert(&tree, n5, 0, n7);
	tree_insert(&tree, n5, 1, n8);

	tree_preamble_visit(&tree, tree.root);
	printf("\n");
	tree_inorder_visit(&tree, tree.root);
	printf("\n");
	tree_postorder_visit(&tree, tree.root);
	printf("\n");

	//销毁树
	tree_destroy(&tree);

	return 0;
}

        运行结果：

0 1 3 4 2 5 7 8 6 
3 1 4 0 7 5 8 2 6 
3 4 1 7 8 5 6 2 0

        本例代码：

code path   chapter.05/e.g.5.2/

https       https://github.com/magicworldos/datastructure.git
git         git@github.com:magicworldos/datastructure.git
subverion   https://github.com/magicworldos/datastructure