1

So... I have the following:

A class with several properties which are retrieved from an .xml file. These properties are if the object is a condition (it has two children) and its name. Basically, the object's children properties are the names of its children.

The .xml looks like this:

<object-2>
     <name>Object - 2</name>
     <yesChild>Object - 3</yesChild>
     <noChild>Object - 4</noChild>
</object-2>

If the noChild is empty, then it means that the object is not a condition. All objects retrieved from the .xml are stored into an array.

What I need is to somehow create a tree out of it and identify all paths that can be taken in order to reach the last element in the array. The algorithm does not need to traverse all nodes, just the ones it needs to reach the last element of the array.

Example:

We have 4 objects: X1, X2, X3 and X4, where X1 is a condition with X2 and X3 as its children then we will have 2 paths that start in X1 and end in X4. Path 1: X1->X2->X4 Path 2: X1->X3->X4

Thank you.

4

1 回答 1

0

由于您在解析后没有显示数据的格式，所以我猜测:) 以下是我将解析后的数据存储在 ruby​​ 对象中的方式（为清楚起见，使用新型哈希键语法）：

[ {yes: 2, no: 3},
  {yes: 4},
  {yes: 4},
  {yes: -1} ]

然后，可以递归地完成树遍历。只要您的数组不是几千个元素长，这将正常工作。

def tree(object_number, list)
  if object_number == list.size
    [[object_number]]
  else
    list[object_number-1].values.map { |obj_num|
      tree(obj_num,list)
    }.inject{|a,b| a+b}.map{|l| [object_number] + l}
  end
end

现在调用函数：

tree(1,data)
  => [[1, 2, 4], [1, 3, 4]]
data = [ {yes: 2, no: 3}, {yes: 4, no:5}, {yes:5, no:4}, {yes:5}, {yes: -1} ]
tree(1,data)
  => [[1, 2, 4, 5], [1, 2, 5], [1, 3, 5], [1, 3, 4, 5]]

它是如何工作的：构建此列表的最简单方法是向后，因为我们只有在完成所有路径后才知道路径的数量。所以这段代码一直跟随引用到最后，当它到达最后一个对象时，它将它作为一个单元素二维数组返回。

tree(5,list)
  => [[5]]

在每个递归级别，它获取递归调用的结果（作为列表列表返回）并将它自己的对象编号添加到每个内部列表中。因此，备份树：

tree(4,list) # prepends 4 to tree(5)
  => [[4,5]]
tree(3,list) # prepends 3 to tree(4) and tree(5)
  => [[3,4,5],[3,5]]
tree(2,list) # prepends 2 to tree(4) and tree(5)
  => [[2,4,5],[2,5]]
tree(1,list) # prepends 1 to tree(2) and tree(3)
  => [[1, 2, 4, 5], [1, 2, 5], [1, 3, 5], [1, 3, 4, 5]]

如果列表可能长到足以溢出堆栈，则始终可以在不递归的情况下执行此操作。递归只是解决这个特定问题的最简单方法。

于 2012-12-27T09:23:36.593 回答