时间戳

首页 > 解决方案 > 如何在python中构建任意深度的动态树？

python-3.x - 如何在python中构建任意深度的动态树？

问题描述

我需要建立一棵树，每个级别有n个子级和t个级别。每个节点将包含一个值。

我可以使用节点类制作一棵树，然后对多个级别使用多个 for 循环。但是我如何在没有 for 循环的情况下实现这一点（如何递归地做到这一点）？

我认为我在使用递归时犯了一些明显的错误。我从一个节点（根）和一些子节点开始，然后执行以下操作：

class Tree():
   def __init__(self):
     self.children = []
     self.data = []

   def create_children(self, childNum):
     for num in range(childNum):
        self.children.append(Tree())

   def create_data(self, data):
        for val in data:
           self.data.append(val)

root = Tree()  # create root
root.create_data([0])
root.create_children(3)  # create branch 1 with n=3 children

for b1child in root.children:
   b1child.create_data([2]) # create data of each node
   # create branch 2 
   b1child.create_children(3) # create 3 children at each node

   for b2child in b1child.children:
      b2child.create_data([2])         # create branch 3
      b2child.create_children(3)

      for b3child in b2child.children:
        b3child.create_data([2])

# test children exists with value 
root.children[0].children[1].children[2].data

标签： python-3.xtree

解决方案

在您的课程中使用递归方法最容易做到这一点Node。像这样的东西，虽然你需要添加一些东西来为每个Node实例提供一个值：

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

    def create_children(self, num_children, depth):
        if depth == 0:                                     # base case
            return

        for i in range(num_children):
            child = Node()
            self.children.append(child)
            child.create_children(num_children, depth-1)   # recurse!

然后，您的Tree代码可以创建根节点并调用root.create_children(n, t)（或者t-1，我不确定根节点是否应计为深度的一部分）。

推荐阅读