数据结构 - python如何递归生成树？

https://segmentfault.com/n/13...

大概这样写:

#!/usr/bin/env python
# encoding: utf-8

class Tree(object):
    def __init__(self, label):
        self.value = label
        self.child = {}

    def add_child(self, label, relate):
        # self.child.append(Tree())
        self.child[label] = Tree(relate)

    def get_value(self):
        return self.value

    def get_child(self):
        return self.child


def travelsal(tree):
    li = [tree]
    while True:
        try:
            t = li.pop()
            print t.get_value()
            child = t.get_child()
            if child:
                li.extend(child.values())
        except:
            break


def create_tree():
    root = Tree('root')
    root.add_child('c_key1', 'child_1')
    root.add_child('c_key2', 'child_2')
    print root.get_child()
    travelsal(root)


def main():
    create_tree()

if __name__ == "__main__":
    main()

好像比較懂你的意思了, 試寫了一個 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

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

如果是手動一個一個加入 child 的話應該就像上面那樣, create 跟 recursion 沒什麼關係, traverse 的時候才跟 recursion 有關。

除非你有一個對應於 tree 結構的資料, 字典, json 之類的, 然後你想要依資料自動生成, 可能這種情況才會用 recursion 來 build tree。

因為我對於你實際的輸入不是很了解, 但是我猜你想問的是下面這件事情, 我舉個想像的例子說明這一點, 假設我們的原始資料長這樣:

    data = { 
        't11': {
            'relation': 30,
            'sub': {
                't21': {
                    'relation': 15
                },
                't22': {
                    'relation': 10
                },
                't23': {
                    'relation': 35
                }
            }
        },
        't12': {
            'relation': 40,
            'sub': {
                't24': {
                    'relation': 20
                },
            }
        }
    }

我必須要將這樣子的資料建出一個 Tree 來, 這邊的確就跟 recursion 有關了, 首先我在 Tree 中增加一個 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))

結果:

root
    t12-40
    t11-30
t12
    t24-20
t11
    t21-15
    t23-35
    t22-10
t24
t21
t23
t22

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

我回答過的問題: Python-QA