Почему вставка в BST вставляет корень дважды?

Question

Я создал двоичный класс дерева поиска. Я создал метод ввода, метод высоты и метод печати. Когда я вставляю, все выглядит отлично. Если корень равен нулю, я создаю новый корень и устанавливаю элемент. Но когда я вызываю метод height, он печатает 2 вместо 1. Когда я вызываю свой метод печати, он печатает все элементы, включая root, дважды. Например, я вставил следующие элементы в следующем порядке: 9, 5, 4, 55, 555

Когда слово мой метод PREorderPRINT, он печатает: 9, 5, 4, 9, 55, 555

Значения, напечатанные правильно, за исключением дубликата 9 в середине, который я никогда не вставил. Мой метод вставки НЕ использует рекурсию. Но мои методы высоты и печати используют рекурсию.

Рекурсивный preOrderPrint проверяет, является ли root! = Null, затем он печатает элемент, получает левый и получает право. Когда я вызываю preorder в моем общедоступном методе предварительного заказа, я сначала проверяю, что дерево пустое, если нет, то я печатаю его, передавая его в корневой каталог preOrderPRint (root)

Метод рекурсивной высоты проверяет, является ли корень нулевым и возвращает ноль , Если нет, он получает высоту левого и правого поддеревьев корня, сравнивает их и возвращает либо влево + 1, либо вправо + 1. Когда я вызываю свой общедоступный метод высоты, я проверяю, является ли root нулевым и возвращает ноль, иначе вызовите рекурсивную высоту, проходящую в корне.

Когда я вставляю один элемент, 9, в дерево и вызываю метод высоты, он печатает высоту 2. Но мой метод размера печатает правильный размер, 1. Должно быть что-то не так с моим рекурсивный preorderPrint и методы высоты. Я не могу понять, что мне не хватает. Есть ли специальный случай, который я забыл добавить?

EDIT: Я опубликовал код и удалил его. Исправлена ​​проблема. Все, что мне нужно было сделать, это изменить else на else-if и добавить условие для сравнения root с вставленным элементом. Глупая ошибка.

Answer 1

Моя проблема была в моем методе ввода. Мой первый случай проверял, был ли корневой узел нулевым. Если он равен нулю, он создает узел, равный корню, и устанавливает элемент.

Мой второй случай сравнивает мой корень и проверяет, не было ли вставляемого элемента меньше, чем root, если это так, он «получает» узел слева. После этого, если вставленный элемент больше корня, он «получает» узел справа.

Далее у меня был еще один блок if-else, который устанавливает элемент влево, если элемент меньше, чем root. После этого у меня был только оператор else, который привязывал элемент к узлу вправо, независимо от того, был ли он уже вставлен в случае root == null.

Чтобы исправить свою проблему, мне пришлось сменить это выражение else на инструкцию if-else и добавить условие, которое проверяет, является ли элемент вставленным больше, чем root. Это предотвратило введение корня дважды.