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

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

只需应用递归深度优先搜索来查找特定元素并返回路径.

构造元素路径的递归步骤X.

• 如果当前元素是X:return{X}

• 如果当前元素不是X:

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