параметры Java всегда передаются по значению. Это немного запутывает, когда параметр является ссылкой переменной. Вещь, чтобы отметить:
- Любое назначение параметра является не будет рассматриваться звонящие, только внутри тела метода. Это верно, является ли оно примитивным или ссылкой (объекту).
- Если переменная является ссылкой на изменяемый объект (то есть объект, поля которого вы можете получить и изменить либо напрямую, либо с помощью установщика), то присвоение в поле будет видно вызывающий абонент.
Итак, что мы можем сделать с вышеуказанной программой? Предполагая, что у вас есть доступ к полям TreeNode
объекта left
и right
, вы должны изменить метод так, чтобы параметр current
всегда представлял родительский узел любого добавленного узла. Таким образом, он никогда не будет null
, он всегда будет реальным объектом. И в реальном объекте мы можем менять поля!
Итак, мы начинаем с верхним методом:
public boolean insert(E element) {
if (root == null) {
root = new TreeNode(element);
return true;
} else {
return insert(element, root);
}
}
Если мы не имеем ничего в нашем дереве еще - корень нуль - то мы не можем назвать наш рекурсивный метод вообще. В его нынешнем виде отсутствует «родительский» узел. Но в этой ситуации правильное дело - установить root
данному элементу. Таким образом, мы создаем новый узел с заданным элементом и назначаем его root. В следующий раз root
больше не будет null
!
Если это не было null, мы можем передать его как «родительский» для вставки. Либо его содержимое равно новому элементу (в этом случае рекурсивный метод возвращает false), либо элемент должен быть вставлен где-то под номером. Так что это хороший «родитель».
Теперь сам рекурсивный метод:
private boolean insert(E element, OrderedSet<E>.TreeNode current) {
if (current.data.compareTo(element) == 0) {
// The element is already in the tree, so we do not insert
// anything, and we return false.
return false;
} else {
if (current.data.compareTo(element) > 0) {
// Smaller elements need to be inserted at the left
if (current.left == null) {
current.left = new TreeNode(element);
return true;
} else {
return insert(element, current.left);
}
} else {
// Bigger elements need to be inserted at the right
if (current.right == null) {
current.right = new TreeNode(element);
return true;
} else {
return insert(element, current.right);
}
}
}
}
Теперь код для каждого случая (больше и меньше) не стало немного сложнее:
if (current.left == null) {
current.left = new TreeNode(element);
return true;
} else {
return insert(element, current.left);
}
Мы больше не разрешается пропускать null
на следующий шаг рекурсии, поскольку null
не является надлежащим «родителем», и мы не сможем назначить его поля. Поэтому, если левая ветвь равна нулю, мы не можем ее возвращать.Но в этом случае подходящее действие состоит в том, чтобы фактически установить левый узел в наш новый элемент, потому что он равен меньше нашего текущего узла. Итак, мы создаем новый узел, задаем current.left
для ссылки на него, и теперь мы добавили что-то в дерево, мы можем вернуть true
.
Но если узел left
не был нулевым, то либо он будет равен данному элементу, либо данный элемент должен быть установлен где-то под ним. Таким образом, левый узел является хорошим «родительским» узлом, и мы можем назвать его рекурсией.
Та же логика также применяется к добавлению элементов справа.
Поскольку мы присваиваем непосредственно current.left
и current.right
, которые поля нашего дали current
, результат будет видно вызывающим.
'current' передается по значению, а не по ссылке. Вы не можете присвоить ему значение и ожидать вернуть его в вызывающий. – RealSkeptic
Любая идея о том, как ее исправить? – moo