寻找构建目录树的更智能方法

Question

我有大的Json对象。除了别的以外，该对象还描述了其组件对象如何分层连接的树型关系。该对象知道其子对象是谁，但不（直接）知道其父对象是谁。下面的“ my_hash”例示了该结构。每个对象的ID为101、102等，名称为“一个”，“两个”等，并且可以有0、1个或多个子代。我正在尝试建立每个对象的“路径”。例如。由于代码的原因，对象名称“五”应具有路径“ /一/二/四”。基本上，我试图建立一种对象层次结构的目录结构。

下面的代码可以工作，但是看起来有点长，不是很雅致，不是很像Ruby。对于如何更有效，更优雅地执行此操作，我将不胜感激。我直觉我的代码可能不是很健壮，即很好地处理了异常。任何想法或帮助均表示赞赏。

附带说明，我只是在学习Ruby，到目前为止主要是在Perl中编程的。

class Tree
  def initialize
    @my_hash = {
      101 => ["one", [102, 107]],
      102 => ["two", [103, 104]],
      103 => ["three", []],
      104 => ["four", [105, 106]],
      105 => ["five", []],
      106 => ["six", []],
      107 => ["seven", [108]],
      108 => ["eight", []],
    }
    @child_to_parent_node = {}
    @id_to_name = {}
    @my_path_hash = {}
    @my_hash.keys.each do |key|
      @my_path_hash[key] = ""
    end
    @parent_path_id = []
  end

  def map_child_to_parent
    @my_hash.each do |key, value|
      @id_to_name.store(key, value[0])
      node_name, children = value[0], value[1]
      children.each do |child_id|
        @child_to_parent_node.store(child_id, node_name)
      end
    end
  end

  def build_path(id)
    parent = @child_to_parent_node[id]
    parent.nil? ? return : @parent_path_id << parent
    id = @id_to_name.key(parent)
    build_path(id)
    @parent_path_id
  end

  def update_tree
    @id_to_name.keys.each do |id|
      tmp_array = self.build_path(id)
      path = ""
      if (tmp_array.nil?)
        path = "/"
      else
        tmp_array.reverse.each do
          path = path + "/" + tmp_array.pop
        end
      end
      puts "id: #{id} path: #{path}"
    end
  end
end

my_tree = Tree.new
my_tree.map_child_to_parent
my_tree.update_tree

Answer 1

实际上，要解决此任务，您必须从叶到根遍历树，对吗？因此，您对树的表示对于该特定任务而言非常不便。如果您可以权衡一些内存以寻求更干净的解决方案，那么我将创建一个辅助结构，其中包含每个节点的父级。假设

@parents = @my_hash.each_with_object({}) do |(pid, props), acc|
  _, children = props
  children.each { |cid| acc[cid] = pid }
end

#=> {102=>101, 107=>101, 103=>102, 104=>102, 105=>104, 106=>104, 108=>107}

现在，可以使用几个辅助功能以非常简洁的方式解决任务。例如：

def id_by_name(name)
  id, _ = @my_hash.find { |k, v| v.first == name }
  id
end

def name_by_id(id)
  @my_hash[id].first
end

def path_to(node)
  path = [node]
  id = id_by_name(node)
  path.unshift(name_by_id(id)) while id = @parents[id]
  path.join("/")
end

path_to "five" #=> "one/two/four/five"

[请注意：解决方案仍然非常低效-主要是因为要获取节点ID的名称，我们必须在最坏的情况下遍历整个初始哈希。这是我们为不合适的数据结构所付出的代价。