红宝石中的目标树遍历

Question

所以..。我有以下几点：

从.xml文件中检索到的具有多个属性的类。这些属性是如果对象是一个条件(它有两个子元素)及其名称的话。基本上，对象的子属性是其子属性的名称。

.xml看起来如下所示：

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

如果noChild为空，则意味着该对象不是条件。从.xml检索的所有对象都存储在一个数组中。

我需要的是以某种方式用它创建一棵树，并识别所有可以选择的路径，以便到达数组中的最后一个元素。该算法不需要遍历所有节点，只需要遍历到达数组最后一个元素所需的节点。

示例：

我们有4个对象: X1、X2、X3和X4，其中X1是以X2和X3作为子对象的条件，那么我们将有2条以X1开头，以X4结尾的路径。路径1: X1->X2->X4路径2: X1->X3->X4

谢谢。

Answer 1

由于解析后没有显示数据的格式，我将猜测:)下面是如何将分析过的数据存储在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]]

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

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]]

如果列表可能足够长，以致您的堆栈溢出，则始终可以不递归地执行此操作。递归只是解决这个特殊问题的最简单的方法。