二叉树的遍历

标签：左子遍历右子 BTNode 二叉树 root

前言

二叉树有三种遍历方式，三种遍历方式的核心都是把一颗二叉树分为根、左子树、右子树三部分。前中后其实说的是根出现的顺序，在二叉树中左子树遍历顺序始终先于右子树。

分析

以这个二叉树为例讲解，一颗二叉树分为根、左子树、右子树。空树是最小单位已经不能再分

最先分为根1、根1的左子树、根1的右子树

根1的左子树又可以分为根2、根2的左子树、根2的右子树（为空树）

根1的右子树又可以分为根4、根4的左子树、根4的右子树

根2的左子树又可以分为根3 、根3的左子树（为空树）、根3的右子树（为空树）

根2的右子树是空树是最小单位已经不能再分了

根4的左子树又可以分为根5 、根5的左子树（为空树）、根5的右子树（为空树）

根4的右子树又可以分为根6 、根6的左子树（为空树）、根6的右子树（为空树）

如下图

温馨提示：空树用N来表示

前序遍历

根-> 左子树 ->右子树

开始遍历

根1-> 根2（1的左子树） -> 根3（2的左子树）-> N(3的左子树)-> N(3的右子树)

2的左子树遍历完，返回遍历2的右子树

根1-> 根2（1的左子树） -> 根3（2的左子树）-> N(3的左子树)-> N(3的右子树)->N（2的右子树）

1的左子树遍历完，返回遍历1的右子树

根1-> 根2（1的左子树） -> 根3（2的左子树）-> N(3的左子树)-> N(3的右子树)->N（2的右子树）->根4（1的右子树）->根5（4的左子树）->N（5的左子树）->N（5的右子树）

4的左子树遍历完，返回遍历4的右子树

根1-> 根2（1的左子树） -> 根3（2的左子树）-> N(3的左子树)-> N(3的右子树)->N（2的右子树）->根4（1的右子树）->根5（4的左子树）->N（5的左子树）->N（5的右子树）->根6（4的右子树）->N(6的左子树)->N(6的右子树)

遍历结束，结果：1 2 3 N N N 4 5 N N 6 N N

中序遍历

左子树-> 根-> 右子树

开始遍历

（根1的左子树）->（根2的左子树）->N(根3的左子树）->根3->N(根3的右子树）

2的左子树遍历完，返回遍历根2和根2的右子树

（根1的左子树）->（根2的左子树）->N(根3的左子树）->根3->N(根3的右子树）->根2->N（2的右子树）

根2和根2的右子树遍历完(也就是根1的左子树遍历完)，返回遍历根1和根1的右子树

（根1的左子树）->（根2的左子树）->N(根3的左子树）->根3->N(根3的右子树）->根2->N（2的右子树）->根1->（根4的左子树）->N(根5的左子树)->根5->N(根5的右子树)

4的左子树遍历完，返回遍历根4和他的右子树

（根1的左子树）->（根2的左子树）->N(根3的左子树）->根3->N(根3的右子树）->根2->N（2的右子树）->根1->（根4的左子树）->N(根5的左子树)->根5->N(根5的右子树)->根4->N（根6的左子树）->根6->N（根6的右子树）

遍历结束，结果：N 3 N 2 N 1 N 5 N 4 N 6 N

后序遍历

左子树-> 右子树-> 根

大家可以自行遍历，这里给个参考结果

结果：N N 3 N 2 N N 5 N N 6 4 1

三种遍历结果汇总

代码实现（核心：递归）

定义一个二叉树的结构体，里面包含左子树指针，右子树指针，数据

先造一棵链式二叉树出来

#include<stdio.h>
#include<stdlib.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;
BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->left = newnode->right = NULL;
	newnode->data = x;
	return newnode;
}
BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	return node1;
}
// 二叉树前序遍历
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}
// 二叉树中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}
// 二叉树后序遍历
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}
int main()
{
	BTNode* root = CreatBinaryTree();
	PreOrder(root);
	printf("\n");
	InOrder(root);
	printf("\n");
	PostOrder(root);
}