Trouver un mot dans un arbre de recherche binaire Java?

Question

Le problème que j'ai est que j'ai une recherche binaire trois, et tous les noeuds contiennent des valeurs de chaîne plutôt que des nombres entiers. Il obtient ces chaînes à partir d'un fichier txt et place les lignes de texte individuelles du fichier sous forme de nœuds dans l'arborescence. Il n'y a pas de problème avec ça.

Mon problème est que j'ai besoin d'une méthode qui itère dans mon arbre et trouve un mot spécifique. J'ai déjà des classes séparées, BinarySearchTree et BinaryTreeNode pour servir de base à l'arbre que j'essaie de créer. Les mots qu'il doit trouver sont situés dans un fichier appelé "fichier de test de recherche copy.txt" et il doit écrire les mots qu'il trouve dans un autre fichier appelé "SearchResults.txt"

Je n'ai aucune idée de comment fais-le, alors je cherche des conseils.

C'est la méthode que je besoin d'aide avec:

public boolean SearchWord(String target){ 
    //returns true if the target string exists in the dictionary 
    // otherwise it returns false 
    //ALSO you need to write the results of Search 
    //in an output file called "SearchResults.txt" 

    return false; 
} 

Voici tout mon code, à l'exclusion des deux autres classes mentionnées ci-dessus, si ça aide.

public class Dictionary { 
    public BinaryTreeNode theBinaryTree; 
    /** 
    * I need to read one string by one string 
    * and then insert it into a tree. 
    * I need to read all of the strings in the source file, line by line, 
    * and insert them into my dictionary. 
    * After readinga single string, it needs to put it into a tree. 
    * I first need to create the dictionary tree, 
    * and then implement these methods on the tree. 
    * The Dictionary type is string. 
    * @throws FileNotFoundException 
    */ 

    private BinaryTreeNode dictionaryTree; // this is the tree within your dictionary class 

     public Dictionary(String filePath) throws IOException{ 
      BufferedReader br = new BufferedReader(new FileReader("Dictionary.txt")); 
      this.dictionaryTree = readFile(br); 
      br.close(); 
     } 


     public BinaryTreeNode readFile(BufferedReader reader) throws IOException{ 
      String word = reader.readLine();   
      if(word!=null){ 
       return new BinaryTreeNode(word, readFile(reader), readFile(reader));    
      }else{ 
       return new BinaryTreeNode() ; // empty node or null? 
      }  
     } 


    /** 
    * @return 
    * Once again, I already have this method written and modified 
    * within the BinarySearchTree class. 
    * I'm simply going to call it over here. 
    */ 
    public int CountWords(){ 
     //returns the number of words in the dictionary 
     //This is just counting nodes. 

     BinarySearchTree Aria = new BinarySearchTree(); 
     return Aria.countNodes(dictionaryTree);  
    } 

    public boolean SearchWord(String target){ 
     //returns true if the target string exists in the dictionary 
     // otherwise it returns false 
     //ALSO you need to write the results of Search 
     //in an output file called "SearchResults.txt" 

     return false; 
    } 

    /** 
    * I already modified the print order method 
    * in BinarySearchTree 
    * to work with strings. 
    * So I just called it here on the dictionaryTree. 
    * @PrintOrderedDict() 
    * 
    * However, I also had to modify the method, 
    * so that it wrote whatever values the method recieved 
    * to teh output file. 
    */ 

    public void PrintOrderedDict() throws IOException{ 
     //Print the dictionary words 
     //in order in a new file called "OrderedDictionary.txt". 
     //Just modify print order to work with strings. 
     try { 
     BinarySearchTree jojo = new BinarySearchTree(); 
     FileWriter fstream = new FileWriter("OrderedDictionary.txt"); 

     BufferedWriter out = new BufferedWriter(fstream); 
     out.write(jojo.inorderPrint(dictionaryTree)); 

     out.close();} 
     catch (Exception e) { 
      System.err.println("Error"); 
     } 

    } 

    public boolean DeleteWord(String target){ 
     //delete the target word if it exits in the dictionary and return true 
     //otherwise return false 
     return false; 
    } 
} 

Toute aide ou conseil serait apprécié.

---- ---- EDIT

Ceci est aussi un petit échantillon du fichier "dictionary.txt" (Il est trop longtemps pour mettre la chose entière dans)

ourselves 
out 
over 
own 
same 
shan't 
she 
all 

Cette est le fichier « fichier de test recherche de copy.txt »:

the 
program 
a 
ours 
house 
ME 
ours 
main 
java 
whom 
with 

Answer 1

Vous n'avez pas inclus le code le plus pertinent, qui est BinaryTreeNode, de sorte que les noms de champ utilisés ici sont devinettes, mais cela le fera:

Méthode dans le dictionnaire:

public boolean SearchWord(String target){ 
    boolean found = theBinaryTree.contains(word); 
    // write the values of "target" and "found" to file (code omitted) 
    return found; 
} 

Méthode BinaryTreeNode:

private String word; 
private BinaryTreeNode left; 
private BinaryTreeNode right; 

public boolean contains(String target) { 
    if (target.equals(word)) 
     return true; 
    BinaryTreeNode next = target.compareTo(word) < 0 ? left : right; 
    return next != null && next.contains(target); 
} 

Answer 2

Ceci est évidemment un devoir, je ne vais pas voler la possibilité de le résoudre de vous, mais je vais vous donner des conseils que vous pouvez utiliser pour résoudre facilement votre problème:

1. Vous connaissez déjà l'algorithme, si j'ai bien compris, donc vous maintenant ce que vous avez à faire avec les chiffres. Vous devez faire la même chose avec Strings, juste vous ne savez pas comment comparer les chaînes.

2. Utilisez la méthode compareTo. s1.compareTo(s2) est:

   • positif, si s1> s2

   • négatif, si s1 s2 <

   • 0, si s1.equals (s2)

3. comparable est une interface.Si une classe implémente Comparable, elle aura une méthode compareTo. La chaîne arrive à implémenter Comparable, comme vous pouvez le voir here.

Answer 3

Divisez le problème en plusieurs parties.

1) Faites une recherche sur la façon de lire un fichier. Lisez le fichier et renvoyez les résultats à la sortie standard. C'est assez facile, et environ le tiers du travail que vous devez faire.

2) Écrivez des mots aléatoires dans un fichier. Ouvrez le fichier, écrivez les mots, puis vérifiez votre travail, aussi pas difficile à faire et vous vous rapprochez.

3) Chargez votre arbre de recherche binaire et écrivez du code pour faire une recherche, c'est assez facile. Si votre mot est égal au nœud actuel, renvoyez vrai Sinon, si moins que le nœud actuel, allez à gauche, si plus grand, allez à droite. Si votre pointeur est null, retournez false;

4) Mettez tout ensemble. La conquête de cette partie est beaucoup moins écrasante.