二叉树的前序、中序、后序遍历（递归）

  虽然写这个博客主要目的是为了给我自己做一个思路记忆录，但是如果你恰好点了进来，那么先对你说一声欢迎。我并不是什么大触，只是一个菜菜的学生，如果您发现了什么错误或者您对于某些地方有更好的意见，非常欢迎您的斧正！

  前序遍历（DLR），是二叉树遍历的一种，也叫做先根遍历、先序遍历、前序周游，可记做根左右。前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。
  看图就很清晰，我就不阐述我的理解了。

前序遍历结果：ABDGHCEF

  中序遍历：中序遍历（LDR）是二叉树遍历的一种，也叫做中根遍历、中序周游。在二叉树中，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。

中序遍历结果：GDHBAEICF

  后序遍历：后序遍历（LRD）是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中，先左后右再根，即首先遍历左子树，然后遍历右子树，最后访问根结点。

  这里加一部分我的理解吧：后序遍历就是只要这个结点还有子树，就按照从左到右先遍历子树。

中序遍历结果：GHDBIEFCA
接下来是代码部分（建议复制后自己运行一下）：

二叉堆的遍历.h

#pragma once
#include <stdio.h>
typedef char dataType;

/*构建二叉树结点*/
typedef struct TreeNode
{
	dataType data;/*该结点的数据*/
	TreeNode *left;/*指向左边结点的指针*/
	TreeNode *right;/*指向右边结点的指针*/
}TreeNode;


/*前序遍历*/
void PreTraver(TreeNode *root);

/*中序遍历*/
void MidorTraver(TreeNode *root);

/*后序遍历*/
void LastTraver(TreeNode *root);

/*测试遍历函数*/
void TestTravel();

二叉堆的遍历.cpp

#include "二叉堆的遍历.h"
#include <iostream>
using namespace std;

/*前序遍历*/
void PreTraver(TreeNode *root)
{
	if (root != NULL)/*如果这个结点非空*/
	{
		cout << root->data << " ";/*打印这个结点的数值*/
		PreTraver(root->left);/*遍历它的左子树*/
		PreTraver(root->right);/*遍历它的右子树*/
	}
}

/*中序遍历*/
void MidorTraver(TreeNode *root)
{
	if (root != NULL)/*如果这个结点非空*/
	{
		MidorTraver(root->left);/*遍历它的左子树*/
		cout << root->data << " ";/*打印这个结点的数值*/
		MidorTraver(root->right);/*遍历它的右子树*/
	}
}

/*后序遍历*/
void LastTraver(TreeNode *root)
{
	if (root != NULL)/*如果这个结点非空*/
	{
		LastTraver(root->left);/*遍历它的左子树*/
		LastTraver(root->right);/*遍历它的右子树*/
		cout << root->data << " ";/*打印这个结点的数值*/
	}
}

/*测试遍历函数*/
void TestTravel()
{
	/*构建二叉树*/
	/*
	             A
	          B     C
	      D      E    F
	    G   H      I
	*/
	TreeNode binaryTree[9] =
	{
	{ 'A',&binaryTree[1],&binaryTree[2] },
	{ 'B',&binaryTree[3],NULL },
	{ 'C',&binaryTree[4],&binaryTree[5] },
	{ 'D',&binaryTree[6],&binaryTree[7] },
	{ 'E',NULL,&binaryTree[8] },
	{ 'F',NULL,NULL },
	{ 'G',NULL,NULL },
	{ 'H',NULL,NULL },
	{ 'I',NULL,NULL }
	};
	cout << "前序遍历结果:";
	PreTraver(binaryTree);
	cout << endl;
	cout << "中序遍历结果:";
	MidorTraver(binaryTree);
	cout << endl;
	cout << "后序遍历结果:";
	LastTraver(binaryTree);
}

主函数

#include <stdio.h>
#include "二叉堆的遍历.h"

int main()
{
	TestTravel();
	getchar();
	return 0;
}

运行结果：


参考网站以及博客：

百度百科
二叉树的前序、中序、后序三种遍历的六种实现方式（递归、非递归）（C++） https://blog.csdn.net/liujiayu1015/article/details/52535829