PreOrderRecur

---

用递归方式来实现二叉树的先序的遍历打印.

public void preOrderRecur(Node head){
  if(head == null){
     return;
   }
   sysout(head.value()+"");//先打印头节点
   preOrderRecur(head.left);//遍历左子树
   preOrderRecur(head.right);//再遍历右子树
  
}

非递归的形式遍历 过程:

1. 首先申请一个新的栈,记为stack.
2. 然后将头结点head压入stack中
3. 每次从stack中弹出栈顶节点,记为cur,然后打印cur的值. 如果cur右孩子不为null,将cur的右孩子压入stack中. 最后如果cur的左孩子不为null的话,将cur的左孩子压入stack中.
4. 不断重复步骤3,直到stack为null,全部过程结束.

初始树如下:
            1
          /   \
         2     3
        / \   /  \
      4    5  6   7

第一步 
申请一个新的栈stack,栈的规则是先进后出.
                      弹出打印 1
       |   1   |      --------->
       --------
         stack 
    把node1压入栈中,弹出并打印它
    
    规则: 
    每次从stack中栈顶节点记为cur,然后打印cur的值.
    如果cur右孩子不为null的话,先将cur的右孩子先压入stack中.
            最后如果cur的左孩子不为null的话,将cur的左孩子压入stack中.
第二步:
把node1的左孩子和右孩子压入栈中
   |  2  |         弹出栈顶node2的值
   ------            -------->
   |  3  |         发现node2有左孩子和右孩子,所以先压入node2的右孩子,再压入node2的左孩子
   -----
                    结果如下
             
                    |   4   |          依次弹出栈顶的node4的值
                     ------            弹出栈顶的node5的值
                    |   5   |          弹出栈顶的node3的值
                    --------           ------------>  
                    |    3  |          现在发现node4,5都没左右节点,只有node3还有左右节点6,7 
                    --------
                     所以进行下一步压栈过程 
                     |   6   |           
                     --------           先弹出node6
                     |   7   |        ----------->
                     --------            在弹出node7
           根据弹出结果的顺序:
           先序遍历的结果是:1 2 4 5 3 6 7