本文共 2158 字，大约阅读时间需要 7 分钟。

一、先序遍历

1、递归算法

struct Tree{	int date;	Tree* lchild;	Tree* rchild;	Tree(int x):date(x),lchild(nullptr),rchild(nullptr){}};void PreOrder(Tree* root){	if (root != nullptr)	{		cout << root->date << " ";		PreOrder(root->lchild);		PreOrder(root->rchild);	}}

2、非递归算法

void PreOrder(Tree* root){	stack
   
     Stack;	if (root == nullptr)		return;	while (root != nullptr || !Stack.empty())	{		while (root != nullptr)		{			Stack.push(root);			cout << root->date << " ";			root = root->lchild;		}		root = Stack.top();		Stack.pop();		root = root->rchild;	}}
   

二、中序遍历

1、递归算法

void InOrder(Tree* root){	if (root != nullptr)	{		InOrder(root->lchild);		cout << root->date << " ";		InOrder(root->rchild);	}}

2、非递归算法

void InOrder(Tree* root){	stack
   
     s;	while (root != nullptr || !s.empty())	{		if (root != nullptr)		{			s.push(root);			root = root->lchild;		}		else		{			root = s.top();s.pop();			cout << root->date << " ";			root = root->rchild;		}	}}
   

三、后序遍历

1、递归算法

void PostOrder(Tree* root){	if (root != nullptr)	{		PostOrder(root->lchild);		PostOrder(root->rchild);		cout << root->date << " ";	}}

2、非递归算法

void PostOrder(Tree* root){	stack
   
     s;	Tree* r = nullptr;//使用辅助指针，指向最近访问过的节点	while (root != nullptr || !s.empty())	{		if (root != nullptr)		{			s.push(root);			root = root->lchild;		}		else		{			root = s.top();			if (root->rchild != nullptr && root->rchild != r)				root = root->rchild;			else			{				s.pop();				cout << root->date << " ";				r = root;				root = nullptr;			}		}	}}
   

四、层次遍历

1、方法1

void LevelOrder(Tree* root){	if (root == nullptr)		return;	queue
   
     que;	que.push(root);	while (!que.empty())	{		root = que.front();		cout << root->date << " ";		que.pop();		if (root->lchild != nullptr)			que.push(root->lchild);		if (root->rchild != nullptr)			que.push(root->rchild);	}}
   

2、方法2

void LevelOrder(Tree* root){	if (root == nullptr)		return;	queue
   
     que;	que.push(root);	while (!que.empty())	{		int size = que.size();		while (size)		{			root = que.front();			cout << root->date << " ";			que.pop();			if (root->lchild != nullptr)				que.push(root->lchild);			if (root->rchild != nullptr)				que.push(root->rchild);			--size;		}	}}
   

转载地址：http://stwab.baihongyu.com/