二叉树先序遍历：中 左 右
二叉树中序遍历： 左 中 右
二叉树后序遍历： 左 右 中
本文以二叉树的先序遍历为例，讲解递归和非递归两种方法求解。
首先给出二叉树节点的结构
struct Node {
int value;
Node left;
Node right;
Node(int x) {this.value = x;}
};
例：二叉树如图所示
1
/ \
2 3
/ \ / \
4 5 6 7
1. 递归求解方法比较简单如下所示：
打印二叉树的先序遍历结果
void PreOrder(Node head) {
std::cout<<head.value<<" ";
PreOrder(head.left);//递归打印左子树
PreOrder(head.right);//递归打印右子树
}
2.非递归求解
(1). 使用stack来实现。首先将head压入栈，每次将栈顶元素弹出，记为cur，打印cur的值。然后，如果右节点不为空，将cur的右节点压入栈，如果左节点不为空，将其左节点压入栈，当栈为空时循环结束! 本方法是在出栈的时候实现打印输出。
void preOrder(Node head) {
stack<Node> s;
s.push(head);
while(!s.empty()) {
Node temp = s.top();
s.pop();
std::cout<<temp.value<<std::endl;
if( temp.right) s.push(temp.right);
if( temp.left) s.push(temp.left);
}
}
(2). 还是使用stack.不过这个稍微不同，是先将所有的最左节点入栈，例如1，2，4先入栈，然后将栈顶元素弹出，并记为cur，如果cur的右节点不为空，则将右节点入栈，并循环将右节点的左子节点入栈。此方法是入栈时打印输出节点值。此方法依据先序遍历 1 2 4 5 3 6 7的顺序，依次入栈。
void preOrder(Node head) {
stack<Node> s;
while(head) {
s.push(head);
std::cout<<head.value<<std::endl;
head = head.left;
}
while(!s.empty()) {
Node temp = s.top().right;
s.pop();
while (temp) {
s.push(temp);
std::cout<<temp.value<<std::endl;
temp = temp.left;
}
}
}
