Как я могу написать функцию, которая возвращает список ключей во вложенной таблице?

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: вернуть {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

Если в иерархии есть циклы, вам нужно отслеживать посещенные подтаблицы. См. глобальный код в демоверсии Lua live .

Answer 4

Это решение, которое я придумал, используя совет Дарио:

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