Блог

У меня есть двоичное дерево поиска, и я думаю, что один из моих методов работает неправильно. Программа, которая у меня есть, — это программа, которая слово за словом разделяет строки, прочитанные из файла, и удаляет в нем специальные символы, затем переносит эти слова в структуру данных в алфавитном порядке. Если одно и то же слово было передано ранее во время передачи, это увеличивает частоту этого слова. Проверяя выходные данные моей программы, я увидел что-то вроде этого.

МОЙ ВЫВОД:

 Readed Line: sun-meal            //After some operation it is seperated like "sun" and "metal"
    String inserted.
    String inserted.
Readed Line: sun-oil             //After some operation it is seperated like "sun" and "oil"
    String inserted.
    String inserted.             //Error is here.
 

ИСТИННЫЙ ВЫВОД ДОЛЖЕН БЫТЬ:

 Readed Line: sun-meal                      //After some operation it is seperated like "sun" and "metal"
    String inserted.
    String inserted.
Readed Line: sun-oil                       //After some operation it is seperated like "sun" and "oil"
    String inserted.
    Repeated String. Frequency  1.         //It should be like that.
 

Я поделюсь своим исходным кодом, но я хочу знать, что я делаю не так? Почему «sun» вставляется 2 раза?

Класс TreeDriver:

 import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class TreeDriver
{
    public static void main(String [] args) throws FileNotFoundException {
        Tree stTree = new Tree();
        TreeNode compareNode;

        Scanner scan = new Scanner(new File(args[0]));

        while (scan.hasNextLine()) {
            String data = scan.nextLine();
            System.out.println("Readed Line: " data);
            String[] convertedData = data.replaceAll("[^a-zA-Z ]", " ").toLowerCase().split("\s ");
            int y = 0;
            try {
                while(convertedData[y] != null){
                    String st = convertedData[y];

                    if (st.contains(" ")) {

                    }
                    else{
                        compareNode = Tree.search(stTree.getRoot(), st);

                        if (compareNode != null) {
                            compareNode.upFreq();
                            System.out.println("tRepeated String. Frequency  1.");
                        } else {
                            stTree.insert(st);
                            System.out.println("tString inserted.");
                        }
                        y  ;
                    }
                }
            }
            catch(Exception ignored) {
            }
        }

        scan.close();
    }
}
 

Класс TreeNode

 public class TreeNode
{
    private int freq;   //frequency of the String in the Node
    private String stValue;
    private TreeNode left;
    private TreeNode right;

    public TreeNode(String st)
    {
        stValue = st;
        left = null;
        right = null;
        freq = 1;
    }

    public void add(String st)
    {
        if (left == null)
        {
            left = new TreeNode(st);
        }
        else if (right == null)
        {
            right = new TreeNode(st);
        }
        else
        {
            if(countNodes(left) <= countNodes(right))
            {
                left.add(st);
            }
            else
            {
                right.add(st);
            }
        }
    }

    //Count the nodes in the binary tree to which root points, and
    public static int countNodes( TreeNode root ) {
        if ( root == null )

            // The tree is empty.  It contains no nodes.
            return 0;

        else {

            // Start by counting the root.
            int count = 1;


            // Add the number of nodes in the left subtree.
            count  = countNodes(root.getLeft());
            // Add the number of nodes in the right subtree.
            count  = countNodes(root.getRight());

            return count;  // Return the total.
        }
    }

    public TreeNode getLeft(){
        return left;
    }

    public TreeNode getRight(){
        return right;
    }

    public String getString()
    {
        return stValue;
    }

    public void upFreq()
    {
        freq = freq   1;
    }
    public int getFreq()
    {
        return freq;
    }

}
 

Класс дерева:

 public class Tree
{
    private TreeNode root;

    public Tree()
    {
        root = null;
    }

    public boolean isEmpty()
    {
        return root == null;
    }

    public void insert(String st)
    {
        if (isEmpty())
        {
            root = new TreeNode(st);
        }
        else
        {
            root.add(st);
        }
    }

    public TreeNode getRoot()
    {
        return root;
    }

    public static TreeNode search(TreeNode root, String st)
    {
        if(root == null)
        {
            return null;
        }
        else if(st.equals(root.getString()))
        {
            return root;
        }
        else
        {   if (root.getLeft() != null)
            return search(root.getLeft(), st);
        else
            return search(root.getRight(), st);
        }
    }
    public TreeNode found(TreeNode root)
    {
        return root;
    }
    public static void preorderPrint(TreeNode root)
    {
        if ( root != null )
        {
            System.out.print( root.getString()   " " );  // Print the root item.
            preorderPrint( root.getLeft() );   // Print items in left subtree.
            preorderPrint( root.getRight() );  // Print items in right subtree.
        }
    }
}
 

Не могли бы вы, пожалуйста, помочь мне найти проблему?

Действительно, ваша search функция неверна :

   if (root.getLeft() != null)
     return search(root.getLeft(), st);
  else
     return search(root.getRight(), st);
 

Вы проходите через правый дочерний узел, только если левый имеет значение null, тогда как вы должны пройти через оба.