|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg I. Khovayko 2:5020/400 07 Jan 2003 18:23:09
To : Slava Antonov
Subject : Re: Срочно требуется алгоритм сравнения бинарных деревьев.
--------------------------------------------------------------------------------
ATTN: ниже под словом "символ" подразумевается некий уникальный идентификатор
узла дерева. В примере входной задачи были использованы символы A,B.
Slava Antonov wrote:
>
> Причем он должен считать вот такие деревья одинаковыми:
>
> /\ /\
> A B B A
Hу, так это элементарно!
1. Для каждого дерева делать:
1.1. Обойти дерево любым способом, и свалить из него содержимое в массив.
Hо свалить не только символ в узле дерева, а символ, конкатенированый с
с символом родителя через какой-нибудь разделитель, не встречающийся
в названии узла, причем порядок конкатенации не важен.
1.2. Сортируем массив
2. Сравнили массивы для обеих деревьев.
Если они одинаковы - деревья тоже одинаковы. Все.
Пример:
Дерево_1:
entity
fish
salmon
catfish
animal
cat
dog
drug
fentanil
aspirin
Дерево_2:
entity
animal
dog
cat
drug
aspirin
fentanil
fish
salmon
catfish
Для обоих деревьев выгруженый массив будет иметь строчки:
entity/fish
entity/animal
entity/drug
animal/dog
animal/cat
drug/aspirin
drug/fentanil
fish/salmon
fish/catfish
После сортировки оба массива будут одинаковы.
Вместо имен из узлов можно пользоваться указателями на узлы,
или некими уникальными номерами узлов.
В последнем случае, если номер узла помещается в 16 бит,
то в массив можно сваливать int-ы, полученные как:
int K = (N_предка << 16) | N_тек_узла;
Допустимы и любые другие правила конкатенации. Важно лишь,
чтобы конкатенированный результирующий символ в данном
контексте был уникальным.
--
#include <best/regards.hpp>
Oleg I. KHOVAYKO
(301)435-5885 || WEB: http://olegh.spedia.net
--- ifmail v.2.15dev5
* Origin: National Center for Biotechnology Information (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
