二叉树——前序遍历的递归与非递归算法

前序遍历按照“根结点-左孩子-右孩子”的顺序进行访问。

1. 递归实现

   /**
    * 前序遍历
    * @param node
    */
   public static void preOrderTraverse(Node node) {
       if (node == null) return;
       System.out.print(node.data + "\t");
       preOrderTraverse(node.leftNode);
       preOrderTraverse(node.rightNode);
   }

2. 非递归实现

根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。即对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子不为空，按相同规则访问它的左子树；当访问其左子树时，再访问它的右子树。因此其处理过程如下：

1. 访问结点P，并将结点P入栈;
2. 判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1);若不为空，则将P的左孩子置为当前的结点P;
3. 直到P为NULL并且栈为空，则遍历结束。

   /**
    * 前序遍历 非递归
    * @param node
    */
   public static void nonRecInOrder(Node node) {
       Stack<Node> stackNode = new Stack<Node>();
       Node d = node;
       while (d != null || stackNode.size() > 0) {
           while (d != null) {
               System.out.print(d.data + "\t");
               stackNode.push(d);
               d = d.leftNode;
           }

           while (stackNode.size() > 0) {
               d = stackNode.pop();
               d = d.rightNode;
           }
       }
   }