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

Question

Я пытаюсь решить эту проблему: «Дано бинарное дерево, проверьте его посещение перед заказом и создайте бинарное дерево поиска с таким же посещением перед заказом. Покажите, возможно ли это всегда, если нет, приведите пример, когда это невозможно." Любая помощь? Мне нужно написать псевдокод и указать сложность времени, но у меня много сомнений по поводу построения дерева поиска в двоичном коде с одинаковым посещением предварительного заказа для каждого возможного двоичного дерева.

Answer 1

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

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

Я надеюсь помочь вам. И добро пожаловать в стек переполнения!