1.回顾二叉树的概念

二叉树是：

空树
非空：根节点，根节点的左子树、根节点的右子树组成的。

2.二叉树遍历有：前序/中序/后序的递归结构遍历

前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

简单来说就是
--------😐 -------------😐--------😐 -------------😐
前序: 根左子树右子树
中序: 左子树根右子树
前序: 左子树右子树根

手搓一个二叉树:

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));
	assert(newNode);
	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;
}

在这里插入图片描述

2.1 前序

看代码:

void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

在这里插入图片描述
我们来看一下左子树的递归的过程:

那我们怎么更好的理解呢???
首先我们得明确递归的思路:递归就是将大问题化作小问题解决,但是得控制好边界条件,并且递归就是递和归这两个过程,递就相当于往下遍历,归就是回去!
我们来分析一下前序吧,根据前序的定义是先找到根(我们直接打印出的), 然后左子树右子树,这是不是一个大问题?
在这里插入图片描述
那么子树是不是也可以分为根(我们直接打印出的), 然后左子树右子树这是不是小问题呢??

2.2中序

// 二叉树中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

在这里插入图片描述
左子树递归图:

2.3后序

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}