ruby中的对象树遍历

一个包含多个从.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，其中X 1是与X2和X3作为其子一个条件，那么我们将有2条路径即开始在X1和X4结束。路径1：X1-> X2-> X4 路径2：X1-> X3-> X4

谢谢。

来源

2012-11-14 drake10k

由于您在解析后没有显示数据的格式，因此我会猜测:)以下是我将如何将分析的数据存储在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-27 09:23:36

ruby​​中的对象树遍历

回答

相关问题

ruby中的对象树遍历