二叉树的遍历

二叉树的层序遍历
二叉树的先序，中序，后序遍历 递归版本
二叉树的先序，中序，后序遍历 非递归版本

import java.util.*;
import java.lang.*;

public class TreeTravese {
	public static TreeNode createTree(int nums) {
		// int nums = 7;
		/*
			1
		  2   3
		 4 5 6 7
		*/
		int curNum = 1;
		TreeNode root = new TreeNode(curNum);
		Queue<TreeNode> Q = new LinkedList<TreeNode>();
		Q.offer(root);
		while( curNum <= nums || !Q.isEmpty() ) {
			TreeNode node = Q.poll();
			if ( node == null ) break;

			TreeNode leftNode = null;
			TreeNode rightNode = null;
			if (++curNum <= nums)
				leftNode = new TreeNode(curNum);
			if (++curNum <= nums)
				rightNode = new TreeNode(curNum);
			node.left = leftNode;
			node.right = rightNode;

			Q.offer(leftNode);
			Q.offer(rightNode);
		}
		Q = null;
		return root;
	}

	//递归版本
	public static void preOrderRecursion(TreeNode root) {
		if (root == null) return;

		visitNode(root);
		preOrderRecursion(root.left);
		preOrderRecursion(root.right);
	}

	public static void inOrderRecursion(TreeNode root) {
		if (root == null) return;

		inOrderRecursion(root.left);
		visitNode(root);
		inOrderRecursion(root.right);
	}

	public static void postOrderRecursion(TreeNode root) {
		if (root == null) return;

		postOrderRecursion(root.left);
		postOrderRecursion(root.right);
		visitNode(root);
	}

	//非递归， 栈版本
	public static void preOrderStack(TreeNode root) {
		if (root == null) 
			return;
		Stack<TreeNode> S = new Stack<>();
		TreeNode p = root;
		while( p != null || !S.empty() ) {
			while( p != null ) {
				visitNode(p);
				S.push(p);
				p = p.left;
			}

			p = S.pop();
			p = p.right;
		}
		S = null;
	}

	public static void inOrderStack(TreeNode root) {
		if (root == null) return;

		Stack<TreeNode> S = new Stack<>();
		TreeNode p = root;
		while( p != null || !S.empty() ) {
			while( p != null ) {
				S.push(p);
				p = p.left;
			}

			p = S.pop();
			visitNode(p);
			p = p.right;
		}
		S = null;
	}

	public static void postOrderStack(TreeNode root) {
		if (root == null) return;

		Stack<TreeNode> S = new Stack<>();
		TreeNode p = root;
		TreeNode preNode = null;
		while( p != null || !S.empty() ) {
			while( p != null ) {
				S.push(p);
				p = p.left;
			}

			p = S.peek();
			if ( p.right != null && p.right != preNode) { //右孩子未访问
				p = p.right;
				S.push(p);
				p = p.left;
			}
			else {
				visitNode(p);
				preNode = p;
				S.pop();
				p = null;
			}
		}
		S = null;
	}

	//层序遍历
	public static void levelTravese(TreeNode root) {
		if (root == null) return;

		Queue<TreeNode> Q = new LinkedList<TreeNode>();
		Q.offer(root);
		while( !Q.isEmpty() ) {
			TreeNode front = Q.poll();
			visitNode(front);

			if (front.left != null) Q.offer(front.left);
			if (front.right != null) Q.offer(front.right);
		}
		Q = null;
	}

	public static void visitNode(TreeNode node) {
		System.out.printf("%d ", node.val);
	}
	public static void main(String[] args) {
		TreeNode root = createTree(8);
		
		System.out.println("===levelTravese===");
		levelTravese(root);
		System.out.println();

		System.out.println("===preOrderRecursion===");
		preOrderRecursion(root);
		System.out.println();

		System.out.println("===preOrderStack===");
		preOrderStack(root);
		System.out.println();

		System.out.println("===inOrderRecursion===");
		inOrderRecursion(root);
		System.out.println();

		System.out.println("===inOrderStack===");
		inOrderStack(root);
		System.out.println();

		System.out.println("===postOrderRecursion===");
		postOrderRecursion(root);
		System.out.println();

		System.out.println("===postOrderStack===");
		postOrderStack(root);
		System.out.println();
	}
}

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	public TreeNode(int val) {
		this.val = val;
		this.left = null;
		this.right = null;
	}
}