Получить путь от каждого конечного узла до корня в древовидной структуре - PullRequest
Новая
       21

Получить путь от каждого конечного узла до корня в древовидной структуре

1 голос
/ 10 марта 2011

Как я могу превратить эту древовидную структуру 

[1, [2, [3, 4]], [5, [6, [7], 8]]]

1
   2
      3
      4
   5
      6
         7
      8

.... в эту структуру "перевернутого дерева", которая в основном содержит пути от всех конечных узлов до 1 (корень): 

[8, [5, [1]], 7, [6, [5, [1]]], 4, [2, [1]], 3, [2, [1]]]

8
   5
      1
7
   6
      5
         1
4
   2
      1
3
   2
      1

Результат даже не нужно структурировать в виде дерева, четыре плоских массива в правильном порядке также подойдут.

Похоже, Поиск в глубину может быть подходящим алгоритмом, но я не могу понять псевдокод (что возвращает инцидент ()), поэтому я застрял.

Если бы кто-то мог предложить метод Ruby (или действительно простой для понимания псевдокод) для преобразования исходного вложенного массива в массив результатов, я был бы бесконечно благодарен.

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

Ответы [ 4 ]

1 голос
/ 10 марта 2011

Вы можете использовать этот код. Это не лучший мой код, но я тоже изучаю ruby: D (это было хорошее упражнение) 

a = [1, [2, [3, 4]], [5, [6, [7], 8]]]

class Node
  attr_reader :value
  attr_reader :parent
  attr_reader :children

  def initialize(value, parent)
    @value = value
    @parent = parent
    @parent.add_child self unless parent == nil
    @children = []
  end

  def add_child(child)
    @children << child
  end

  def print_node(ident) 
    Range.new(0,ident).each {print ' '}
    print @value.to_s
    print "\n"
    children.each { |child| child.print_node (ident+4) }
  end

end

class Tree
  def self.from_array(array)
    process array, nil
  end


  def self.process(array, parent)
    node = nil
    array.each do |array_item| 
      if array_item.is_a? Numeric
        node = Node.new(array_item, parent) 
      else
        process(array_item, node)
      end
    end

    node
  end

  def self.print_paths_to_root node
    if node.children.empty? 
      puts print_path_to_root(node)
    else
      node.children.each do |child|
        print_paths_to_root child
      end  
    end
  end

  def self.print_path_to_root node 
    if node != nil
      node.value.to_s + '  ' + print_path_to_root(node.parent) 
    else
      ""
    end
  end
end

puts 'TREE'
root = Tree.from_array a
root.print_node 0

puts "\n\n\n"

puts 'PATH TO ROOT'
Tree.print_paths_to_root root
1 голос
/ 11 марта 2011

Чуть более компактный код: 

tree = [1, [2, [3, 4]], [5, [6, [7], 8]]]

def find_reverse_leaf_paths(nodes, prefix = [], paths = []) 
  leafs = []
  nodes.each do |node|
    if node.is_a?(Numeric)
      leafs.push(node)
    else
      prefix.push(leafs.pop) unless leafs.empty?
      leafs.clear
      find_reverse_leaf_paths(node, prefix, paths)
    end 
  end 
  leafs.each do |leaf|
    paths.push(prefix + [leaf])
  end 
  prefix.pop unless leafs.empty?
  paths.map { |path| path.reverse }.reverse
end

puts find_reverse_leaf_paths(tree).inspect
0 голосов
/ 11 марта 2011

Чтобы прояснить мысль, которую я пытался сделать в моих предыдущих комментариях к вопросу, я покажу некоторый код.Я использую только массив в качестве дерева, поэтому пустое дерево должно [root, []] (следовательно, защита для пустых дочерних элементов). 

class Array
  def paths
    root, children = self
    return [root] if children.empty? 
    children.map do |child|
      (child.is_a?(Array) ? child.paths : [[child]]).map do |tail|
        [root] + tail
      end
    end.flatten(1)
  end
end

tree = [1, [[2, [3, 4]], [5, [[6, [7]], 8]]]]
p tree.paths
# [[1, 2, 3], [1, 2, 4], [1, 5, 6, 7], [1, 5, 8]]

Конечно, это не тот ввод, который вы имели, ни результат, который вы хотели;-) но это та же идея, не так ли?Я хочу сказать, что если структура данных «логическая», код должен быть довольно простым (и функциональным, чтобы обходить дерево, нам не нужен императивный алгоритм!).

0 голосов
/ 10 марта 2011

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

Ваши первые 2 массива листьев будут развиваться следующим образом: 

1 - node 
12 - node
123 - leaf - output 321.
12 - pop out
124 - leaf - output 421

NWS

...