用递归和非递归两种方式实现二叉树的先序遍历（前序遍历）

一、分析

先序遍历（前序遍历）遍历顺序为：根、左、右。

二、递归实现

public class Node{
	public int value;
  public Node left;
  public Node right;
  
  public Node(int data){
  	this.value = data;
  }
}

public void preOrderRecur(Node head){
	if(head == null){
  	return;
  }
  System.out.println(head.value + " ");
  preOrderRecur(head.left);
  preOrderRecur(head.right);
}

三、非递归实现

3.1 问题分析

用递归方法解决的问题都能用非递归方法实现，这是因为递归方法无非就是利用函数栈来保存信息，如果用自己申请的数据结构来代替函数栈，也可以实现相同的功能。

用递归方式实现二叉树的前序遍历过程如下：

1、申请一个新的栈，记为stack。然后将头节点head压入stack中。

2、从stack中弹出栈顶节点，记为cur，然后打印cur节点的值，再将cur的右子节点（不为空的话）压入栈中，最后将cur的左子节点（不为空的话）压入stack中。

3、不断重复步骤2，直到stack为空，全部过程结束。

代码如下：

public class Node{
	public int value;
  public Node left;
  public Node right;
  
  public Node(int data){
  	this.value = data;
  }
}

public void preOrderunRecur(Node head){
	if(head != null){
  	System.out.println(head.value + " ");
    Stack<Node> stack = new Stack<Node>;
    stack.add(head);
    while(!stack.isEmpty()){
    		head = stack.pop();
        System.out.println(head.value + " ");
        if(head.right != null){
        	stack.push(head.right);
        }
        if(head.left != null){
        	stack.push(head.left);
        }
    }
  }
  System.out.println();
}