Нахождение корневого значения двоичного дерева? - PullRequest
Новая
       3

Нахождение корневого значения двоичного дерева?

2 голосов
/ 20 февраля 2012

У меня есть массив, в котором хранятся отношения значений, что делает несколько деревьев примерно такими:

enter image description here

Итак, в этом случае мой массив будет (root, связанный с)

(8,3) (8,10) (3,1) (3,6) (6,4) (6,7) (10,14) (14,13)

И я хотел бы установить для всех корневых значений в массиве основной корень в дереве (во всех деревьях):

(8,3) (8,1) (8,6) (8,4) (8,7) (8,10) (8,14) (8,13)

Какой алгоритм мне следует исследовать?

Ответы [ 2 ]

6 голосов
/ 20 февраля 2012

1) Составьте список всех уникальных первых элементов кортежей.

2) Удалите все элементы, которые также отображаются в качестве второго элемента кортежа.

3) Вы будетеостаться с корнем (8 здесь).Замените первые элементы всех кортежей этим значением.

РЕДАКТИРОВАТЬ:

Более сложный подход, который будет работать с несколькими деревьями, будет следующим:

Первый, преобразуйте в родительскую таблицу поиска: 

1 -> 3
3 -> 8
4 -> 6
6 -> 3
7 -> 6
10 -> 8
13 -> 14
14 -> 10

Далее выполните команду «найти родителя со сжатием пути» для каждого элемента:

1) 

1 -> 3 -> 8

дает 

1 -> 8
3 -> 8
4 -> 6
...

3) 

3 -> 8

4) 

4 -> 6 -> 3 -> 8

дает 

1 -> 8
3 -> 8
4 -> 8
6 -> 8
7 -> 6
...

6) 

6 -> 8 (already done)

7) 

7 -> 6 -> 8

и т. Д.

Результат: 

1 -> 8
3 -> 8
4 -> 8
6 -> 8
7 -> 8
...

Затем преобразуйте это обратно в список кортежей: 

(8,1)(8,3)(8,4)...

Родитель поиска с алгоритмом сжатия пути равен find_set для непересекающихся наборных лесов, например, 

int find_set(int x) const
{
    Element& element = get_element(x);
    int& parent = element.m_parent;
    if(parent != x)
    {
        parent = find_set(parent);
    }
    return parent;
}

Ключевым моментом является то, что сжатие пути помогает избежать большой работы.Например, в приведенном выше примере, когда вы выполняете поиск для 4, вы сохраняете 6 -> 8, что ускоряет последующие поиски, ссылающиеся на 6.

0 голосов
/ 20 февраля 2012

Итак, предположим, у вас есть список кортежей, представляющих точки: 

def find_root(ls):
  child, parent, root = [], [], []
  for node in ls:
    parent.append(node[0])
    child.append(node[1])

  for dis in parent: 
    if (!child.count(dis)): 
      root.append(dis)

  if len(root) > 1 : return -1 # failure, the tree is not formed well

  for nodeIndex in xrange(len(ls)):
    ls[nodeIndex] = (root[0], ls[nodeIndex][1])

  return ls
...