已知一个二叉树的前序、中序遍历求其后续遍历 Java代码实现

如题，好像大学的课后作业。写一个练练手。网上不少，大多都是C或C++的。

 

一个二叉树前序遍历：GDAFEMHZ

                  中序遍历：ADEFGHMZ

求其后续遍历。

 

求解过程

0.这三种遍历不知道是什么意思的请自行搜索。

1.通过前序遍历我们可知此树根节点为G（即前序遍历第一个字符）

2.观测中序遍历可知此树左子树所有节点为：ADEF  右子树所有节点为：HMZ（以根节点划分）

3.得到左子树的前序遍历（DAFE）中序遍历（ADEF） 顺序未变。

4.得到右字数的前序遍历（MHZ）中序遍历（HMZ） 顺序未变。

5.递归此过程，展开所有子树。

 

代码如下：

    定义二叉树的类

public class Tree {
	
	 String root = "";//根节点
	 Tree left;       //左子树
	 Tree right;      //右子树
	 
	 String pre = "";//前序遍历字符串
	 String in = "";//中序遍历字符串
	 String back = "";//后序遍历字符串
	
	Tree(String s){
		this.root = s;
	}
	
	Tree(){}
	
}

 

    实现代码：

   

public class testTree {
	
	
	public static String post = "";

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String pre = "GDAFEMHZ";
		String in = "ADEFGHMZ";
		Tree t = new Tree();
		t.root = in;
		t.pre = pre;
		
		build(t);
		System.out.println(post);
		
		
	}
	
	
	/**
	 * 采取后序遍历递归展开所有节点
	 * @param tree
	 */
	public static void build(Tree tree){
		

		if(tree == null){
			return;
		}
		open(tree);
		if(tree.left != null){
			open(tree.left);
			build(tree.left);
		}
		if(tree.right != null){
			open(tree.right);
			build(tree.right);
		}
		post = post + tree.root;
	}
	
	
	/**
	 * 将节点不是单字符的节点展开
	 * @param tree
	 */
	
	public static void open(Tree tree){
		if(tree.root.length()>1){
			String s2 = tree.root;
			String s1 = tree.pre;
			 
			tree.root =s1.substring(0, 1);
			String [] node = s2.split(tree.root);
			if(node.length>=2){
				tree.left = new Tree(node[0]);
				tree.left.pre = s1.substring(1, node[0].length()+1);
				tree.right = new Tree(node[1]);
				tree.right.pre = s1.substring(s1.length()-node[1].length(), s1.length());
			}

		}
	}

}