二叉树的三种遍历方式

发布时间:2023-04-29 18:30

 目录

1.二叉树的结构:

2.二叉树的前序遍历:

3.二叉树的中序遍历:

4.二叉树的后序遍历:

5.二叉树前、中、后序的代码实现:

前序遍历函数:

 中序遍历函数:

 后序遍历:

完整代码: 

代码运行结果截图:


 在学数据结构的时候,我们很多人不知道在从何学起,也不知道怎么巩固所学的知识,今天在这里向大家推荐一个我认为特别优秀的一个刷题网站:牛客网,其中含有大量的算法题和面试题,
链接:牛客网YYDS

二叉树的三种遍历方式_第1张图片

1.二叉树的结构:

每一个二叉树均可以分为三部分:1.根节点 2.左子树 3.右子树。

比如上图中的A的左右子树分别是B、C,而E的左右子树为NULL、NULL。通常我们把NULL省略。

2.二叉树的前序遍历:

又叫先根遍历,遍历顺序是根节点、左子树、右子树。

上图的前序遍历:A B D NULL NULL E NULL NULL C NULL NULL

省略NULL后:A B D E C

3.二叉树的中序遍历:

遍历顺序:左子树、根节点、右子树

上图的中序遍历:NULL D NULL B NULL E NULL A NULL C NULL

省略NULL后:D B E A C

4.二叉树的后序遍历:

遍历顺序:左子树、右子树、根节点

上图的中序遍历:NULL NULL D NULL NULL E B NULL NULL C A

省略NULL后:D E B C A

5.二叉树前、中、后序的代码实现:

前序遍历函数:

void prev_order(BTNode* root)//前序遍历
{
	if (root == NULL)
	{
		printf("NULL");
		return;
	}
	printf("%c ", root->data);
	prev_order(root->left);
	prev_order(root->right);
}

二叉树的三种遍历方式_第2张图片

 中序遍历函数:

void on_order(BTNode* root)//中序遍历
{
	if (root == NULL)
	{
		printf("NULL\n");
		return;
	}
	prev_order(root->left);
	printf("%c ", root->data);
	prev_order(root->right);
}

二叉树的三种遍历方式_第3张图片

 后序遍历:

void post_order(BTNode* root)//后序遍历
{
	if (root == NULL)
	{
		printf("  NULL   \n");
		return;
	}
	prev_order(root->left);
	prev_order(root->right);
	printf("%c    ", root->data);
}

二叉树的三种遍历方式_第4张图片

完整代码: 

#define _CRT_SECURE_NO_WARNINGS 1
#include
#include
typedef char BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;
BTNode* BuyNode(BTDataType x)//开辟空间存储变量
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;
	return newnode;
}
void prev_order(BTNode* root)//前序遍历
{
	if (root == NULL)
	{
		printf("NULL");
		return;
	}
	printf("%c ", root->data);
	prev_order(root->left);
	prev_order(root->right);
}
void on_order(BTNode* root)//中序遍历
{
	if (root == NULL)
	{
		printf("NULL\n");
		return;
	}
	prev_order(root->left);
	printf("%c ", root->data);
	prev_order(root->right);
}
void post_order(BTNode* root)//后序遍历
{
	if (root == NULL)
	{
		printf("  NULL   \n");
		return;
	}
	prev_order(root->left);
	prev_order(root->right);
	printf("%c    ", root->data);
}
int main(void)
{
	BTNode* n1 = BuyNode('A');
	BTNode* n2 = BuyNode('B');
	BTNode* n3 = BuyNode('C');
	BTNode* n4 = BuyNode('D');
	BTNode* n5 = BuyNode('E');
	n1->left = n2;
	n1->right = n3;
	n2->left = n4;
	n2->right = n5;
	prev_order(n1);
	printf("\n");
	on_order(n1);
	printf("\n");
	post_order(n1);
	printf("\n");
	return 0;
}

代码运行结果截图:

二叉树的三种遍历方式_第5张图片

在学数据结构的时候,我们很多人不知道在从何学起,也不知道怎么巩固所学的知识,今天在这里向大家推荐一个我认为特别优秀的一个刷题网站:牛客网,其中含有大量的算法题和面试题,
链接:牛客网YYDS

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号