数据结构初阶：二叉树的前中后序三种遍历(递归的暴力美学)

想要实现二叉树的遍历可以创建一个链式结构的二叉树

回顾一下二叉树的概念，二叉树分为空树和非空二叉树，非空二叉树由根节点、根节点的左子树和根节点的右子树组成。

typedef char BTDataType;          // 数据类型
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;  // 二叉树的左节点
	struct BinaryTreeNode* right; // 二叉树的右节点
}BTNode;

前中后序遍历

1）前序遍历(Preorder Traversal 亦称先序遍历)：访问根结点的操作发⽣在遍历其左右⼦树之前

访问顺序为：根结点、左⼦树、右⼦树

A- > B -> D -> NULL -> NULL -> NULL -> C -> E -> NULL -> NULL -> F -> NULL -> NULL

2）中序遍历(Inorder Traversal)：访问根结点的操作发⽣在遍历其左右⼦树之中（间）

访问顺序为：左⼦树、根结点、右⼦树

NULL -> D -> NULL -> B -> NULL -> A -> NULL -> E -> NULL -> C -> NULL -> F -> NULL

3）后序遍历(Postorder Traversal)：访问根结点的操作发⽣在遍历其左右⼦树之后

访问顺序为：左⼦树、右⼦树、根结点

NULL -> NULL -> D -> NULL -> B -> NULL -> NULL -> E -> NULL -> NULL -> F -> C -> A

创建节点

BTNode* ByeNode(BTDataType x)
{
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	if (root == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	root->data = x;
	root->left = root->right = NULL;
	return root;
}

BTNode* createBinaryTree()
{
	BTNode* rootA = ByeNode('A');
	BTNode* rootB = ByeNode('B');
	BTNode* rootC = ByeNode('C');
	BTNode* rootD = ByeNode('D');
	BTNode* rootE = ByeNode('E');
	BTNode* rootF = ByeNode('F');

	rootA->left = rootB;
	rootA->right = rootC;
	rootB->left = rootD;
	rootC->left = rootE;
	rootC->right = rootF;

	return rootA;
}

代码实现前序遍历

// 先序遍历二叉树——根左右
void preOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	preOrder(root->left);
	preOrder(root->right);
}

画了一个简易的递归图，原图过长且太小了

中序遍历代码

// 中序遍历二叉树——左根右
void inOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	inOrder(root->left);
	printf("%c ", root->data);
	inOrder(root->right);
}

后序遍历代码

//后序遍历二叉树——左右根
void postOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	postOrder(root->left);
	postOrder(root->right);
	printf("%c ", root->data);
}