java Binary Search Tree inorder récursivement, chaîne de retour

Question

J'ai une méthode toString, qui devrait renvoyer une chaîne représentant l'ensemble de l'arbre de recherche binaire dans l'ordre. Je suis arrivé jusqu'ici, mais il s'agit simplement d'imprimer les nombres dans l'ordre, et la méthode toString renvoie simplement la valeur de rootNode bien sûr. Je ne sais pas comment je devrais résoudre ça.

@Override 
public String toString() { 
    if (rootNode == null){ 
     return ""; 
    } 
    else { 
     return inorder(rootNode.data); 
    } 
} 

/** 
* @param root 
*/ 
public String inorder(Node<T> root){ 
    if (root != null){ 
     inorder(root.left); 
     System.out.println(root.value + " "); 
     inorder(root.right); 
    } 
} 

J'ai été coincé avec ce problème pendant des heures.

Answer 1

Peut-être que vous pouvez essayer cette

@Override 
public String toString() 
{ 
    java.lang.StringBuilder toReturn = new java.lang.StringBuilder(); 
    if (rootNode == null){ 
     return ""; 
    } 
    else{ 
     inorder(rootNode.data , toReturn); 
    } 
    return toReturn.toString(); 
} 

/** 
* @param root 
*/ 
public void inorder(Node<T> root , java.lang.StringBuilder treeLikeStringBuilder){ 
    if (root != null){ 
     inorder(root.left); 
     System.out.println(root.value + " "); 
     treeLikeStringBuilder.append(root.value.toString() + " "); 
     inorder(root.right); 
    } 
} 

afinde signature (nœud, StringBuilder) serait plutôt aider à la construction d'une chaîne comme la structure pour le parcours infixe, de sorte que toString() pourrait retourner cette chaîne afinde travsersal, aussi StringBuilder est utilisé pour que les modifications apportées au MUTABLE StringBuilder passé en argument (StringBuilder toReturn) à la méthode inorder (Node, StringBuilder) reflètent les changements dans la méthode toString(), espérons que ça aide ??

Answer 2

L'algorithme ci-dessous simplifie votre tâche, il ne fait que visiter chaque nœud par rapport à l'algorithme inOrder et ajouter ces données de nœud à la chaîne.

public void inOrder(Node<T> root, string NodeData){ // Algorithm for inOrder - "left child node, root, right child node" 
    if (root != null){ 
     inOrder(root.left, NodeData); // traverse left sub tree 
     NodeData += root.Data.ToString() + " | "; // append to NodeData 
     inOrder(root.right, NodeData); // traverse right sub tree 
    } 
} 

invoquez la méthode comme ceci:

string TreeNodeData = ""; 
Tree.inOrder(ENTER ROOT OF TREE HERE, TreeNodeData); 

Enfin, vous pouvez vérifier le résultat avec:

System.out.println(TreeNodeData);