Re: Срочно требуется алгоритм сравнения бинарных деревьев.

From

Oleg I. Khovayko ()

To

Slava Antonov

Date

2003-01-07T17:23:09Z

Area

RU.ALGORITHMS

From: "Oleg I. Khovayko" <olegh@ncbi.nlm.nih.gov>

ATTN: ниже под словом "символ" подразумевается некий уникальный идентификатор
узла дерева. В примере входной задачи были использованы символы A,B.

Slava Antonov wrote:
> 
> Причем он должен считать вот такие деревья одинаковыми:
> 
>   /\          /\
> A   B       B  A


Ну, так это элементарно!

1. Для каждого дерева делать:
 1.1. Обойти дерево любым способом, и свалить из него содержимое в массив.
      Но свалить не только символ в узле дерева, а символ, конкатенированый с 
      с символом родителя через какой-нибудь разделитель, не встречающийся 
      в названии узла, причем порядок конкатенации не важен.
 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)