【数据结构】二叉树前、中、后序遍历

1 前序遍历

1.1前序遍历的定义

二叉树的前序遍历遵循特定的访问顺序：根节点-左子树-右子树。这种遍历方式属于深度优先搜索的一种形式，广泛应用于各种编程语言的数据结构操作中。

1.2前序遍历的代码实现

#pragma once
#include<stdio.h>
#include<stdlib.h>

typedef char BTDataType;

typedef struct BTNode
{
	struct BTNode* left;
	struct BTNode* right;
	BTDataType data;

}BTNode;

BTNode* BuyBTNode(BTDataType x);

void PrevOrder(BTNode* root);
void InOrder(BTNode* root);
void PostOrder(BTNode* root);

int TreeSize(BTNode* root);

void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	printf("%c ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

int main()
{
	BTNode* A = BuyBTNode('A');
	BTNode* B = BuyBTNode('B');
	BTNode* C = BuyBTNode('C');
	BTNode* D = BuyBTNode('D');
	BTNode* E = BuyBTNode('E');

	A->left = B;
	A->right = C;
	B->left = D;
	B->right = E;

	PrevOrder(A);
	printf("\n");

	return 0;
}

实现效果：

2 中序遍历

2.1中序遍历的定义

二叉树的中序遍历是一种深度优先遍历算法，它遵循 “左 - 根 - 右” 的访问顺序，即先访问左子树，再访问根节点，最后访问右子树。

2.2中序遍历的代码实现

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	InOrder(root->left);
	printf("%c ", root->data);
	InOrder(root->right);
}

实现效果：

3后序遍历

3.1后序遍历的定义

二叉树的后序遍历遵循 “左 - 右 - 根” 的顺序，即先访问左子树，接着访问右子树，最后访问根节点。

3.2后序遍历的代码实现

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%c ", root->data);
}

实现效果：