buildtree.java

PKU中一些数据结构基本算法题的java实现

package OTHERS;

import java.util.Scanner;

public class BuildTree {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		String preOrder = cin.next();
		String midOrder = cin.next();
		Node root = buildTree(preOrder,midOrder);
		printPostOrder(root);
		

	}

	static void printPostOrder(Node root){
		if(root == null){
			return;
		}
		printPostOrder(root.left);
		printPostOrder(root.right);
		System.out.print(root.value);
	}
	static Node buildTree(String preOrder, String midOrder){
		if(preOrder.length()==0){
			return null;
		}
		else if(preOrder.length()==1){
			return new Node(preOrder.charAt(0));
		}
		char ch = preOrder.charAt(0);
		Node parent = new Node(ch);
		int index = midOrder.indexOf(ch);
		String leftMidOrder = midOrder.substring(0,index);
		String rightMidOrder = midOrder.substring(index+1);
		
		String leftPreOrder = preOrder.substring(1, 1+leftMidOrder.length());
		String rightPreOrder = preOrder.substring(1+leftMidOrder.length());
		
		Node leftSon = buildTree(leftPreOrder,leftMidOrder);
		Node rightSon = buildTree(rightPreOrder,rightMidOrder);
		parent.left = leftSon;
		parent.right = rightSon;
		return parent;
	}
	
}

class Node{
	Node left;
	Node right;
	char value;
	public Node(char value) {
		super();
		this.value = value;
	}
}