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")