BST字符串遍歷

Question

我試圖爲我的BST實現一個inorder，preorder和postorder遍歷算法。看起來inorder算法到目前爲止還在工作，但它只返回單詞的第一個字符。我意識到我正在返回char c，但我很困惑我會如何讓它返回整個單詞。任何幫助將不勝感激！

package main; 

import java.io.*; 
import java.util.*; 

// Node class 
class Node 
{ 
    char c; 
    boolean end; 
    Node left, right; 

    public Node(char c) 
    { 
     this.c = c; 
     this.end = false; 
     this.left = null; 
     this.right = null; 

    }   
} 


class BinarySearchTree 
{ 
    private Node root; 

    public BinarySearchTree() 
    { 
     root = null; 
    } 

    public void addValue(String s) 
    { 
      root = addValue(root, s, 0); 
    } 

    private Node addValue(Node x, String s, int d) 
    { 
      char c = s.charAt(d); 
      if (x == null) 
     x = new Node(c); 
      if (c < x.c) 
     x.left = addValue(x.left, s, d); 
      else if (c > x.c) 
     x.right = addValue(x.right, s, d); 
      else x.end = true; 
       return x; 
    } 

    public boolean search(String s) 
    { 
      return search(root, s, 0); 
    } 

    private boolean search(Node x, String s, int d) 
    { 
      if (x == null) 
     return false; 

      char c = s.charAt(d); 

      if (c < x.c) 
       return search(x.left, s, d); 
      else if (c > x.c) 
       return search(x.right, s, d); 
      else 
       return x.end; 

    } 

     public void inorder(){ 
      inorder(root); 
     } 

     private void inorder(Node r){ 
      if (r != null){ 
       inorder(r.left); 
       System.out.print(r.c); 
       inorder(r.right); 
      } 
     } 
} 

public class Project2 
{ 
    public static void main(String[] args) throws Exception 
    { 
     BinarySearchTree tree = new BinarySearchTree(); // Make new BST object 

     // Variable for scanned word 
     String token = ""; 

     // Use scanner for input file 
     Scanner scan = new Scanner(new File("10words.txt")).useDelimiter("\\s+"); 

     //Check for next line in text file 
     while (scan.hasNext()) 
     { 
      token = scan.next(); 
      tree.addValue(token); 
     } 
     scan.close(); 

     tree.inorder(); 

     Scanner inputWord = new Scanner(System.in); 
     System.out.print("\nEnter a word to search: "); 
    String word = inputWord.next().toLowerCase(); 

    if(tree.search(word) == false){ 
      System.out.println("Word NOT Found!"); 
     } else{ 
      System.out.println("Word Found!"); 
     } 
     inputWord.close(); 
    } 
} 

Answer 1

我沒有看你的inorder代碼，但你說它的工作原理，所以我會相信你。

但是我確實看了一下你的addValue代碼，你只能在這裏保存第一個字符。難怪你不能把整個單詞回覆，你只是不保存它：P

相反，你應該改變你的節點類接受一個字符串，而不是一個字符。您不需要addValue方法中的d參數。

Java String類提供了.compareTo（）方法，以按字典順序比較字符串。你可以用string.compareTo（otherString）使用它

此方法將一個值< 0，等於返回0或> 0

< 0 means string is lexicographically smaller than otherString (for example: "Apple" would be smaller than "Banana") 

= 0 means it's the exact same word 

> 0 means string is bigger than otherString (for example: "Banana" would be bigger than "Apple") 

Answer 2

您的addValue方法看起來不正確。它只修改根，然後字符相等，所以它返回。特別是d從不修改。

在更基本的層次上，BST適合在樹中查找字符，而不是查找字符串。如果你想查找一個單詞，你可以使用一個Trie（這不是一個二叉樹）。