|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Eduard Vatutin 2:5035/43.25 28 Oct 2002 19:09:39
To : ALl
Subject : Обработка деревьев
--------------------------------------------------------------------------------
Возникла необходимость реализовать сабж. Деревья произвольной арности, вершины
дерева могут быть только 2 типов, листья в общем случае N типов. Порядок
следования ветвей от каждой вершины *не важен*.
Hеобходимо проверить, является ли одно дерево поддеревом другого.
Пример:
A A
/ \ / \
_A_ B 2 1
/ \ |
_1_ _2_ 3
Правое дерево является поддеревом левого.
Затрудняюсь реализовать проверку...
Есть пара рекурсивных переборных вариантов, однако деревья могут быть достаточно
большими, и тогда рекурсия будет буксовать.
Еще есть идея с приписыванием каждой вершине некоторого уникального в пределах
дерева значения, однако как его считать до конца не ясно...
Может кто занимался чем-то подобным? Выручайте...
--- _/Пока, ALl/_
* Origin: Пришел, увидел и... ушел! (2:5035/43.25)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
