HDu1710(二叉树)

[java]
package D0726; 
 
import java.util.Scanner; 
 
public class HDU1710 { 
 
    static String str; 
 
    public static void main(String[] args) { 
        Scanner sc = new Scanner(System.in); 
        String[] strpre;//这里要用数组接受输入 
        String[] strin; 
        int n; 
        while (sc.hasNext()) { 
            n = sc.nextInt(); 
            strpre = new String[n]; 
            strin = new String[n]; 
            str = ""; 
            for (int i = 0; i < n; i++) 
                strpre[i] = sc.next(); 
            for (int i = 0; i < n; i++) 
                strin[i] = sc.next(); 
            Node3 node = buildTree(strpre, strin); 
            postOrder(node); 
            System.out.println(str.trim()); 
        } 
    } 
 
    // 建立二叉树 
    public static Node3 buildTree(String[] strpre, String[] strin) { 
        if (strpre.length <= 0) 
            return null; 
 
        // 建立一个根节点 
        String s = strpre[0]; 
        Node3 root = new Node3(s); 
        // 以根节点为中心，将中序分为两个子序列 
        int i, index = 0; 
        for (i = 0; i < strin.length; i++) { 
            if (strin[i].equals(s)) { 
                index = i; 
                break; 
            } 
        } 
        String[] leftin = new String[index]; 
        String[] rightin = new String[strin.length - index - 1]; 
        for (i = 0; i < index; i++) 
            leftin[i] = strin[i]; 
        int j = index+1; 
        for (i = 0; j < strin.length; i++,j++)  
            rightin[i] = strin[j]; 
        // 根所左中序的长度，将先序分为左右两个子先序 
        int leftlen = leftin.length; 
        String[] leftpre = new String[leftlen]; 
        String[] rightpre = new String[strpre.length - leftlen - 1]; 
        for (i = 0; i < leftlen; i++) 
            leftpre[i] = strpre[i + 1]; 
        for (i = 0; i < strpre.length - leftlen - 1; i++) 
            rightpre[i] = strpre[i + leftlen + 1]; 
        root.lChild = buildTree(leftpre, leftin); 
        root.rChild = buildTree(rightpre, rightin); 
        return root; 
    } 
 
    // 后序遍历 
    public static void postOrder(Node3 node) { 
        if (node != null) { 
            postOrder(node.lChild); 
            postOrder(node.rChild); 
            str += " " + node.data; 
        } 
    } 
} 
 
class Node3 { 
    public String data; 
    public Node3 lChild; 
    public Node3 rChild; 
 
    public Node3(String data) { 
        this.data = data; 
        this.lChild = null; 
        this.rChild = null; 
    } 
} 
作者：lhfight

补充：软件开发 , Java ,