如何编写一个返回嵌套表中的键列表的函数？

Question

我有一个分层嵌套的关联数组。它看起来像这样：

A = { 
    B = { 
     C = {}, 
     D = {}, 
    }, 
    E = { 
     F = { 
      G = {} 
     } 
    }, 
    H = {} 
} 

我想写一个函数，返回每个键的“祖先”。

所以：

f("A") = {"A"} 
f("B") = {"B","A"} 
f("C") = {"C","B","A"} 
f("G") = {"G","F","E","A"} 
f("fake") = {} 

我已经工作了，我需要使用递归，但我有困难的写入功能。有人能给我一些关于如何编写这样一个函数的指针吗？

（请不要把我同http://xkcd.com/138/！）

Answer 1

只需申请一个递归depth-first search找到你的特定元素，并返回路径。

构建元素路径的递归步骤X。

• 如果当前元素为X：返回{X}

• 如果当前元素不是X：

  1. 检查所有的子节点。
  2. 获取返回有效路径并向其中添加当前元素的子节点。
  3. 如果没有有效的子节点，则返回nil。

Answer 2

A = { 
    B = { 
     C = {}, 
     D = {}, 
    }, 
    E = { 
     F = { 
      G = {} 
     } 
    }, 
    H = {} 
} 

function f(root, find) 
    -- iterate over all child values 
    for k, v in pairs(root) do 
     if k == find then 
      -- found the match 
      return({find}) 
     else 
      -- no match, search the children 
      tmp = f(root[k], find) 
      if tmp ~= nil then 
       table.insert(tmp, 1, k) 
       return tmp 
      end 
     end 
    end 
end 

print(table.concat(f(A, "G"), " ")) 

，因为你无法检索次序最高的表的名称（在这种情况下，A），则可能需要嵌套该表到另一个表，如下面的例子：

r = {A = { 
    B = { 
     C = {}, 
     D = {}, 
    }, 
    E = { 
     F = { 
      G = {} 
     } 
    }, 
    H = {} 
} 
} 

在这种情况下，您需要调用f（r，“G”）的原因。

Answer 3

这是我想出了用达里奥的建议解决方案：

function checkTable(t, key) 
    if t[key] then 
     return {key} 
    else 
     for k, subtable in pairs(t) do 
      local children = checkTable(subtable,key) 
      if #children ~= 0 then 
       table.insert(children,1,k) 
       return children 
      end 
     end 
     return {} 
    end 
end 

Answer 4

如果有层次的循环，你需要跟踪访问子表。 请参阅Lua live demo中的globals code。