Вставка в двоичное дерево не работает с использованием java
В настоящее время я изучаю деревья с помощью java и у меня здесь происходят некоторые ошибки при вставке элементов в двоичное дерево Я не понимаю, почему это не работает
это код: узел дерева:
public class TNode {
int data;
TNode left;
TNode right;
public TNode(int data) {
this.data = data;
left = null;
right = null;
}
}
класс дерева:
public class Tree {
TNode root;
public Tree(){
root = null;
}
public TNode insertNode(TNode item, int d) {
if (item == null) {
return new TNode(d);
}
if (d < item.data) {
item.left = insertNode(item, d);
}
if (d > item.data) {
item.right = insertNode(item, d);
} else {
return item;
}
return item;
}
public void add(int d) {
insertNode(root, d);
}
}
Всякий раз, когда я добавляю элемент, корень остается нулевым без правых или левых элементов Если кто-то может помочь, я буду очень благодарен
Ответы 2
root всегда равен нулю, потому что вы никогда не присваиваете ему значение.
вы можете добавить в начало проверки метода и назначить его
public TNode insertNode(TNode item, int d){
if (item == null){
TNode node = new TNode(d);
if (root == null) {
root = node;
}
return node
}
... rest of method isn't changed...
Кроме того, при рекурсии вы должны выполнять вызов с правильным дочерним узлом вместо того, чтобы всегда вызывать с помощью item, поэтому, например, первым случаем будет:
item.left = insertNode(item.left, d);
Во втором случае вы могли бы просто использовать item.right.
"корень = ню;" вероятно должно быть "root = node;" xD хороший
Прекрасный код, но рекурсия не продвигается дальше
item.left = insertNode(item.left, d);
item.right = insertNode(item.right, d);
И исходный рут не обновляется:
root = insertNode(root, d);
Остальная часть или окончательный возврат излишни.
Кое-что о стиле кода
insertNode имеет узел в качестве входа и возвращает обновленное значение узла, поэтому вызов «шаблон» должен выглядеть так:
X = insertNode(X, d); // X is some expression
Это связано с тем, что java никогда не может присвоить переданному выражению аргумента: у него нет передачи по ссылке, а есть передача по значению; f(x) никогда не назначается x.
..поскольку вы никогда не назначаете root (на что-то другое, кроме
null), пожалуйста, сделайте (вероятно, лучший дизайн) в методеadd:if (root == null) { root = insertNode(root, d); } else { insertNode(root, d); }