二叉树和堆（3）——二叉树链式结构的实现和递归思想（1）

二叉树的前序、中序和后序遍历

前序遍历

图片解析

代码表示

递归分析

中序遍历

图片解析

代码表示

后序遍历

图片解析

代码表示

学习二叉树的基本操作前，需要创建一棵二叉树，然后才能学习相关的操作。因此，本篇我们就先介绍一下二叉树的链式结构。这里的链式结构说的是二叉树的前序、中序和后序遍历。

二叉树的前序、中序和后序遍历

学习二叉树的结构，最简单的就是遍历。所谓二叉树的遍历，就是按照某种特殊的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。

前序遍历

前序遍历：先访问根节点，然后是左子树，最后是右子树。每个子树也是这样的顺序进行遍历。

注意，这里说的是子树，而不是孩子

图片解析

图中ln和rn分别代表左子树和右子树，并且用ln和rn表述的子树都是空。为了能够清楚原理，我们把空的子树也表是出来。

从图上看，前序遍历就是类似于一个递归，遍历完 1 后，就开始遍历 1的左子树，1的左子树里的其他按照根左子树右子树遍历后，遍历 1 的右子树，原理同上。

代码表示

我们先手捏一个符合图上的二叉树。

代码如下：

typedef int datatype;
typedef struct BinaryTree
{
	datatype _data;
	struct BinaryTree* _left;
	struct BinaryTree* _right;
}BT;

BT* CreatNode(datatype x)
{
	BT* newnode = (BT*)malloc(sizeof(BT));
	if (newnode == NULL)
	{
		perror("malloc");
		return;
	}
	newnode->_left = NULL;
	newnode->_right = NULL;
	newnode->_data = x;
	return newnode;
}
BT* CreatBinaryTree()
{
	BT* node1 = CreatNode(1);
	BT* node2 = CreatNode(2);
	BT* node3 = CreatNode(3);
	BT* node4 = CreatNode(4);
	BT* node5 = CreatNode(5);
	BT* node6 = CreatNode(6);
	node1->_left = node2;
	node1->_right = node4;
	node2->_left = node3;
	node4->_left = node5;
	node4->_right = node6;
	return node1;
}

然后前序遍历：

void PreOrder(BT* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	printf("%d ", root->_data);
	PreOrder(root->_left);
	PreOrder(root->_right);
}
int main()
{
	BT* root = CreatBinaryTree();
	PreOrder(root);
	return 0;
}

我们打印一下：

为什么是这样呢？

递归分析

就是一个简单的函数递归，先执行红色箭头的，在执行绿色箭头的，最后在执行紫色箭头的。

也就是打印 1 后，进入 1的_left ,然后打印 2 然后进入 2的_left ，打印 3然后进入3的_left ，打印 n 后返回上级函数（即3），然后进入 3的_right ,打印 n然后返回3 ，此时 3 的函数已经结束，然后返回 2的_left，然后进入 2的_left ,然后打印 n后返回2 此时2已经结束，就返回 1的_left 然后进入1的_right,然后打印 4 后，进入4的_left ,然后打印 5 .。这样依次类推。

中序遍历

中序遍历：先访问左子树，然后访问根，然后访问右子树。

图片解析

有了前面前序遍历的铺垫，中序遍历是不是很简单了。

代码表示

中序遍历的代码如下：

void InOrder(BT* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	InOrder(root->_left);
	printf("%d ", root->_data);
	InOrder(root->_right);
}

我们打印一下试试：

和我们上面的图片分析的一样捏。

这个递归分析和前序遍历的一样，这里就不展开说了。

不懂的小伙伴可以画一下递归图呀。

后序遍历

后序遍历：先遍历左子树，然后遍历右子树，最后遍历根。

图片解析

相信这个已经难不倒小伙伴们了

代码表示

后序遍历的代码如下：

void PostOrder(BT* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	PostOrder(root->_left);
	PostOrder(root->_right);
	printf("%d ", root->_data);
}

我们打印一下试试：