preorder在树后序 [英] Preorder to postorder in tree

问题描述

我有一个问题我想从序和preorder创建后序，但我不瓦纳使用重建树，我想只有递归做到这一点。 I $ C C这个$，在这一刻，有我的，右边的树在preorder（部分第一个字符在preorder的根，我发现这序，我有左，右身边，我recurency转化为右侧），但我有树的左边的一个问题。我不也没办法做到这一点。有人可以给我一些建议或code？请帮助：）

解决方案

 公共静态字符串一（字符串pre，字符串中，诠释开始，诠释完）{
            焦炭C = pre.charAt（开始）; //在preorder第一个字符是根
            INT九=查找（pre中，C）; //如果我们发现这个字符在序翻译，我们知道在哪里的左右侧树
            叠+ = C;
            如果（开始== 0安培;＆安培; FLAGA ==真）{
                左= pre.substring（1，IX + 1）;
                右= pre.substring（IX + 1，结束）;
                FLAGA = FALSE;
                返回（右，中，0，结束）;
            }
            字符串反转=新的StringBuffer（STOS）.reverse（）的toString（）。
    //堆栈看
//的System.out.println（堆栈+ STOS）;
            如果（开始＆LT; right.length（） -  1）{
                返回（右，中，启动+ 1，结束 -  1）;
            }
            返回 ;
     }
    公共静态INT发现（一个字符串，字符串B，字符C）{
        INT b_l = b.length个（）;
        的for（int i = 0; I＆LT; b_l ++ I）
            如果（b.charAt（一）== C）
                返回我;
        返回-1;
 

第一个测试： 字符串pre =FBADCEGIH; 串序=ABCDEFGHI; 答案应该是：// A，C，E，D，B，H，I，G，F 我的问题是树的左边，我没有任何想法要做到这一点正确的，我不知道为preorder所有的情况我的code工作和序。

I have a question i want to create postorder from inorder and preorder, but i don't wana use reconstruction of tree, i want only recursive do this. I code this, and at this moment, i have a part of, right side of tree in preorder( First char in preorder is root, i find this in inorder, and i have left and right side, i recurency translate to right side), but i have a problem with left side of tree. I don't have no idea to do this. Can someone give me some of suggestion or code ? Please help :)

解决方案

 public static String a(String pre, String in, int start, int end) {
            char c = pre.charAt(start); //first char in preorder is root
            int ix = find(pre, in, c); // if we find this char in inorder translation we know where is left and right side of tree
            stack += c;
            if (start == 0 && flaga == true) {
                left = pre.substring(1, ix + 1);
                right = pre.substring(ix + 1, end);
                flaga = false;
                return a(right, in, 0, end);
            }
            String reverse = new StringBuffer(stos).reverse().toString();
    //stack to see
//        System.out.println("STACK " + stos);
            if (start < right.length()-1) {
                return a(right, in, start + 1, end - 1);
            }
            return ""; 
     }
    public static int find(String a, String b, char c) {
        int b_l = b.length();
        for (int i = 0; i < b_l; ++i)
            if (b.charAt(i) == c)
                return i;
        return -1;

First Test : String pre = "FBADCEGIH"; String inorder = "ABCDEFGHI"; ANswer should be : //A, C, E, D, B, H, I, G, F My problem is with left side of tree, i don't have any idea to do this correct, and i'm not sure my code work for all situation of preorder and inorder.

这篇关于preorder在树后序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！