Добавление элементов в бинарное дерево поиска без порядка

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

Все те, что были до этого вопроса, указывали что-то вроде «Предположим, что дерево использует алфавитный порядок для сравнения слов», но на этот раз об этом не говорится.

Существует ли порядок сортировки по умолчанию для сортировки строк или целых чисел при добавлении их в дерево?

Для контекста он просит меня:
Нарисовать ниже изображение бинарного дерева поиска, которое получится, если вставить следующие слова в пустое бинарное дерево поиска в следующем порядке: Леголас, Фродо, Сэм, Мерри, Пиппин, Арагорн. , Гимли, Боромир.


sorting tree binary-tree binary-search-tree preorder
person user6064023    schedule 15.03.2016    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Поскольку в вопросе конкретно говорится «Двоичные деревья поиска», вы можете сравнить узел, используя лексикографический порядок (алфавитный порядок) при вставке узлов в дерево.

для вашего примера дерево будет выглядеть так:

                                     Legolas


            Frodo                                                 Sam


  Aaragon              Gimili                             Merry


        Boromir                                               Pippin
person uSeemSurprised    schedule 15.03.2016
comment
Поэтому, если он не указан, для строк вы добавляете первый элемент в список в качестве общего корня, а затем используете лексиграфический (алфавитный) порядок для упорядочения остальных в зависимости от того, идет ли первая буква до или после той, которую вы только что вставил. Отлично, спасибо! еще один вопрос, если это с целыми числами, я предполагаю, что вы просто упорядочиваете их от меньшего к большему, если не указано иное? - person user6064023; 15.03.2016
comment
Да, для целых чисел вы должны упорядочить, на какое целое число больше, если в вопросе говорилось только "Binary tree", тогда вы можете вставлять узлы в любое место дерева, но для "Binary search tree" у него должно быть какое-то свойство упорядочения, чтобы он мог искать элемент - person uSeemSurprised; 15.03.2016
comment
Спасибо за ваши ответы! они очень полезны - person user6064023; 15.03.2016
comment
Без проблем, рад помочь! - person uSeemSurprised; 15.03.2016