java分别使用递归和非递归实现二叉树中序遍历

对于二叉树，它的特点就是任何一个节点，左节点小于父节点、右节点大于父节点遍历二叉树有多种方式，如中序遍历、层序遍历、后序遍历，中序遍历的思路就是左-->父--->右的顺序，下面给出递归和非递归的两种方法，递归很好理解，非递归就是一直找到最左节点，然后回溯节点，如果存在右节点，则重复上述过程

如将下面的二叉树使用中序遍历输出有序数组

代码如下

import JAVA.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
 * 中序遍历的非递归和递归的实现
 * 
 * @author ssj
 *
 */
public class MiddleList {
	public static void main(String[] args) {
		// 创建一颗二叉树
		Node root = new Node("10");
		Node n6 = new Node("6");
		Node n14 = new Node("14");
		n6.setParent(root);
		n14.setParent(root);
		root.setLeft(n6);
		root.setRight(n14);
		Node n4 = new Node("4");
		Node n8 = new Node("8");
		n6.setLeft(n4);
		n6.setRight(n8);
		Node n12 = new Node("12");
		Node n16 = new Node("16");
		n14.setLeft(n12);
		n14.setRight(n16);
		System.out.println("---------递归遍历结果--------------------");
		List list = new ArrayList();
		middleListDG(root, list);
		System.out.println(list);
		System.out.println("---------非递归遍历结果--------------------");
		List list2 = middleList(root);
		System.out.println(list2);
	}
	/**
	 * 递归中序遍历
	 * 
	 * @param root
	 * @return
	 */
	public static void middleListDG(Node root, List list) {
		if (root == null) {
			return;
		}
		middleListDG(root.left, list);
		list.add(root.name);
		middleListDG(root.right, list);
	}
	/**
	 * 非递归中序遍历
	 * @param root
	 * @return
	 */
	public static List middleList(Node root) {
		Stack<Node> sk = new Stack<Node>();
		List list = new ArrayList();
		Node n = root;
		while (n != null) {
			// 一直找到最左边的节点
			while (n != null) {
				sk.push(n);
				n = n.left;
			}
			// 输出最左边的节点
			while (!sk.empty()) {
				Node n2 = sk.pop();
				list.add(n2.getName());
				// 如果该节点存在右节点，先输出所有的右节点，即重复以上过程
				if (n2.right != null) {
					n = n2.right;
					break;
				}
			}
		}
		return list;
	}
}
/**
 * 树节点
 * @author ssj
 *
 */
class Node {
	public String name;
	public Node left;
	public Node right;
	public Node parent = null;
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public Node getParent() {
		return parent;
	}
	public void setParent(Node parent) {
		this.parent = parent;
	}
	public Node(String name) {
		super();
		this.name = name;
	}
	public Node getLeft() {
		return left;
	}
	public void setLeft(Node left) {
		this.left = left;
	}
	public Node getRight() {
		return right;
	}
	public void setRight(Node right) {
		this.right = right;
	}
}

输出结果