Поиск дерева рекурсивно - PullRequest
Новая
       7

Поиск дерева рекурсивно

1 голос
/ 02 ноября 2019

Этот код пытается построить простую древовидную структуру, а затем искать в ней совпадения. Некоторые из них работают нормально. 

mutable struct Tree
    node::String
    children::Vector
end

Tree(str::String) =  Tree(str, [])
Tree(a::Vector) = Tree("root", a)

function Base.show(io::IO, tree::Tree, level = 0)
    print(io, "\t" ^ level * tree.node * "\n")
    for child in tree.children
        show(io, child, level + 1)
    end
end

function Base.length(t::Tree, counter = 1)
    for child in t.children
        if child != nothing
            counter += 1
            counter = length(child, counter)
        end
    end
    return counter
end

function buildtree(path)
    root = Tree(splitpath(path)[end])
    if isdir(path)
        for f in readdir(path)
            push!(root.children, buildtree(joinpath(path, f)))
        end
    end
    return root
end

function findfirstitem(t::Union{Tree, Array}, key)
    result = missing
    # if a number, return some of the children
    if isa(key, Int) || isa(key, UnitRange)
        return t.children[key]
    end
    # or look for a matching node/key
    if isa(key, String)
        for child in t.children
            if occursin(key, child.node)
                return child.node
            end
            if isa(child, Union{Tree, Array})
                findfirstitem(Tree(child.node, child.children), key)
            end
        end
    end
    return result
end

filetree = buildtree(homedir() * "/.julia/registries/General/A")

Запросы верхнего уровня работают нормально; 

julia> findfirstitem(filetree, "A")

"ACME"

julia> findfirstitem(filetree, 2:4)

3-element Array{Any,1}:
ADCME
Compat.toml
Deps.toml
Package.toml
Versions.toml
---------------------------

AIBECS
Compat.toml
Deps.toml
Package.toml
Versions.toml
---------------------------

AIControl
Compat.toml
Deps.toml
Package.toml
Versions.toml
---------------------------

julia> findfirstitem(filetree, "ACME")

"ACME"

Но рекурсия не раскручивается, как мне кажется: 

julia> findfirstitem(filetree, "Compat")

missing

и моя голова начинает болеть от этой рекурсии ...

1 Ответ

3 голосов
/ 02 ноября 2019

Функция не должна ставить задачу просмотра children, поскольку рекурсия позаботится об этом ... 


function findfirstitem(t::Union{Tree, Array}, key)
    # if a number, return some of the children
    if key isa Int || key isa UnitRange
        return t.children[key]
    end
    # or look for a matching node/key
    if key isa String
        if occursin(key,t.node)
            return t
        else
            for child in t.children
                found = findfirstitem(child, key)
                if !ismissing(found)
                    return found
                end
            end
        end
    end
    return missing
end

Но это зависит от ваших ожиданий алгоритма поиска. Должен ли он искать в глубину или ширину в первую очередь?

...