Реализация двоичного дерева в java

Question

Я новичок в datastructure.Я пытаюсь реализовать двоичное дерево, используя Связанный список.

Мне нужно несколько пояснений при его реализации.

i) Для ввода нового значения в дереве, следует ли нам возвращать назад и обход дерева при его реализации.

ii) Пожалуйста, предложите мне случаи для поиска и удаления значения.

iii) Пожалуйста, предложите мне правильный материал для реализации всех типов деревьев.

Answer 1

Ваш связанный список должен показать что-то вроде этого: a->b->c->d->e->f-> ... где ваше дерево будет выглядеть как картинка в конце. где a - корень с левым дочерним элементом b и правым дочерним c. b оставил дочерний элемент d и правый дочерний элемент e, а c имеет только левый дочерний элемент f.

i) вы можете поместить новое значение в конец Связанного списка. Нет необходимости путешествовать по дереву

ii) Я предполагаю, что ваше дерево не будет сортированным двоичным деревом. Итак, для поиска значения k вам нужно пройти через весь Связанный список. это займет O (n) в качестве вашего времени.

Для удаления переменной вы можете удалить узел в Связанном списке, и все будет сдвинуто. так, например, на картинке выше, если вы удаляете d, вы можете увидеть результат на изображении, где f будет заменять d.

iii) Не могли бы вы указать, что вы подразумеваете под всеми типами деревьев?

Надеюсь, это поможет.

Deleting a node