Création d'une chaîne de données de post-commande d'un arbre donné

Question

Dans le cadre de ma tâche, un arbre d'expression m'a été attribué et je dois le convertir en correctif avec O (n) d'exécution. Par exemple,

Pour convertir cet arbre "((1 V (2 H (3 V 4))) H (5 V 6))". Je ne pensais pas à un moyen de le convertir directement en infixe, alors j'ai pensé à le convertir en post-fix et en in-fix. (S'il y a une meilleure façon, dites-le moi).

Maintenant, mon problème est de convertir l'arbre en commande. J'ai essayé les suivantes:

private String treeToPost(Node node, String post) { 
    if (node != null) { 
     treeToPost(node.left, post); 
     treeToPost(node.right, post); 
     post = post + node.data.getName(); 
    } 
    return post; 
} 

Maintenant, j'ai deux problèmes avec cette méthode, la première est que cela ne fonctionne pas, car il enregistre uniquement le dernier nœud, il a voyagé, le second est que je suis pas sûr qu'il fonctionnera à O (n) car il devra créer une nouvelle chaîne à chaque fois. J'ai trouvé une solution à ce problème, mais elle utilisait StringBuilder que je ne suis pas autorisé à utiliser. J'ai pensé à faire un tableau de caractères pour enregistrer les données, mais parce que je ne connais pas la taille de l'arbre, je ne peux pas connaître la taille du tableau nécessaire. Merci pour votre temps :)

Answer 1

Aller directement à l'infixe est probablement plus facile, il suffit d'ajouter toujours des parenthèses.

Deuxièmement, faire quelque chose comme ceci sauvera tous les nœuds:

private String treeToPost(Node node) { 
    String returnString = ""; 
    if (node != null) { 
     returnString += treeToPost(node.left); 
     returnString += treeToPost(node.right); 
     returnString += node.data.getName(); 
    } 
    return returnString; 
} 

Pour infix, cela devrait fonctionner

private String treeToPost(Node node) { 
    String returnString = ""; 
    if (node != null) { 
     returnString += "(" + treeToPost(node.left); 
     returnString += node.data.getName(); 
     returnString += treeToPost(node.right) + ")"; 
    } 
    return returnString; 
} 

Ces deux objets font nouvelle chaîne à chaque fois. Donc, je pense que c'est techniquement O (n^2), parce que la chaîne se développe à chaque fois, mais aucun de mes professeurs ne déduirait de points pour cela. Cependant, si vous voulez éviter ce comportement, vous ne pouvez pas utiliser StringBuilder. Vous pouvez utiliser un CharArrayWriter. C'est un tampon qui se développe dynamiquement. Vous pouvez ensuite faire deux méthodes. Celui qui s'ajoute à la mémoire tampon et ne renvoie rien. Et celui qui renvoie une chaîne. Vous appelez alors le buffer depuis l'intérieur de String.