Re: Обработка деревьев

From

Eduard Vatutin (2:5035/43.25)

To

Serge Nozhenko

Date

2002-10-30T12:12:58Z

Area

RU.ALGORITHMS

 _Приветик_ Serge!
30.10.02 в 02:02, Serge Nozhenko ·-───══> Eduard Vatutin:

 EV>> Возникла необходимость реализовать сабж. Деревья произвольной
 EV>> арности, вершины дерева могут быть только 2 типов, листья в общем
 EV>> случае N типов. Порядок следования ветвей от каждой вершины *не
 EV>> важен*. Необходимо проверить, является ли одно дерево поддеревом
 EV>> другого.
 SN>   Представить деревья каким-нибудь одномерным способом, сортируя
 SN> вершины с общим предком в определенном порядке. Далее все сводится к
 SN> поиску подстроки в строке, для которого есть готовые алгоритмы на
 SN> любой вкус.

Такой вариант у меня был. Только я до конца не решил, когда сортировать: то ли при построении дерева, то ли перед поиском поддерева. Что одно, что другое достаточно труднореализуемо (в смысле ресурсоемко ;), а операций таких надо будет проводить достаточно много (к примеру, среди 50 деревьев найти такую пару, в которой одно дерево является поддеревом другого, модифицировать набор деревьев (их станет на одно меньше) и опять то же самое, пока будут находиться поддеревья).
Может есть еще какие задумки?

--- _/Пока, Serge/_
 * Origin: Если долго мучаться - чего-нибудь да получится (2:5035/43.25)