Мне необходимо разработать свой собственный класс дерева двоичного поиска для назначения. Предполагается отсортировать класс данных (User), который содержит две строки: имя пользователя и пароль, а затем разрешить поиск в текстовом файле по переменной username. Я успешно протестировал файлы для назначения с помощью TreeSet и обнаружил, что при поиске будет получено около 300 положительных совпадений, если будет использован весь файл поиска. Исходя из моей предыдущей работы, я думал, что мой класс двоичного дерева будет работать, но независимо от того, что он никогда не найдет совпадений с помощью своей функции поиска, хотя я знаю, что это неправильно.
Некоторая информация о коде, который здесь не показан-
- Узел (называемый BinTree) содержит один пользовательский класс, а также левый и правый узел, как обычно.
- getUserName - это простой метод доступа, который напрямую извлекает имя пользователя из базового пользователя узла.
- метод grow изначально вызывается на созданном вручную корневом узле (b = new BinTree ([здесь вводятся первые данные из программы чтения файлов])
- Поскольку эта программа обрабатывает имена пользователей, важна чувствительность к регистру.
- Основываясь на том, как написан класс драйвера, метод поиска должен возвращать только true, если он находит пользователя с правильным именем пользователя или false в противном случае.
Вот (новый) метод grow ();
public BinTree grow(BinTree root, BinTree newNode)
{
if (root == null)
return newNode;
if (newNode.getUserName().compareTo(root.getUserName()) > 0)
{
if (root.right == null)
root.right = newNode;
else
root.right.grow(root.right, newNode);
}
else
{
if (root.left == null)
root.left = newNode;
else
root.left.grow(root.left, newNode);
}
return root;
}
А вот (новый) метод search ();
public boolean search(BinTree r, String s) //search for a username, case sensitive
{
if (r.getUserName().compareTo(s) == 0)
return true;
else if (r.left != null && r.getUserName().compareTo(s) < 0)
return r.left.search(r.left, s);
else if (r.right != null)
return r.right.search(r.right, s);
return false;
}
Как я уже говорил, раньше я делал более простое двоичное дерево (в котором содержались только одиночные значения типа int, а не пользовательские классы данных), и я пробовал различные способы написания этих двух методов, но я чувствую, что есть одна важная часть загадка, которую я просто не понимаю. Заранее спасибо за любую помощь.
ОБНОВЛЕНИЕ: Спасибо @Diasiare и @ c0der за то, что они указали на очевидную проблему, заключающуюся в том, что в моем коде были опечатки, касающиеся возвратов и влево / вправо. Я взял это и изменил приведенный выше код, чтобы отразить его. После запуска программа все еще не работала. Затем я написал этот метод show () для печати всех имен пользователей, хранящихся в дереве пользователей.
public void show(BinTree r)
{
if (r != null)
{
show(r.left);
System.out.println(r.getUserName());
show(r.right);
}
} // show
Когда я вызывал его после обновления и компиляции всего остального, он действительно показывал, что список был заполнен именами пользователей в алфавитном порядке. Вот небольшой фрагмент вывода (там много строк)
ted@wisler.com
teddy@borglum.com
teddy@winkey.com
-->teodoro@harkin.com<--
teodoro@stranford.com
teodoro@talaska.com
teodoro@willette.com
tera@norise.com
tera@strevels.com
terence@lathrum.com
terence@morocco.com
terence@neidig.com
terence@rabago.com
teresa@chauvin.com
teresa@dockus.com
Тот, который выделен стрелками, - это тот, который я искал вручную в файле .txt поиска и нашел. В общем, с помощью этой новой информации я определил, что A) grow () работает правильно, так как оно заполняет дерево из файла в алфавитном порядке, а B) search () должен возвращать хотя бы одно совпадение. Поэтому я работаю в предположении, что проблема заключается в поиске () до сих пор.
UPDATE2: Вот контекст, в котором я вызываю search () для тех, кто заинтересован.
try
{
BufferedReader fromPasswords = new BufferedReader(new FileReader("passwordInput.txt"));
while ((line = fromPasswords.readLine()) != null)
{
System.out.println(line);
if(b.search(b, line))
{
matches++;
}
}
fromPasswords.close();
}
catch (Exception e)
{
System.out.println("Error while searching tree: " + e);
System.exit(0);
}