用递归和非递归两种方式实现二叉树的中序遍历

一、分析

中序遍历遍历顺序为：左、根、右。

二、递归实现

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

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

三、非递归实现

3.1 问题分析

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

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

1、申请一个新的栈，记为stack。

2、然后将头节点head压入stack中，依次把左边界压入栈中，即head = head.left; 然后重复步骤2。

3、不断重复步骤2，直到head为空，此时从stack栈中弹出一个节点，记为node。打印node的值，并且让cur = node.right，然后继续重复步骤2。

4、当stack为空且cur为空时，整个过程停止。

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

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