二叉树遍历

	/**
	 * 先序遍历 根左右
	 *
	 * @param root
	 */
	public void traverse1(TreeNode root) {
		if (root == null) {
			return;
		}
		System.out.print(root.value + "-->");
		if (root.left != null) {
			traverse1(root.left);
		}
		if (root.right != null) {
			traverse1(root.right);
		}
	}

	/**
	 * 先序遍历 根左右 非递归
	 *
	 * @param root
	 */
	public void traverse11(TreeNode root) {
		if (root == null) {
			return;
		}
		Stack<TreeNode> stack = new Stack<>();
		stack.push(root);
		while (!stack.isEmpty()) {
			TreeNode pop = stack.pop();
			System.out.print(pop.value + "-->");
			if (pop.right != null) {
				stack.push(pop.right);
			}
			if (pop.left != null) {
				stack.push(pop.left);
			}
		}
	}


	/**
	 * 中序
	 *
	 * @param root
	 */
	public void traverse2(TreeNode root) {
		if (root == null) {
			return;
		}
		if (root.left != null) {
			traverse2(root.left);
		}
		System.out.print(root.value + "-->");
		if (root.right != null) {
			traverse2(root.right);
		}
	}

	/**
	 * 中序遍历 根左右 非递归
	 *
	 * @param root
	 */
	public void traverse22(TreeNode root) {
		if (root == null) {
			return;
		}
		Stack<TreeNode> stack = new Stack<>();
		TreeNode node = root;
		while (node != null || !stack.isEmpty()) {
			while (node != null) {
				stack.push(node);
				node = node.left;
			}
			node = stack.pop();
			System.out.print(node + "-->");
			node = node.right;
		}
	}


	/**
	 * 后序
	 *
	 * @param root
	 */
	public void traverse3(TreeNode root) {

		if (root == null) {
			return;
		}
		if (root.left != null) {
			traverse3(root.left);
		}
		if (root.right != null) {
			traverse3(root.right);
		}
		System.out.print(root.value + "-->");
	}

	/**
	 * 后序 非递归
	 * @param treeNode
	 */
	private void traverse33(TreeNode treeNode) {
		Stack<TreeNode> stack = new Stack<>();
		TreeNode node = treeNode;
		TreeNode lastNode = null;

		while (node != null || !stack.isEmpty()) {
			while (node != null) {
				stack.push(node);
				node = node.left;
			}
			node = stack.pop();
			// 当前结点没有右结点或上一个结点（已经输出的结点）是当前结点的右结点，则输出当前结点
			while (node.right == null || node.right == lastNode) {
				System.out.print(node.value + "-->");
				lastNode = node;
				if (stack.isEmpty()) {
					return;
				}
				node = stack.pop();
			}
			stack.push(node);//还有右结点没有遍历
			node = node.right;
		}
	}
	
	/**
	 * 广度优先遍历二叉树，又称层次遍历二叉树
	 * @param node
	 */
	public void breadthFirstTraverse(Node<E> root) {
		Queue<Node<E>> queue = new LinkedList<Node<E>>();
		Node<E> currentNode = null;
		queue.offer(root);
		while (!queue.isEmpty()) {
			currentNode = queue.poll();
			System.out.print(currentNode.value + " ");
			if (currentNode.left != null)
				queue.offer(currentNode.left);
			if (currentNode.right != null)
				queue.offer(currentNode.right);
		}
	}