Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > алгоритм поиска элемента одного дерева в другом


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

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

например.

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
Какова задача в оригинале (в смысле откуда деревья)?

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

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

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

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

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

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

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

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


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

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)