PosOrderRecur

---

public void PosOrderRecur(Node node){
  if(head == null){
     return;
   }
  posOrderRecur(head.left);//打印左孩子
  posOrderRecur(head.right);//打印右孩子
  sysout(head.value+""); //打印头结点
}

非递归的实现方式: 原理:

1. 申请一个栈,记为S1,然后将头结点压入S1中.
2. 从S1中弹出的节点记为cur,然后把cur的左孩子压入S1中,然后把cur1的右孩子压入S1中.
3. 在整个过程,每一个从S1中弹出的节点,都放进第二个栈S2中.
4. 不断重复2,3,一直到S1为null,过程停止
5. 从S2中一次弹出节点并打印,打印的顺序就是后续遍历的顺序了.

初始树:

            1
          /   \
         2     3
        / \   / \   
       4  5   6  7 
使用2个栈完成的过程
|  |   |  | 
----   ----
栈S1 与 栈S2
先把node1压入S1,令node1=cur,弹出node1并压入S2中,
| 1  |  |   |
-----   ------
S1       S2
接下来先压入cur=node1的左孩子node2,再压入右孩子node3进入S1中, 弹出node3压入S2
|  3 |
------
|  2 |  | 1  |
-----   ------
S1       S2

再压入cur=node3的左孩子node6和右孩子node7,弹出node7压入到S2中,
cur=node7没有孩子,所以弹出node6将它压入到S2中.
|  7  |              
-----
|  6 |  | 3  |
------  -----
|  2 |  | 1  |
-----   ------
S1       S2

变为    
        |  6 |
        ------
        |  7 |
        ------
        | 3  |
------  -----
|  2 |  | 1  |
-----   ------
S1       S2
node6没孩子,弹出node2压入栈S2
再把node2的孩子压入S1
        |  2 |
        ------
        |  6 |
        ------
        |  7 |
        ------
|  5 |  | 3  |
------  -----
|  4 |  | 1  |
-----   ------
S1       S2

最终压入S2的数是:4 5 2 6 7 3 1

用一个栈来实现的方法