树：二叉树的前序/中序/后序/层次递归

在二叉树的应用中，很多使用二叉树的操作都是通过遍历来进行节点的修改。

所以对于遍历而言是学习二叉树的要点，今天就来总结一下。

假设二叉树的结构为：

template<class T> struct BinaryTreeNode {	BinaryTreeNode(const T& x)	:_data(x)	,_left(NULL)	,_right(NULL)	{}	T _data;	BinaryTreeNode<T>* _left;	BinaryTreeNode<T>* _right; };

1. 前序遍历：

void PrevOrder() {	_PrevOrder(_root);	cout<<endl; } void _PrevOrder(BinaryTreeNode<T>* root) {	if (root==NULL)     	    return;	cout<<root->_data<<" ";	_PrevOrder(root->_left);	_PrevOrder(root->_right); } void PrevOrder_Non_R() {	stack<BinaryTreeNode<T>*> s;	if (_root)	s.push(_root);	while(!s.empty())	{	BinaryTreeNode<T>* top = s.top();	cout<<top->_data<<" ";	s.pop();	if (top->_right)	s.push(top->_right);	if (top->_left)	s.push(top->_left);	}	cout<<endl; } 

2.中序遍历：

void InOrder()	{	_InOrder(_root);	cout<<endl;	}         void _InOrder(BinaryTreeNode<T>* root)	{	if (root == NULL)	return;	_InOrder(root->_left);	cout<<root->_data<<" ";	_InOrder(root->_right);	}	void InOrder_Non_R()	{	stack<BinaryTreeNode<T>*> s;	BinaryTreeNode<T>* cur = _root;	while (cur || !s.empty())	{	// 1.压左节点	while (cur)	{	s.push(cur);	cur = cur->_left;	}	// 取栈顶节点数据访问	// 前序遍历top节点的右树	if (!s.empty())	{	BinaryTreeNode<T>* top = s.top();	s.pop();	cout<<top->_data<<" ";	cur = top->_right;	}	}	cout<<endl;	}

3.后序遍历：

       	void PostOrder()	{	_PostOrder(_root);	cout<<endl;	}                 void _PostOrder(BinaryTreeNode<T>* root)	{	if (root == NULL)	return;	_PostOrder(root->_left);	_PostOrder(root->_right);	cout<<root->_data<<" ";	}	void PostOrder_Non_R()	{	stack<BinaryTreeNode<T>*> s;	BinaryTreeNode<T>* cur = _root;	BinaryTreeNode<T>* prevVisited = NULL;	while (cur || !s.empty())	{	// 1.压左节点	while (cur)	{	s.push(cur);	cur = cur->_left;	}	BinaryTreeNode<T>* top = s.top();	if (top->_right == NULL 	|| top->_right == prevVisited)	{	cout<<top->_data<<" ";	s.pop();	prevVisited = top;	}	else	{	cur = top->_right;	}	}	cout<<endl;	}

4.层次遍历

void LevelOrder()	{	queue<BinaryTreeNode<T>* > q;	if (_root)	q.push(_root);	while(!q.empty())	{	BinaryTreeNode<T>* front = q.front();	cout<<front->_data<<" ";	q.pop();	if (front->_left)	q.push(front->_left);	if (front->_right)	q.push(front->_right);	}	cout<<endl;	}

以上