树遍历递归 [英] Tree traversal recursion

问题描述

我是编程新手。我正在做我的树项目

I am new to programming. I am working on my project of tree

我的树看起来像这样
树结构

我已经编写了遍历整个树的代码。目前，我的遍历将打印完整的树，例如：
A，B，E，F，C，D，G，H，I，J，K

I have written code to traverse the complete tree. Currently my traversel will print the complete tree like this A,B,E,F,C,D,G,H,I,J,K

def tree_traversal(self, node):
    if(node != None):
      print node.name
      for child_nodes in node.children:
          self.tree_traversal(child_nodes)

但是我想要这样的输出。

However I want to get the output like this.

[[A,B,E],[A,B,F],[A,C],[A,D,G,H],[A,D,G,I],[A,D,G,J],[A,D,G,K]]

推荐答案

由于您没有提供任何树/节点类，因此我做了一个测试：

Since you didn't give any tree/node class, I made one to test with:

class Node:
    def __init__(self, data, children=None):
        if children is None:
            children = []
        self.data = data
        self.children = children

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

    __repr__ = __str__

从图像中提取的树：

tree = Node("A", [
    Node("B", [
        Node("E"),
        Node("F"),
    ]),
    Node("C"),
    Node("D", [
        Node("G", [
            Node("H"),
            Node("I"),
            Node("J"),
            Node("K"),
        ])
    ])
])

您想要的是一种可以使所有可能的根都移到叶上的算法

What you want is an algorithm that can get all possible root to leaf paths.

def get_all_paths(node, path=None):
    paths = []
    if path is None:
        path = []
    path.append(node)
    if node.children:
        for child in node.children:
            paths.extend(get_all_paths(child, path[:]))
    else:
        paths.append(path)
    return paths

测试它会产生您想要的输出：

Testing it yields the output you wished for:

paths = get_all_paths(tree)
print(paths)
# Prints:
# [[A, B, E], [A, B, F], [A, C], [A, D, G, H], [A, D, G, I], [A, D, G, J], [A, D, G, K]]

但是请注意， [A，B，E，F] 不是有效的路径，因为 F 不是 E 的子级。所以我认为这是一个错误。

However note that [A,B,E,F] is not a valid path, as F is not a child of E. So I assume this was a mistake.

这篇关于树遍历递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！