#python #algorithm #data-structures #tree
#python #алгоритм #структуры данных #дерево
Вопрос:
Каков наилучший способ реализовать древовидную структуру (общую, а не двоичную) в python? Моя интуиция будет иметь следующий скелет:
class TNode(self, data):
#enter things for each individual node
class TStructure(self):
#enter code for implementing nodes that reference each other.
Комментарии:
1. если это домашнее задание, вы должны пометить его как таковое.
Ответ №1:
Почему бы просто не иметь класс для узлов, у которого есть список дочерних узлов?
Отредактируйте, чтобы добавить скелет:
class TreeNode(object):
def __init__(self, data, children=[]):
self.data = data
self.children = list(children)
def add(self, child):
self.children.append(child)
...
На самом деле в этом нет ничего особенного. Каждый древовидный узел содержит набор дочерних элементов (конечные узлы имеют только 0 дочерних элементов, что примерно настолько близко к реализации чистого кода самого определения конечного узла дерева, насколько вы можете получить). Вы могли бы добавить методы для управления порядком дочерних элементов, но если вам это нужно, вам, возможно, лучше просто рассмотреть children открытый список и напрямую использовать методы списка. Вы могли бы добавить такие методы, как search , но для общего дерева без известных ограничений упорядочения (например, в двоичном дереве поиска, где содержимое одного поддерева меньше содержимого другого поддерева), ему не так много нужно сделать. Вы могли бы добавить методы генератора для обхода (с несколькими возможными стратегиями обхода).
Если вы хотите, чтобы данные были только у конечных узлов, тогда у вас есть отдельный класс для внутренних узлов и конечных узлов, где внутренние узлы имеют children и конечные узлы имеют data .
Комментарии:
1. @cfarm54: вы создаете объект node для представления корневого узла дерева и заполняете дерево, добавляя объекты дочернего узла в список корневого узла. Конечно, каждый дочерний объект узла также содержит список, поэтому вы можете продолжать расширять дерево. Узел с пустым списком будет конечным узлом.
2. @cfarm64: Конечно, вам все равно может понадобиться класс дерева с реализациями алгоритмов поиска, добавления и удаления из дерева.
3. @robjb Или вы могли бы просто поместить это в класс node, поскольку каждый узел является корнем поддерева.
4. Добавлен скелет @cfarm54. Ник Джонсон совершенно прав в комментарии robjb; очень мало смысла иметь отдельный класс дерева, поскольку в дереве нет ничего, кроме корневого узла, поэтому гораздо удобнее, чтобы все узлы были деревьями.
5. Я вижу, что у вас будут узлы в каждом из списков, и эти узлы приведут к другим спискам узлов.
Ответ №2:
посмотрите на networkx и объект Graph.
смотрите здесь
Если это для домашней работы, и вам нужно реализовать с нуля, я дам вам подсказку, что вам, вероятно, нужен класс для узлов и класс для ребер…
Редактировать:
На самом деле вам не нужен класс structure, если у вас есть класс node и класс edge, что-то, пересекающее график, — это просто вопрос алгоритмов поиска после его реализации.
class Node:
name=str()
class Edge:
a = Node()
b = Node()
а затем объедините их с __init__ функциями для одного из двух классов в зависимости от того, как вы будете загружать данные.
Комментарии:
1. это не для домашней работы, но интересно, что вы упомянули класс для ребер. Итак, вы предполагаете, что у меня есть 3 класса: один для ребер, один для узлов, затем один для структуры?
2. несмотря на мое редактирование, я бы сказал, что если это не для домашней работы, зачем изобретать мир заново … networkx на самом деле довольно плохая задница для структур данных python.