二叉树的三种遍历方式

文章目录

• 前言
• • 本文章讲解二叉树的三种遍历
• 一、前序遍历
• • 1、理解前序遍历
  • 2、前序遍历代码
• 二、中序遍历
• • 中序遍历代码
• 三、后序遍历
• • 后序遍历代码
• 总结

前言

本文章讲解二叉树的三种遍历

前序遍历：先遍历根节点，然后是左节点，最后是右节点-----根左右
中序遍历：先遍历左节点，然后是根节点，最后是右节点-----左根右
后序遍历：先遍历左节点，然后是右节点，最后是根节点-----左右根
先创建一个二叉树
text.h

#pragma once
#define ElemType  char
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

typedef struct BinaryTreeNode
{
	ElemType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;
//创建结点
BTNode* BuyNode(ElemType x);
//创建二叉树
BTNode* CreateTree();

//前序遍历
void PreOrder(BTNode* root);
//中序遍历
void InOrder(BTNode* root);
//后序遍历
void PostOrder(BTNode* root);

下图为一张最基本的二叉树

接下来将为大家讲解如何遍历。

一、前序遍历

1、理解前序遍历

该图为前序遍历运行结果：

我们看待前序遍历，可以牢牢根据口诀来理解根左右，A为根，红色部分为左，绿色部分为右。这样，在大体上就可以知道哪些元素在A的左边，哪些元素在A的右边。

然后依旧是根据口诀根左右，根有了（A），那么接下来就是处理左半部分，根为B，那么左边就是D，右边就是NULL。
因为D的下面已经没有元素可以遍历了，所以可以认为是整个二叉树最左边的部分，就可以回溯。

根和左半部分都处理完了，那么就剩下右半部分了，聪明的同学已经通过上面的规律看出来了，根为C，左为E，右为F。

2、前序遍历代码

//先序遍历--根左右
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);
}

总结

二叉树的前中后遍历需要多次自己亲自过一遍，这样才能理解图片的进程和函数的递归之间的练习，以便早日在以后的过程中更加熟练地运用和扩展思维。