先序中序后序遍历二叉树

分别采用递归和非递归的方法实现二叉树的先序、中序、后序遍历并输出遍历序列；

递归：

        三者的递归实现方法相近，修改语句以顺序以改变遍历顺序即可；

迭代：（迭代实现三种遍历都用到栈）

        先序：迭代实现先序遍历的时候，结点第一次被访问到就输出（从栈中弹出并输出值），其次要注意入栈时应该由于栈后进先出的特性右子树先入栈，然后左子树入栈；

        中序：迭代实现中序遍历的时候，结点第二次被访问到时输出，故先找到最左下方的结点，然后进行操作；

        后序：中序遍历的差别在于从左孩子走到根节点后不是急着输出根节点，而是再进入右结点，之后再返回，这样根节点会被访问到两次（结点第三次被访问时输出）,设置指向上一个被访问结点的标志pre，限制它只能访问一次右孩子。

//递归实现先序、中序、后序遍历 
void PreOrder(Tree &t){
	if(t == NULL) return;
	cout << t->val << " ";
	PreOrder(t->left);
	PreOrder(t->right);
} 

//中序
void InOrder(Tree &t){
	if(t == NULL) return;
	PreOrder(t->left);
	cout << t->val << " ";
	PreOrder(t->right);
}

//后序
void LastOrder(Tree &t){
	if(t == NULL) return;
	LastOrder(t->left);
	LastOrder(t->right);
	cout << t->val << " ";
} 

//先序遍历迭代输出 
void preOrder(Tree &t){
	if(t == NULL) return;
	stack s;
	s.push(t);
	while(!s.empty()){
		TreeNode* p = s.top();
		s.pop();
		cout << p->val << " ";
		//右子树非空先压栈 
		if(t->right != NULL) s.push(t->right);
		//左子树非空压栈 
		if(t->left != NULL) s.push(t->left);
	} 
} 

//中序遍历迭代输出
void inOrder(Tree &t){
	if(t == NULL) return;
	stack s;
	TreeNode* p = t;
	while(p != NULL || !s.empty()){
		//左孩子不为空就一直向前
		while(p != NULL){
			s.push(p);
			p = p->left;
		} 
		p = s.top();
		s.pop();
		cout << p->val << " ";
		//走向右孩子
		p = p->right;
	}
} 

//后序遍历迭代输出
void lastOrder(Tree &t){
	if(t == NULL) return;
	stack s;
	TreeNode* p = t;
	TreeNode* pre = NULL;
	//设置指向上一个被访问结点的标志pre，限制它只能访问一次右孩子 
	while(p != NULL || !s.empty()){
		while(p != NULL){
			s.push(p);
			p = p->left;
		}
		p = s.top();	//此时查看的是最左边的叶子结点 
		if(p->right == NULL || p->right == pre){
			//如果右孩子为空或者被访问过，访问根节点 
			cout << p->val << " ";
			s.pop();
			pre = p;
			p = NULL; 
		}
		//右孩子非空且未被访问过
		else p = p->right; 
	}
}

1.迭代实现二叉树的遍历时用到栈；

2.结点入栈时注意栈的后进先出特性；

3.后续补充；