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中的對象樹遍歷