Каков наилучший способ реализовать древовидную структуру в Python

Question

Каков наилучший способ реализации древовидной структуры (универсальной, а не двоичной) в python?Моя интуиция имела бы следующий скелет:

class TNode(self, data):
   #enter things for each individual node

class TStructure(self):
   #enter code for implementing nodes that reference each other.

Answer 1

Почему бы просто не иметь класс для узлов, который имеет список дочерних узлов?

Изменить, чтобы добавить скелет:

class TreeNode(object):
    def __init__(self, data, children=[]):
        self.data = data
        self.children = list(children)

    def add(self, child):
        self.children.append(child)
    ...

Там на самом деле не так много. Каждый TreeNode содержит набор дочерних узлов (конечные узлы просто имеют 0 дочерних элементов, что примерно так же близко к реализации в чистом коде самого определения листового узла дерева, как вы можете получить). Вы можете добавить методы для управления порядком дочерних элементов, но если вам нужно, возможно, вам будет лучше, если вы просто рассмотрите список children и будете использовать методы списка напрямую. Вы можете добавить такие методы, как search, но для общего дерева без известных ограничений упорядочения (как в бинарном дереве поиска, где содержимое одного поддерева меньше содержимого другого поддерева), для него не так уж много делать. Вы можете добавить методы генератора для обхода (с несколькими возможными стратегиями обхода).

Если вы хотите, чтобы только конечные узлы имели данные, то у вас есть отдельный класс для внутренних узлов и конечных узлов, где внутренние узлы имеют children, а конечные узлы имеют data.

Answer 2

посмотрите на networkx и объект Graph.

см. здесь

Если это домашнее задание, и вы должны реализовать его с нуля, я дам вам подсказку, что вам, вероятно, нужен класс для узлов и класс для ребер ...

EDIT:

Вам на самом деле не нужен класс структуры, если у вас есть класс узла и класс ребер, что-то, пересекающее граф, является просто вопросом поисковых алгоритмов после его реализации.

class Node:
    name=str()

class Edge:
    a = Node()
    b = Node()

и затем объедините их вместе с __init__ функциями для одного из двух классов в зависимости от того, как вы будете загружать данные.