BST 字符串遍历
BST String Traversal
我正在尝试为我的 BST 实现中序、前序和后序遍历算法。到目前为止,inorder 算法似乎正在运行,但它只是 returning 单词的第一个字符。我意识到我正在 returning char c
,但我对如何使它 return 整个词感到困惑。任何帮助将不胜感激!
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();
}
}
您的 addValue 方法看起来不正确。它只修改根,然后字符将相等,所以它 returns。特别是 d 永远不会被修改。
在更基础的层面上,BST 适用于在树中查找字符,而不适用于查找字符串。如果你想找一个词,你可以使用Trie代替(它不是二叉树)。
我没有看你的顺序代码,但你说它有效,所以我相信你。
不过我确实看过你的 addValue 代码,你只在这里保存了第一个字符。难怪你不能找回整个单词,你就是不保存它:P
相反,您应该更改节点 class 以接受字符串而不是字符。您也不需要在 addValue 方法中使用 d 参数。
Java String class 提供了.compareTo() 方法,以便按字典顺序比较字符串。您可以将它与 string.compareTo(otherString)
一起使用
此方法将return一个<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")
我正在尝试为我的 BST 实现中序、前序和后序遍历算法。到目前为止,inorder 算法似乎正在运行,但它只是 returning 单词的第一个字符。我意识到我正在 returning char c
,但我对如何使它 return 整个词感到困惑。任何帮助将不胜感激!
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();
}
}
您的 addValue 方法看起来不正确。它只修改根,然后字符将相等,所以它 returns。特别是 d 永远不会被修改。
在更基础的层面上,BST 适用于在树中查找字符,而不适用于查找字符串。如果你想找一个词,你可以使用Trie代替(它不是二叉树)。
我没有看你的顺序代码,但你说它有效,所以我相信你。
不过我确实看过你的 addValue 代码,你只在这里保存了第一个字符。难怪你不能找回整个单词,你就是不保存它:P
相反,您应该更改节点 class 以接受字符串而不是字符。您也不需要在 addValue 方法中使用 d 参数。
Java String class 提供了.compareTo() 方法,以便按字典顺序比较字符串。您可以将它与 string.compareTo(otherString)
一起使用此方法将return一个<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")