ruby中的对象树遍历

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是它的子对象，那么我们将有两条路径，从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]]

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

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

如果列表的长度可能足以使堆栈溢出，那么总是可以在不递归的情况下执行此操作。递归只是解决这个特殊问题的最简单方法。