問 題

class Tree:

def __init__(self, label):

self.root = label

self.child = {}

def set_child(self, label, relate):

self.child[label] = relate

def get_root(self):

return self.root

def get_child(self):

return self.child

這么一顆樹結(jié)構(gòu)，該如何寫

def create_tree():

create_tree()

來調(diào)用樹結(jié)構(gòu)遞歸生成樹呢？

如果把對(duì)象寫在遞歸函數(shù)里，每次都會(huì)初始化，所以不行，如果寫在函數(shù)外面，又無法訪問到樹的對(duì)象，該如何寫呢？

還是只能使用字典來生成樹？

我嘗試使用了

def create_tree():

tree = Tree()

顯示是必須傳入?yún)?shù)，如果傳參，又回初始化樹結(jié)構(gòu)，求高人指點(diǎn)

解決方案

好像比較懂你的意思了, 試寫了一個(gè) Tree, 不知道你覺得怎麼樣XD

class Tree:

def __init__(self, name):

self.name = name

self.children = {}

def __iter__(self):

return iter(self.children)

def __str__(self):

return self.name

def __repr__(self):

return 'Tree("{}")'.format(self.name)

def relationiter(self):

yield from self.children.items()

def add_child(self, child, relation):

self.children[child] = relation

return child

def dfs(self, include_self=True):

if include_self:

yield self

for child in self.children:

yield child

yield from child.dfs(False)

def bfs(self, include_self=True):

if include_self:

yield self

trees = list(self.children.keys())

while True:

if not trees:

break

tree = trees.pop(0)

yield tree

trees += list(tree.children.keys())

import and create tree:

In [1]: from tree import Tree

In [2]: root = Tree('root')

...:

...: t11 = root.add_child(Tree('t11'), 30)

...: t12 = root.add_child(Tree('t12'), 40)

...:

...: t21 = t11.add_child(Tree('t21'), 15)

...: t22 = t11.add_child(Tree('t22'), 10)

...: t23 = t11.add_child(Tree('t23'), 35)

...:

...: t24 = t12.add_child(Tree('t24'), 20)

...:

測試 __str__ 跟 __repr__:

In [3]: root

Out[3]: Tree("root")

In [4]: print(root)

root

測試 iterator 和 relation iterator:

In [5]: for child in root:

...: print(child)

...:

t12

t11

In [6]: for child, relation in root.relationiter():

...: print(child, relation)

...:

t12 40

t11 30

測試 dfs 和 bfs:

In [7]: for tree in root.dfs(include_self=True):

...: print(tree)

...:

root

t12

t24

t11

t21

t22

t23

In [8]: for tree in root.bfs(include_self=True):

...: print(tree)

...:

root

t12

t11

t24

t21

t22

t23

這邊還有一個(gè)問題是, 不知道你原始的資料長甚麼樣子, 所以我無法猜測你怎麼 create tree。

如果是手動(dòng)一個(gè)一個(gè)加入 child 的話應(yīng)該就像上面那樣, create 跟 recursion 沒什麼關(guān)係, traverse 的時(shí)候才跟 recursion 有關(guān)。

除非你有一個(gè)對(duì)應(yīng)於 tree 結(jié)構(gòu)的資料, 字典, json 之類的, 然後你想要依資料自動(dòng)生成, 可能這種情況才會(huì)用 recursion 來 build tree。

因?yàn)槲覍?duì)於你實(shí)際的輸入不是很了解, 但是我猜你想問的是下面這件事情, 我舉個(gè)想像的例子說明這一點(diǎn), 假設(shè)我們的原始資料長這樣:

data = {

't11': {

'relation': 30,

'sub': {

't21': {

'relation': 15

},

't22': {

'relation': 10

},

't23': {

'relation': 35

}

}

},

't12': {

'relation': 40,

'sub': {

't24': {

'relation': 20

},

}

}

}

我必須要將這樣子的資料建出一個(gè) Tree 來, 這邊的確就跟 recursion 有關(guān)了, 首先我在 Tree 中增加一個(gè) classmethod:

@classmethod

def from_data(cls, name, data):

tree = cls(name)

if data:

for subname, subdata in data.items():

tree.add_child(

cls.from_data(subname, subdata.get('sub', None)),

subdata['relation'])

return tree

接著我可以用下面這種方式 recursive 地 create tree:

root = Tree.from_data('root', data)

測試:

for tree in root.bfs():

print(tree)

for child, relation in tree.relationiter():

print(' {}-{}'.format(child, relation))

結(jié)果:

root

t12-40

t11-30

t12

t24-20

t11

t21-15

t23-35

t22-10

t24

t21

t23

t22

P.S. 有問題歡迎討論!

掃一掃關(guān)注IT屋

微信公眾號(hào)搜索 “ IT屋 ” ，選擇關(guān)注與百萬開發(fā)者在一起

總結(jié)

以上是生活随笔為你收集整理的python 画树 递归_数据结构 - python如何递归生成树？的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。