根据二叉树的前序和中序获得后序，后序和中序获得前序

根据二叉树的前序和中序获得后序，后序和中序获得前序的实现。可以用递归，呵呵！

下面是我写的测试程序：

package algorithm;

public class BTree {

	private static StringBuilder postOrderReverse = new StringBuilder();// 储存后序的一个逆行
	private static StringBuilder preOrder = new StringBuilder();// 储存前序

	/**
	 * 根据先序和中序，获得后序
	 * 
	 * @param preOrder
	 * @param inOrder
	 */
	public static void getPostOrder(String preOrder, String inOrder) {

		if (preOrder.length() == 1 && inOrder.length() == 1) {
			postOrderReverse.append(preOrder);
			return;
		}

		char root = preOrder.charAt(0);
		int rootIndex = -1;
		String left_InOrder = null;
		String left_preOrder = null;
		String right_Inorder = null;
		String right_preOrder = null;

		postOrderReverse.append(root);// 将跟节点放入

		rootIndex = inOrder.indexOf(root);
		left_InOrder = inOrder.substring(0, rootIndex);// 左子树 的中序
		right_Inorder = inOrder.substring(rootIndex + 1);// 右子树的中序

		preOrder = preOrder.substring(1);
		int size = left_InOrder.length();
		int index = -1;
		for (int i = 0; i < size; ++i) {
			int tmp = preOrder.indexOf(left_InOrder.charAt(i));
			if (index < tmp)
				index = tmp;
		}

		left_preOrder = preOrder.substring(0, index + 1);// 左子树前序
		right_preOrder = preOrder.substring(index + 1);// 右子树前序

		if (right_preOrder != null && !right_Inorder.equals(""))
			getPostOrder(right_preOrder, right_Inorder);

		if (left_preOrder != null && !left_preOrder.equals(""))
			getPostOrder(left_preOrder, left_InOrder);
	}

	/**
	 * 根据后序和中序 ，获得先序
	 * 
	 * @param postOrder
	 * @param inOrder
	 */
	public static void getPreOrder(String postOrder, String inOrder) {

		if (postOrder.length() == 1 && inOrder.length() == 1) {
			preOrder.append(postOrder);
			return;
		}

		String root = postOrder.substring(postOrder.length() - 1);
		int rootIndex = -1;
		String left_InOrder = null;
		String left_postOrder = null;
		String right_Inorder = null;
		String right_postOrder = null;

		preOrder.append(root);

		rootIndex = inOrder.indexOf(root);
		left_InOrder = inOrder.substring(0, rootIndex);// 左子树中序
		right_Inorder = inOrder.substring(rootIndex + 1);// 右子树中序

		int index = -1;
		int size = left_InOrder.length();
		for (int i = 0; i < size; ++i) {
			int tmp = postOrder.indexOf(left_InOrder.charAt(i));
			if (tmp > index)
				index = tmp;
		}

		left_postOrder = postOrder.substring(0, index + 1);// 左 子树后序
		right_postOrder = postOrder
				.substring(index + 1, postOrder.length() - 1);// 右子树后序

		if (left_InOrder != null && !left_InOrder.equals("")
				&& left_postOrder != null && !left_postOrder.equals(""))
			getPreOrder(left_postOrder, left_InOrder);
		if (right_Inorder != null && !right_Inorder.equals("")
				&& right_postOrder != null && !right_postOrder.equals(""))
			getPreOrder(right_postOrder, right_Inorder);
	}

	public static void main(String[] args) {
		getPostOrder("BCAD", "CBAD");
		System.out.println(postOrderReverse.reverse());
		getPreOrder("ACBFGED", "ABCDEFG");
		System.out.println(preOrder);
	}
}