python - 打印n叉树python的所有路径

Question

我想在 python 中打印 N 叉树中从根到叶节点的所有路径。我有一个在二叉树中打印它的想法，但在 N 元中这样做并没有给我正确的结果。

我在此处弹出并访问子节点列表中的每个节点，但不确定如何为每个叶节点分别打印路径。

class createnode:
 def __init__(self,val):
   self.data=val
   self.child=[]

def traverse(root):
    global path
    if root.child:
     while(len(root.child)>0):
       x=root.child.pop(0)
       path.append(x.data)
       traverse(x)
    else:
      printarray(path)

def printarray(path):
  print(path)


root = createnode(10)
root.child.append(createnode(2))
root.child.append(createnode(4))

root.child[0].child.append(createnode(15))
root.child[0].child.append(createnode(20))
root.child[0].child.append(createnode(25))
root.child[0].child.append(createnode(30))

root.child[1].child.append(createnode(45))
root.child[1].child.append(createnode(50))
root.child[1].child.append(createnode(55))
root.child[1].child.append(createnode(60))
path=[]
total_val=30
traverse(root)

预期输出:

10、2、15

10, 2, 20

10、2、25

10、2、30

10, 4, 45

10, 4, 50

10, 4, 55

10, 4, 60

Answer 1

试试这个:

def traverse(node, path = []):
    path.append(node.data)
    if len(node.child) == 0:
        print(path)
        path.pop()
    else:
        for child in node.child:
            traverse(child, path)
        path.pop()

使用您的示例生成以下输出:

[10, 2, 15]
[10, 2, 20]
[10, 2, 25]
[10, 2, 30]
[10, 4, 45]
[10, 4, 50]
[10, 4, 55]
[10, 4, 60]