좋은 파이썬 트리 데이터 구조를 찾고 있습니다.

좋은 파이썬 트리 데이터 구조를 찾고 있습니다.

---

좋은 트리 데이터 구조 클래스를 찾고 있습니다. 나는 이 패키지 를 보았지만, 나는 파이썬 (프로그래밍이 아님)을 비교적 처음 접했기 때문에 더 나은 것이 있는지 모르겠습니다.

여기에있는 Pythonistas의 의견을 듣고 싶습니다. 정기적으로 사용하고 추천하는 좋아하는 트리 스크립트가 있습니까?

[편집하다]

명확히하기 위해, '트리'는 단순하게 정렬되지 않은 트리를 의미합니다 (음, 그것은 약간의 재귀 적 정의입니다. 트리가 필요한 이유 (예 : 유스 케이스). 플랫 파일에서 트리 데이터를 읽고 있으며 데이터에서 트리를 만들고 트리의 모든 노드를 트래버스해야합니다.

---

직접 굴려보세요. 예를 들어, 트리를 목록 목록으로 모델링하십시오. 사람들이 더 나은 추천을 제공하기 전에 구체적인 요구 사항을 자세히 설명해야합니다.

HelloGoodbye의 질문에 대한 응답으로 트리를 반복하는 샘플 코드입니다.

def walk(node):
    """ iterate tree in pre-order depth-first search order """
    yield node
    for child in node.children:
        for n in walk(child):
            yield n

한 가지 캐치는이 재귀 적 구현이 O (n log n)라는 것입니다. 내가 처리해야하는 모든 나무에 대해 잘 작동합니다. 아마도 파이썬 3의 하위 생성기가 도움이 될 것입니다.

---

다음과 같이 dicts의 멋진 트리를 만들 수 있습니다.

import collections

def Tree():
    return collections.defaultdict(Tree)

정확히 원하는 것이 아닐 수도 있지만 매우 유용합니다! 값은 리프 노드에만 저장됩니다. 작동 방식의 예는 다음과 같습니다.

>>> t = Tree()
>>> t
defaultdict(<function tree at 0x2142f50>, {})
>>> t[1] = "value"
>>> t[2][2] = "another value"
>>> t
defaultdict(<function tree at 0x2142f50>, {1: 'value', 2: defaultdict(<function tree at 0x2142f50>, {2: 'another value'})}) 

자세한 내용 은 요점을 참조하십시오 .

---

완료되지 않은 Brett Alistair Kromkamp가 작성한 모듈을 찾았습니다. 나는 그것을 끝내고 github에서 공개하고 이름을 treelib(original pyTree) :

https://github.com/caesar0301/treelib

도움이 되길 바랍니다 ....

---

바탕 defaultdict를 사용하여 한 줄 나무 위의 대답은 , 당신은 클래스를 만들 수 있습니다. 이렇게하면 생성자에서 기본값을 설정하고 다른 방법으로 빌드 할 수 있습니다.

class Tree(defaultdict):
    def __call__(self):
        return Tree(self)

    def __init__(self, parent):
        self.parent = parent
        self.default_factory = self

이 예제에서는 각 노드가 트리에서 부모를 참조 할 수 있도록 역 참조를 만들 수 있습니다.

>>> t = Tree(None)
>>> t[0][1][2] = 3
>>> t
defaultdict(defaultdict(..., {...}), {0: defaultdict(defaultdict(..., {...}), {1: defaultdict(defaultdict(..., {...}), {2: 3})})})
>>> t[0][1].parent
defaultdict(defaultdict(..., {...}), {1: defaultdict(defaultdict(..., {...}), {2: 3})})
>>> t2 = t[0][1]
>>> t2
defaultdict(defaultdict(..., {...}), {2: 3})
>>> t2[2]
3

다음으로, Tree 클래스에서 __setattr__을 재정 의하여 부모를 재 할당 할 때 부모에서 자식으로 제거하도록 할 수도 있습니다. 이 패턴으로 멋진 물건이 많이 있습니다.

---

정렬 된 아이들이있는 나무의 경우, 보통 다음과 같은 일을합니다 (좀 덜 일반적이고 제가하는 일에 맞게 조정 됨).

class TreeNode(list):

    def __init__(self, iterable=(), **attributes):
        self.attr = attributes
        list.__init__(self, iterable)

    def __repr__(self):
        return '%s(%s, %r)' % (type(self).__name__, list.__repr__(self),
            self.attr)

You could do something comparable with a dict or using DictMixin or it's more modern descendants if you want unordered children accessed by key.

---

It might be worth writing your own tree wrapper based on an acyclic directed graph using the networkx library.

---

Another good and easy to use implementation of trees in Python is pyTree: https://github.com/caesar0301/pyTree

pyTree also provides the posibility visualizing the tree:

Harry[harry]
|___ Jane[jane]
|    |___ Diane[diane]
|         |___ George[george]
|              |___ Jill[jill]
|         |___ Mary[mary]
|    |___ Mark[mark]
|___ Bill[bill]

---

Here's something I was working on.

class Tree:
    def __init__(self, value, *children):
        '''Singly linked tree, children do not know who their parent is.
        '''
        self.value = value
        self.children = tuple(children)

    @property
    def arguments(self):
        return (self.value,) + self.children

    def __eq__(self, tree):
        return self.arguments == tree.arguments

    def __repr__(self):
        argumentStr = ', '.join(map(repr, self.arguments))
        return '%s(%s)' % (self.__class__.__name__, argumentStr)

Use as such (numbers used as example values): t = Tree(1, Tree(2, Tree(4)), Tree(3, Tree(5)))

---

Would BTrees help? They're part of the Zope Object Database code. Downloading the whole ZODB package is a bit of overkill, but I hope the BTrees module would be at least somewhat separable.

---

I think, from my own experience on problems with more advanced data structures, that the most important thing you can do here, is to get a good knowledge on the general concept of tress as data structures. If you understand the basic mechanism behind the concept it will be quite easy to implement the solution that fits your problem. There are a lot of good sources out there describing the concept. What "saved" me years ago on this particular problem was section 2.3 in "The Art of Computer Programming".

참고URL : https://stackoverflow.com/questions/3009935/looking-for-a-good-python-tree-data-structure