Есть ли универсальные алгоритмы, подходы для создания деревьев если даны "traversen"?
Здравств. Подскажите пожалуйста есть ли какой то универсальный подход, алгоритм, для создания деревьев когда задана 1 или 2 или 3 traverse. К примеру, вот(в данном случае это бинарное дерево):
1. inorder: c m v h n q i q
2. preorder: q n v m c h q i
3. postorder: c m h v n i q q
Пришлось здорово голову поломать, чтоб с первого раза такое решить. Нужно научится решать за 5-10 минут.
Спасибо.
1. inorder: c m v h n q i q
2. preorder: q n v m c h q i
3. postorder: c m h v n i q q
Пришлось здорово голову поломать, чтоб с первого раза такое решить. Нужно научится решать за 5-10 минут.
Спасибо.
Цитата: webdev
Пришлось здорово голову поломать, чтоб с первого раза такое решить. Нужно научится решать за 5-10 минут.
Если вы хотите получить внятный ответ, то, пожалуйста, потрудитесь объяснить аудитории термин "traversen", а также смысл вот этого текста:
Цитата: webdev
1. inorder: c m v h n q i q
2. preorder: q n v m c h q i
3. postorder: c m h v n i q q
Хочу внятный ответ. traverse - это способы обхода дерева.
Вики
Вики
Цитата:
Обход дерева (TRAVERSE)
Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов.
Первая операция — INFIX_TRAVERSE — позволяет обойти все узлы дерева в порядке возрастания ключей и применить к каждому узлу заданную пользователем функцию обратного вызова f. Эта функция обычно работает только c парой (K,V), хранящейся в узле. Операция INFIX_TRAVERSE реализуется рекурсивным образом: сначала она запускает себя для левого поддерева, потом запускает данную функцию для корня, потом запускает себя для правого поддерева.
INFIX_TRAVERSE ( f ) — обойти всё дерево, следуя порядку (левое поддерево, вершина, правое поддерево).
PREFIX_TRAVERSE ( f ) — обойти всё дерево, следуя порядку (вершина, левое поддерево, правое поддерево).
POSTFIX_TRAVERSE ( f ) — обойти всё дерево, следуя порядку (левое поддерево, правое поддерево, вершина).
INFIX_TRAVERSE:
Дано: дерево Т и функция f
Задача: применить f ко всем узлам дерева Т в порядке возрастания ключей
Алгоритм:
Если дерево пусто, остановиться.
Иначе
Рекурсивно обойти левое поддерево Т.
Применить функцию f к корневому узлу.
Рекурсивно обойти правое поддерево Т.
В простейшем случае, функция f может выводить значение пары (K,V). При использовании операции INFIX_TRAVERSE будут выведены все пары в порядке возрастания ключей. Если же использовать PREFIX_TRAVERSE, то пары будут выведены в порядке, соответствующим описанию дерева, приведённого в начале статьи.
Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов.
Первая операция — INFIX_TRAVERSE — позволяет обойти все узлы дерева в порядке возрастания ключей и применить к каждому узлу заданную пользователем функцию обратного вызова f. Эта функция обычно работает только c парой (K,V), хранящейся в узле. Операция INFIX_TRAVERSE реализуется рекурсивным образом: сначала она запускает себя для левого поддерева, потом запускает данную функцию для корня, потом запускает себя для правого поддерева.
INFIX_TRAVERSE ( f ) — обойти всё дерево, следуя порядку (левое поддерево, вершина, правое поддерево).
PREFIX_TRAVERSE ( f ) — обойти всё дерево, следуя порядку (вершина, левое поддерево, правое поддерево).
POSTFIX_TRAVERSE ( f ) — обойти всё дерево, следуя порядку (левое поддерево, правое поддерево, вершина).
INFIX_TRAVERSE:
Дано: дерево Т и функция f
Задача: применить f ко всем узлам дерева Т в порядке возрастания ключей
Алгоритм:
Если дерево пусто, остановиться.
Иначе
Рекурсивно обойти левое поддерево Т.
Применить функцию f к корневому узлу.
Рекурсивно обойти правое поддерево Т.
В простейшем случае, функция f может выводить значение пары (K,V). При использовании операции INFIX_TRAVERSE будут выведены все пары в порядке возрастания ключей. Если же использовать PREFIX_TRAVERSE, то пары будут выведены в порядке, соответствующим описанию дерева, приведённого в начале статьи.
а вот с помощью этого всего
Цитата:
1. inorder: c m v h n q i q
2. preorder: q n v m c h q i
3. postorder: c m h v n i q q
2. preorder: q n v m c h q i
3. postorder: c m h v n i q q
с помощью этих вариантов обходов нужно нарисовать дерево.
Цитата: webdev
traverse - это способы обхода дерева
Вот именно traverse, а не traversen. И вот именно, обход дерева - устоявшийся русский термин, гораздо более понятный всем нежели это.
Цитата:
Эта функция обычно работает только c парой (K,V), хранящейся в узле.
Цитата:
с помощью этих вариантов обходов
а где в вариантах - пары?
По ходу вы не понимаете что я спрашиваю. :)
Значит так. Задание дано например
1вариант. три способа(заданы три последовательности обхода) построить дерево
2вариант. один способ(задана одна последовательность обхода) построить дерево
3вариант. два способа(заданы две последовательности обхода) построить дерево
Это не конкретный вопрос, а общий.
Есть ли что-то универсальное? Например я уверенно знаю, что в инордер первый элемент это самый левый элемент, в постордер корень - последний элемент и так д...
Значит так. Задание дано например
1вариант. три способа(заданы три последовательности обхода) построить дерево
2вариант. один способ(задана одна последовательность обхода) построить дерево
3вариант. два способа(заданы две последовательности обхода) построить дерево
Это не конкретный вопрос, а общий.
Есть ли что-то универсальное? Например я уверенно знаю, что в инордер первый элемент это самый левый элемент, в постордер корень - последний элемент и так д...
Цитата: webdev
Это не конкретный вопрос, а общий.
Есть ли что-то универсальное?
Похоже что, если бинарное дерево несбалансированное и/или неполное, то воссоздание точной структуры исходного дерева может быть под вопросом. С первого взгляда задача может быть решена методом перебора вариантов... А насколько велики входные данные?