Блог

Это функция, которая добавляет узел в мое двоичное дерево поиска.Как я могу переформатировать это, чтобы вернуть значение true, если это дерево еще не содержало указанный элемент.

 private Node insertNode(Node root, Student student) {
    if (root == null) {
        root = new Node(student);
    }
    int comp;
    if (Comparator != null) {
        comp = Comparator.compare(student, root.value);
    } else {
        comp = student.compareTo(root.value);
    }

    if (comp < 0) {
        root.left = insertNode(root.left, student);
    } else if (comp > 0) {
        root.right = insertNode(root.right, student);
    }
    return root;
}
 

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

Возможно, будет намного проще сначала выполнить поиск узла, если он существует, вернуть значение false, а если нет, запустить этот код, а затем вернуть значение true. Что-то вроде:

 // Keep `insertNode`, as is, unchanged, except name it `createNode`.
// Make sure to include in its docs that it doesn't create
// if the `student` record already exists in the tree.

private boolean insertNode(Student student) {
    if (search(this.root, student)) return false;
    createNode(this.root, student);
    return true;
}
 

Как правило, при написании рекурсивных алгоритмов почти всегда требуется 2 метода. Фактический рекурсивный метод, который является private и имеет бессмысленные аргументы, по крайней мере, если смотреть на него с точки зрения API, и public один, который знает, какие начальные значения должны быть переданы для этих аргументов.

Например, в вашем коде вам необходимо указать Node root insertNode «кому». С точки зрения insertNode рекурсивного процесса это имеет решающее значение. Однако, с внешней точки зрения, это не имеет смысла. Если я пишу код для интерфейса графического интерфейса, который показывает всех студентов, зачем мне нужно указывать узел? Ваш объект, безусловно, имеет тип StudentTree или что-то еще, он, без сомнения, знает корневой узел. (Это должно быть, например, полем, если это не так прямо сейчас).

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

Чтобы быть ясным, это невозможно без использования 2 методов. В лучшем случае вы можете вернуть, вместо того Node , некоторые комбинированный объект, который возвращает узел, а также логическое и тогда все абоненты могут распаковать его, но это требует кучу усилий (создать класс для представления этого, и каждый раз, когда вы звоните insertNode , включая в insertNode себя, извлеките узел из объекта).