Блог

Мне было интересно, как наилучшим образом реализовать древовидную структуру данных, чтобы иметь возможность перечислять пути всех уровней. Позвольте мне объяснить это на следующем примере:

      A
   /   
   B    C
   |    /
   D   E  F
  

Я хочу иметь возможность генерировать следующее:

 A
B
C
D
E
F
A-B
A-C
B-D
C-E
C-F
A-B-D
A-C-E
A-C-F
  

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

Всякий раз, когда вы обнаруживаете проблему на деревьях, просто используйте рекурсию 😀

 def paths(tree):
  #Helper function
  #receives a tree and 
  #returns all paths that have this node as root and all other paths

  if tree is the empty tree:
    return ([], [])
  else: #tree is a node
    root = tree.value
    rooted_paths = [[root]]
    unrooted_paths = []
    for subtree in tree.children:
        (useable, unueseable) = paths(subtree)
        for path in useable:
            unrooted_paths.append(path)
            rooted_paths.append([root] path)
        for path in unuseable:
            unrooted_paths.append(path)
    return (rooted_paths, unrooted_paths)

def the_function_you_use_in_the_end(tree):
   a,b = paths(tree)
   return a b
  

Просто еще один способ:

Каждый путь без повторений в дереве однозначно описывается его началом и завершением.

Итак, одним из способов перечисления путей является перечисление каждой возможной пары вершин. Для каждой пары относительно легко найти path (найдите общего предка и пройдите по нему).

Найдите путь к каждому узлу дерева, используя поиск в глубину, затем вызовите enumerate-paths(Path p) , где p — путь от корня к узлу. Давайте предположим, что путь p представляет собой массив узлов, p[0] [1] .. p[n] где p[0] — корень, а p[n] — текущий узел.

 enumerate-paths(p) {
    for i = 0 .. n  
        output p[n - i] .. p[n] as a path. 
}
  

Каждый из этих путей отличается, и каждый из них отличается от результатов, возвращаемых из любого другого узла дерева, поскольку никакие другие пути не заканчиваются на p[n] . Очевидно, что оно завершено, поскольку любой путь ведет от узла к некоторому узлу между ним и корнем. Это также оптимально, поскольку находит и выводит каждый путь ровно один раз.

Порядок будет немного отличаться от вашего, но вы всегда можете создать массив list путей, где A[x] это список путей длины x . Затем вы могли бы выводить пути в порядке их длины, хотя для этого потребовалось бы O (n) памяти.