参考博客click here!

链式二叉树存储结构:

typedef int DataType;

typedef struct BiNode {
	DataType data;
	struct BiNode *lc, *rc;		// 左右子节点指针
	int depth;
} BiNode, *BiTree;

初始化:

void rootInit(BiTree &root)
{
	root = NULL;
	assert(!root);			// 检查root是否合法
	return;
}

先序遍历: 根左右

递归先序遍历遵循条件:
先访问根节点, 然后访问左子节点, 最后访问右子节点。(根左右)
二叉树为空则停止递归

void PreOrder(BiTree &root)			// 递归先序遍历
{
	if(root == NULL)
		return;
	cout << root->data << " ";
	PreOrder(root->lc);
	PreOrder(root->rc);
}

非递归版本的先序遍历:

1.若根节点为空(空树,不需要遍历),直接返回;

2.否则,将根节点入栈;

3.判断栈是否为空,不为空进入循环;

4.取栈顶结点并访问该节点,同时将该节点出栈;

5.若该节点的右子树不为空,将右孩子结点入栈;

6.若该节点的左子树不为空,将左孩子节点入栈;

7.直到栈为空,跳出循环,完成了先序遍历

void PreOrder2(BiTree &root)		// 非递归先序遍历
{
	stack<BiTree> s;	// 定义一个栈
	while( !s.empty()) s.pop();	// 清空
	if(root != NULL)
		s.push(root);
	BiTree tmp;			// 临时
	while( !s.empty())			// 栈不为空
	{
		tmp = s.top();			// 获得栈顶元素
		s.pop();
		cout << tmp->data << " ";
		if(tmp->lc != NULL)		// 先序遍历,必须先判断右子树
			s.push(tmp->rc);
		if(tmp->rc != NULL)		// 判断右子树
			s.push(tmp->lc);

	}
	cout << endl;
	return;
}

中序遍历:左根右

递归中序遍历遵循条件:    若二叉树为空,直接返回;

1.遍历二叉树的左子树
2.访问根节点
3.遍历二叉树的右子树

void MidOrder(BiTree &root)		// 中序遍历 递归
{
	if(root == NULL)
		return;
	MidOrder(root->lc);		// 先左
	cout << root->data << " ";	// 然后根
	MidOrder(root->rc);		// 最后右
}

非递归中序遍历:

1.若树为空,直接返回;否则令tmp=root,进入循环(跳出条件为栈为空 或 tmp==NULL)

2.循环的将tmp节点的所有左子树入栈

3.取栈顶结点为tmp,访问该节点并出栈

4.令tmp=tmp的右孩子,进入下一次循环

void MidOrder2(BiTree &root)	// 中序遍历 非递归
{
	stack<BiTree> s;
	while( !s.empty()) s.pop();

	BiTree tmp = root;
	while( !s.empty() || tmp != NULL)
	{
		while(tmp != NULL)		//	中序遍历,先向左边找, 左边没有就输出根
		{
			s.push(tmp);
			tmp = tmp->lc;
		}
		tmp = s.top();
		cout << tmp->data << " ";	// 然后根
		tmp = tmp->rc;				// 向右
		s.pop();
	}
	cout << endl;
}

后续遍历:左右根

递归后序遍历

void PostOrder(BiTree &root)	// 后序遍历
{
	if(root == NULL)
		return;
	PostOrder(root->lc);		// left
	PostOrder(root->rc);		// right
	cout << root->data << " ";	// root
}

非递归后序遍历:

1.若树为空,直接返回;否则令tmp= root,进入循环(条件为栈非空或tmp!=NULL)

2.循环的将所有左子树入栈;

3.去栈顶结点,若该节点没有右子树或者右子树已经访问过了,则访问该节点并出栈;

4.否则,令tmp为该节点的右子树,进入下一层循环。

void PostOrder2(BiTree &root)	// 非递归后序遍历
{
	stack<BiTree> s;
	while( !s.empty()) s.pop();

	BiTree tmp = root;
	BiTree pre = NULL; 			// 记录先前刚访问过的结点
	BiTree top;					// 用于临时保存栈顶结点
	while( !s.empty() || tmp != NULL)
	{
		while(tmp != NULL)		// 先一直向左
		{
			s.push(tmp);
			tmp = tmp->lc;
		}
		top = s.top();
		if(top->rc == NULL || top->rc == pre)	// 如果右子节点为空或者已经访问过
		{	// 如果没有右子节点或者已经访问过就输出当前子树的根节点,并出栈
			cout << top->data << " ";
			pre = top;		// 用于从右子节点回溯的时候判断右子节点是否已经访问过
			s.pop();
		}
		else
			tmp = top->rc;

	}
}

完整代码:

#include <iostream>
#include <assert.h>
#include <stack>
using namespace std;
typedef int DataType;

typedef struct BiNode {
	DataType data;
	struct BiNode *lc, *rc;		// 左右子节点指针
	int depth;
} BiNode, *BiTree;

void rootInit(BiTree &root)
{
	root = NULL;
	assert(!root);			// 检查root是否合法
	return;
}

/* 先序遍历 根左右 */
void PreOrder(BiTree &root)			// 递归先序遍历
{
	if(root == NULL)
		return;
	cout << root->data << " ";
	PreOrder(root->lc);
	preOrder(root->rc);
}
void PreOrder2(BiTree &root)		// 非递归先序遍历
{
	stack<BiTree> s;	// 定义一个栈
	while( !s.empty()) s.pop();	// 清空
	if(root != NULL)
		s.push(root);
	BiTree tmp;			// 临时
	while( !s.empty())			// 栈不为空
	{
		tmp = s.top();			// 获得栈顶元素
		s.pop();
		cout << tmp->data << " ";
		if(tmp->lc != NULL)		// 先序遍历,必须先判断右子树
			s.push(tmp->rc);
		if(tmp->rc != NULL)		// 判断右子树
			s.push(tmp->lc);

	}
	cout << endl;
	return;
}

/* 中序遍历 左根右 */
void MidOrder(BiTree &root)		// 中序遍历 递归
{
	if(root == NULL)
		return;
	MidOrder(root->lc);		// 先左
	cout << root->data << " ";	// 然后根
	MidOrder(root->rc);		// 最后右
}
void MidOrder2(BiTree &root)	// 中序遍历 非递归
{
	stack<BiTree> s;
	while( !s.empty()) s.pop();

	BiTree tmp = root;
	while( !s.empty() || tmp != NULL)
	{
		while(tmp != NULL)		//	中序遍历,先向左边找, 左边没有就输出根
		{
			s.push(tmp);
			tmp = tmp->lc;
		}
		tmp = s.top();
		cout << tmp->data << " ";	// 然后根
		tmp = tmp->rc;				// 向右
		s.pop();
	}
	cout << endl;
}

/* 后序遍历 左右根 */
void PostOrder(BiTree &root)	// 后序遍历
{
	if(root == NULL)
		return;
	PostOrder(root->lc);		// left
	PostOrder(root->rc);		// right
	cout << root->data << " ";	// root
}
void PostOrder2(BiTree &root)	// 非递归后序遍历
{
	stack<BiTree> s;
	while( !s.empty()) s.pop();

	BiTree tmp = root;
	BiTree pre = NULL; 			// 记录先前刚访问过的结点
	BiTree top;					// 用于临时保存栈顶结点
	while( !s.empty() || tmp != NULL)
	{
		while(tmp != NULL)		// 先一直向左
		{
			s.push(tmp);
			tmp = tmp->lc;
		}
		top = s.top();
		if(top->rc == NULL || top->rc == pre)	// 如果右子节点为空或者已经访问过
		{	// 如果没有右子节点或者已经访问过就输出当前子树的根节点,并出栈
			cout << top->data << " ";
			pre = top;		// 用于从右子节点回溯的时候判断右子节点是否已经访问过
			s.pop();
		}
		else
			tmp = top->rc;

	}
}

int main()
{







	return 0;
}