Comment imprimer efficacement l'espace blanc nécessaire à la tâche dans mon prettyPrint() méthode BST

Question

Pour la jolie méthode d'impression de ma classe BST, on nous a dit par notre professeur pour l'arbre:

bst.put(7, 7); //  _7_ 
    bst.put(8, 8); // / \ 
    bst.put(3, 3); // _3_  8 
    bst.put(1, 1); /// \ 
    bst.put(2, 2); // 1  6 
    bst.put(6, 6); // \ /
    bst.put(4, 4); // 2 4 
    bst.put(5, 5); //  \ 
        //   5 

Le code doit imprimer l'arbre comme si:

    "-7\n" + 
        " |-3\n" + 
        " | |-1\n" + 
        " | | |-null\n" + 
        " | | -2\n" + 
        " | | |-null\n" + 
        " | | -null\n" + 
        " | -6\n" + 
        " | |-4\n" + 
        " | | |-null\n" + 
        " | | -5\n" + 
        " | | |-null\n" + 
        " | | -null\n" + 
        " | -null\n" + 
        " -8\n" + 
        " |-null\n" + 
        " -null\n"; 

J'ai mon code pour imprimer l'arbre presque parfait à ce que le conférencier comme spécifié en utilisant récursion, bien que je ne peux pas trouver un moyen d'imprimer les espaces blancs comme il précisé. Je comprends que c'est un problème avec seulement l'impression des caractères sur n'importe quel sous arbre, mais je ne suis pas sûr d'un moyen d'imprimer correctement les espaces.

Voici comment mes impressions de code:

-7 
|-3 
| |-1 
| | |-null 
| |-2 
| | |-null 
| |-null 
|-6 
| |-4 
| | |-null 
| |-5 
| | |-null 
| |-null 
|-null 
-8 
|-null 
-null 

Comme vous pouvez le voir pour les bons nœuds d'arbres sous il n'y a pas l'espacement prefixxed, et toute tentative de préfixe un espace pour les bons nœuds d'arbres sous, a seulement modifié le format de l'arbre.

Voici mon code, toute aide serait profondément heureux

public String prettyPrintKeys() { 
    String output = ""; 
    int indent = 0; 
    output = prettyPrint(root, indent); 
    System.out.print(output); 
    return output; 
} 
private String prettyPrint(Node x, int indent){ 
    String output = ""; 
    for(int i=0; i<indent; i++){ 
     output = output + " |"; 
    } 
    if(x == null){ 
     return output = output + "-null\n"; 
    } 
    indent++; 
    output = output + "-" + x.key + "\n" + prettyPrint(x.left, indent); 
    indent--; 
    output = output + prettyPrint(x.right, indent); 
    return output; 
} 

Answer 1

Normalement, je ne fais pas les devoirs, mais cela est un peu difficile, et vous avez fait comme 90% des travaux.

Vous avez une erreur conceptuelle. Principalement je pense que vous pouvez "retourner" cette valeur d'une manière ou d'une autre. Je ne pense pas que cela fonctionne. Vous devez transmettre votre valeur de retour pour pouvoir l'ajouter, tout comme vous devez transmettre la variable indent.

L'autre problème était que vous ne regardiez pas attentivement la sortie désirée. Il y a deux styles de retrait. Un pour imprimer un noeud droit, où "|" est imprimé, et un pour un noeud gauche, où "" est imprimé. Vous devez les suivre séparément.

Voici ma tentative, j'espère que j'ai bien compris. ;-)

package quicktest; 

/** 
* 
* @author Brenden Towey 
*/ 
public class TreePrint 
{ 

    public static void main(String[] args) 
    { 
     Node root = new Node(); 
     fill(root); 
     prettyPrintKeys(root); 
    } 

    public static String prettyPrintKeys(Node root) 
    { 
//  String output = ""; 
//  int indent = 0; 
     StringBuilder indent = new StringBuilder(); 
     StringBuilder output = new StringBuilder(); 

     prettyPrint(root, indent, output); 
     System.out.print(output); 
     return output.toString(); 
    } 

    private static void prettyPrint(quicktest.TreePrint.Node x, 
      StringBuilder indent, StringBuilder output) 
    { 
//  for(int i = 0; i < indent; i++) 
//   output = output + " |"; 
     output.append(indent); 
//  if(x == null) 
//   return output = output + "-null\n"; 
     output.append("-"); 
     output.append(x); 
     output.append("\n"); 
     if(x == null) return; 
//  indent++; 
//  output = output + "-" + x.key + "\n" + prettyPrint(x.left, indent); 
     indent.append(" |"); 
     prettyPrint(x.left, indent, output); 
//  indent--; 
//  output = output + prettyPrint(x.right, indent); 
     indent.delete(indent.length()-2, indent.length()); 
     indent.append(" "); // <<-- second indent style 
     prettyPrint(x.right, indent, output); 

     // needed a second indent-- here 
     indent.delete(indent.length()-2, indent.length()); 
    } 

    private static class Node 
    { 

     Comparable key; 
     Node left; 
     Node right; 

     @Override 
     public String toString() 
     { 
     return "Node{" + "key=" + key + '}'; 
     } 


    } 

    private static void fill(Node root) 
    { 
     insert(root, 7); 
     insert(root, 8); 
     insert(root, 3); 
     insert(root, 1); 
     insert(root, 2); 
     insert(root, 6); 
     insert(root, 4); 
     insert(root, 5); 
    } 

    private static void insert(quicktest.TreePrint.Node node, Comparable newKey) 
    { 
     if(node.key == null) { 
     node.key = newKey; 
     return; 
     } 
     if(node.key.compareTo(newKey) > 0) { 
     if(node.left == null) node.left = new Node(); 
     insert(node.left, newKey); 
     return; 
     } 
     if(node.right == null) node.right = new Node(); 
     insert(node.right, newKey); 
    } 
} 

sortie de ce programme:

run: 
-Node{key=7} 
|-Node{key=3} 
| |-Node{key=1} 
| | |-null 
| | -Node{key=2} 
| | |-null 
| | -null 
| -Node{key=6} 
| |-Node{key=4} 
| | |-null 
| | -Node{key=5} 
| | |-null 
| | -null 
| -null 
    -Node{key=8} 
    |-null 
    -null 
BUILD SUCCESSFUL (total time: 0 seconds)