二叉树的先序遍历(分而治之思想)

代码在文章底部。

先序遍历又叫先根遍历，顾名思义：遍历顺序为根，左子树，右子树。

样例图

本文将对以下二叉树进行遍历

先上代码：先序遍历的核心代码。

void PreOrder(BiTNode* T)
{
	if (T == NULL)
	{
		cout << "NULL ";
		return;
	}
	cout << T->data << " ";
	PreOrder(T->lchild);
	PreOrder(T->rchild);
}

先序遍历的运行结果：
A B D E C

函数的递归调用

解释：第一步：从A结点开始打印，打印A结点，进入A的左子树。

第二步：打印B结点，进入B的左子树。

第三步：打印D结点，进入D的左子树。

第四步：D的左子树为空， 打印 NULL , 返回上一步，打印D的右子树。

第五步：进入D的右子树。

第六步： D的右子树为空，打印 NULL , 返回上一步。

第七步：此处的代码运行结束，返回上一步。

第八步：进入B的右子树，打印E。

第九步：进入E的左子树。

第十步：打印E的左子树，打印NULL，返回上一步，打印E的右子树。

第十一步：进入E的右子树。

第十二步：打印E的右子树，打印NULL，返回上一步，此处的函数运行结束。

第十三步：此处的函数运行结束，返回上一步。

第十四步：此处的函数运行结束，返回上一步。

第十五步：进入A的右子树，打印C。

第十六步：进入C的左子树。

第十七步：C的左子树为空， 打印 NULL , 返回上一步，打印C的右子树。

第十八步：进入C的右子树。

第十九步：C的右子树为空， 打印 NULL , 返回上一步。

第二十步：此处函数运行结束，继续返回上一步。

到此程序的运行就结束了。

源代码

#include<iostream>
using namespace std;
typedef char ElemType;

typedef struct BiTNode {
	ElemType data;           //数据域
	struct BiTNode* lchild;  //左孩子指针
	struct BiTNode* rchild;	 //右孩子指针
}BiTNode;

//先序排序
void PreOrder(BiTNode* T)
{
	if (T == NULL)
	{
		cout << "NULL ";
		return;
	}
	cout << T->data << " ";
	PreOrder(T->lchild);
	PreOrder(T->rchild);
}

//中序排序
void InOrder(BiTNode* T)
{
	if (T == NULL)
	{
		cout << "NULL ";
		return;
	}
	PreOrder(T->lchild);
	cout << T->data << " ";
	PreOrder(T->rchild);
}
//后序排序
void PostOrder(BiTNode* T)
{
	if (T == NULL)
	{
		cout << "NULL ";
		return;
	}
	PreOrder(T->lchild);
	PreOrder(T->rchild);
	cout << T->data << " ";
}
int main()
{
	//快速创建一个树
	BiTNode* A = (BiTNode*)malloc(sizeof(BiTNode));
	A->data = 'A';
	A->lchild = NULL;
	A->rchild = NULL;

	BiTNode* B = (BiTNode*)malloc(sizeof(BiTNode));
	B->data = 'B';
	B->lchild = NULL;
	B->rchild = NULL;

	BiTNode* C = (BiTNode*)malloc(sizeof(BiTNode));
	C->data = 'C';
	C->lchild = NULL;
	C->rchild = NULL;

	BiTNode* D = (BiTNode*)malloc(sizeof(BiTNode));
	D->data = 'D';
	D->lchild = NULL;
	D->rchild = NULL;

	BiTNode* E = (BiTNode*)malloc(sizeof(BiTNode));
	E->data = 'E';
	E->lchild = NULL;
	E->rchild = NULL;

	A->lchild = B;
	A->rchild = C;
	B->lchild = D;
	B->rchild = E;
	cout << "先序排序: ";
	PreOrder(A);
	cout << endl;

	cout << "中序排序: ";
	InOrder(A);
	cout << endl;

	cout << "后序排序: ";
	PostOrder(A);
	cout << endl;

	return 0;
}

运行结果

觉得我回答有用的话，记得点个关注哟！谢谢支持！