Преобразовать дерево (не двоичное) в список путей

Question

Преобразовать дерево (не двоичное) в список путей

использовать метод sum ()

df.groupby(['Fruit','Name']).sum()

Out[31]: 
               Number
Fruit   Name         
Apples  Bob        16
        Mike        9
        Steve      10
Grapes  Bob        35
        Tom        87
        Tony       15
Oranges Bob        67
        Mike       57
        Tom        15
        Tony        1

0

java algorithm

задан Uladzislau Kaminski 29 March 2019 в 09:34

3 ответа

Другие вопросы по тегам:

java algorithm

Похожие вопросы:

score 0 · Answer 1

У меня не было возможности протестировать этот код, но общая идея состоит в том, чтобы перебрать дерево через цикл for-each над дочерними элементами. Мы сохраняем текущий путь внутри строки, добавляя текущее имя на каждом шаге рекурсии. Затем при попадании в лист мы добавляем текущий путь в список.

public ArrayList<String> buildListOfPaths(Node tree) {
    ArrayList<String> list = new ArrayList<String>();
    String str = "";
    traverse(tree, list, str);
    return list;
}

// The idea on how to iterate the elements comes from:
// https://stackoverflow.com/a/19338057
public void traverse(Node root, ArrayList<String> list, String str){ 
    // we know it's a leaf so we can add this path to the list
    if (root.getChildren() == null) {
        list.add(str + root.name);
        return;
    } else {
        for(Node each : root.getChildren()){
            traverse(each, list, str + each.name);
        }
    }
}

score 0 · Answer 2

Вы также можете сделать это итеративным методом следующим образом:

public static List<String> getPaths(Node root) {
    List<String> paths = new LinkedList<>();
    if(root == null)
        return paths;
    Stack<Pair<Node, String>> stack = new Stack<>();
    stack.push(new Pair<>(root, ""));
    while(!stack.isEmpty()) {
        Pair<Node, String> cur = stack.pop();
        Node node = cur.getKey();
        String prefix = cur.getValue() + node.name;
        if(node.childs == null || node.childs.isEmpty())
            paths.add(prefix);
        for(Node child: node.childs)
            stack.push(new Pair<>(child, prefix + "/"));
    }
    return paths;
}

score 0 · Answer 3

Пример использования python для модификации DFS и сбора всех путей от корня до листа. Код не полностью проверен.

class Node:
    def __init__(self, index):
        self.index = index
        self.children = []

    def is_leaf(self):
        return len(self.children) == 0

    def __str__(self):
        return str(self.index)


def _remove_node_on_path_until_finding_parent_of_curr_node(curr_node, curr_path):
    while len(curr_path) > 0 and curr_node not in curr_path[-1].children:
        curr_path.pop(-1)


def modified_dfs(root):
    all_paths = []
    stack_node_to_visit = [root]
    curr_path = []
    while len(stack_node_to_visit) > 0:
        node = stack_node_to_visit.pop(-1)
        _remove_node_on_path_until_finding_parent_of_curr_node(node, curr_path)
        curr_path.append(node)
        if node.is_leaf():
            all_paths.append(curr_path.copy())
        else:
            for child in node.children:
                stack_node_to_visit.append(child)
    return all_paths


################# example usage ####################
root = Node(0)
for i in [1, 2, 3]:
    tmp_child = Node(i)
    root.children.append(tmp_child)
    for j in [100, 200, 300, 400]:
        tmp_child.children.append(Node(j + i))

path_list = modified_dfs(root)

for path in path_list:
    index_list = [str(node) for node in path]
    print(','.join(index_list))

В основном мы выполняем DFS как обычно, но сохраняем curr_path при переходе от корня к листу, обновляя curr_path.