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

From

Eduard Vatutin (2:5035/43.25)

To

ALl

Date

2002-10-28T18:09:39Z

Area

RU.ALGORITHMS

 _Приветик_ ALl!

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

Пример:
                       A           A
                      / \         / \
                     _A_   B       2   1
                    / \  |
                   _1_   _2_ 3

Правое дерево является поддеревом левого.

Затрудняюсь реализовать проверку...
Есть пара рекурсивных переборных вариантов, однако деревья могут быть достаточно большими, и тогда рекурсия будет буксовать.
Еще есть идея с приписыванием каждой вершине некоторого уникального в пределах дерева значения, однако как его считать до конца не ясно...

Может кто занимался чем-то подобным? Выручайте...

--- _/Пока, ALl/_
 * Origin: Пришел, увидел и... ушел! (2:5035/43.25)