La parenthèse de BinTree à BinTree

Question

Salut à tous, J'écris un programme qui prend une représentation sous forme de chaîne d'un arbre binaire et en crée un arbre. Le code me semble tout à fait logique mais il ne fera toujours pas ce qu'il devrait faire. Merci tout le monde. Voici le code:

(((()B(C))D(E))F(G))J(()K((L)M(T)))

private static BinTree<String> findRoot(String s){ 
String tree = s; 
    int i = 0; 
    int count = 0; 
    String root; 
    if(tree.equalsIgnoreCase("()")){ 
     return null; 
    } 
    if(tree.length()==3){ 
     return new BinTree<String>(Character.toString(tree.charAt(1))); 
    } 
    while(i<tree.length()){ 
     if(tree.charAt(i)=='('){ 
      count++; 
     } 
     if(tree.charAt(i)==')'){ 
      count--; 
      if(count==0){ 
       i++; 
       root = Character.toString(tree.charAt(i)); 
       return new BinTree<String>(root, findRoot(tree.substring(1, i-1)), findRoot(tree.substring(i+1))); 
      } 
     } 
     i++; 
    } 
    return null; 
} 

Answer 1

débogage Démarrer en inspectant les valeurs de s pour chaque appel à findRoot(). Le code semble bon, sauf que j'ai l'impression que vous avez des erreurs hors-un dans vos paramètres substring().

Answer 2

Je vois que lorsque vous avez trouvé votre racine, vous appelez récursivement findRoot sur tout ce qui reste de la racine et tout sur la droite. Ou signifié de toute façon. L'appel de l'enfant de gauche supprime la parenthèse qui l'entoure, mais pas la bonne. Voyant que vous trouvez un nœud feuille en vérifiant la longueur de la chaîne de 3, vous voulez garder les parens. Donc l'appel gauche enfant devrait être: findRoot(tree.substring(0, i).

Answer 3

Désolé: ma basse représentante ne me permet pas de commenter directement, je dois donc poser ma question via cette réponse. Est

(((() B (C)) D (E)) F (G)) J (() K ((L) M (T)))

un exemple d'entrée de chaîne - représentation d'un arbre binaire. Si oui, pouvez-vous fournir en forme de mot juste un peu de l'arbre. Juste quelques feuilles feraient l'affaire.