VPF::алгоритм поиска элемента одного дерева в другом

tonchitos

Дата 18.3.2008, 16:28 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 447
Регистрация: 24.2.2007

Репутация: нет
Всего: 40

у меня два дерева. Одно дерево как структура данных, другое как графическая. Деревья одинаковы, те имеют одинаковую структуру и имена. В одном дереве выбран какой-то потомок.

Нужно найти этого потомка в другом дереве.

например.

Node1
Node11
  Node111
   Node1111
Node12
  Node 121
Node13
  Node131
   Node1311
   Node1312
Node132
Node2
Node3

Node1
Node11
  Node111
   Node1111
Node12
  Node 121
Node13
  Node131
   Node1311
   Node1312
Node132
Node2
Node3

вот предположим этого потомка надо найти. Предположим имена в разных ветках могут совпадать, но не могут совпадать 2 ветки одного уровня.те у одного родителя не может быть 2х детей с одинаковыми именами.

как блин. Рекусия, вроде, но точнее не соображу.

--------------------

– Люди забыли эту истину, – сказал Лис, – но ты не забывай: ты навсегда в ответе за всех, кого приручил.

Sardar

Дата 18.3.2008, 16:48 (ссылка)

(нет голосов)

Загрузка ...

Бегун

Профиль
Группа: Модератор
Сообщений: 6986
Регистрация: 19.4.2002
Где: Нидерланды, Groni ngen

Репутация: 1
Всего: 317

Какова задача в оригинале (в смысле откуда деревья)?

Если деревья выполнены простыми ссылками родитель:[потомки], то просто построй путь от искомой ноды (решение "в лоб"):

Код

уровень = 0;
смещения_в_потомках = [];

нода = искомая_нода;

пока (нода.имеет_родительскую_ноду) {
  уровень += 1;
  
  род_нода = нода.родительская_нода;
  потомки = род_нода.список_потомков;
  смещение = 0;

  пока(потомки[смещение] != нода) смещение += 1; //ищем ноду впотомках
  
  смещения_в_потомках.добавить смещение;
  нода = род_нода;
}

//в этом месте знаем как глубоко нода и главное путь да неё

нода = второе_дерево.корневая_нода;
пока(смещение_в_потомках.ещё_есть_элементы) {
  смещение = смещение_в_потомках.следующий_элемент;
  нода = нода.потомки[смещение];
}

//нода - ссылка на искомую ноду во втором дереве

Если есть некий уникальный признак, то можно его положить в хеш, доступ почти мгновенный. Если дерево снабдить счётчиками (читать NestedSet), то ноду можно точно указать по паре чисел, тогда целый шаг с постройкой обратного пути не нужен. Вообщем тут обширное поле для оптимизации smile

--------------------

Опыт - сын ошибок трудных © А. С. Пушкин
Процесс написания своего велосипеда повышает профессиональный уровень программиста. © Opik
Оценить мои качества можно тут.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »