Как итеративно создавать атрибуты класса для общего дерева?

Question

Я изучаю структуры данных общего дерева и двоичного дерева, используя python в качестве обучающей среды.

Я вижу, что класс двоичного дерева обычно имеет три атрибута: его значение, левый потомок и правильный ребенок. И как только этот выбор дизайна сделан, он не требует никаких изменений.

Однако общее дерево может иметь любое количество дочерних элементов, ограниченных от 0 до бесконечности. Поэтому мне любопытно, как я могу создать переменное число детей (например, child_1 ... child_500)?

Не думаю ли я об этом неправильно? Возможно, у каждого дерева должен быть атрибут children, представляющий собой список значений или словарь, ключами которого являются имена child_1 ... child_500, а значениями являются их children ..?

Answer 1

Как уже отмечали другие, переменное количество именованных атрибутов станет громоздким. Список был бы хорошей идеей. Лично я рекомендую адаптировать архитектуру связанного списка.

Определите класс GeneralTreeNode и определите атрибуты как value, parent, child, left_sib и right_sib. Вы можете думать о крайнем левом брате как о «первенце» (это потому, что на него ссылаются как на only дочерний узел его родительского узла. Доступ ко всем остальным братьям и сестрам можно получить, пройдя по крайнему левому брату.

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

Надеюсь, это поможет!

class GeneralTreeNode():

def __init__(self,value=None,parent=None,child=None,left_sib=None,right_sib=None):
    self.value = value
    self.parent = parent
    self.child = child
    self.left_sib = left_sib
    self.right_sib = right_sib

def get_value(self):
    return self.value

def get_parent(self):
    return self.parent

def get_child(self):
    return self.child

def get_left(self):
    return self.left_sib

def get_right(self):
    return self.right_sib   

def set_parent(self,parent):
    self.parent = parent

def set_child(self,child):
    self.child = child

def set_left(self,left_sib):
    self.left_sib = left_sib

def set_right(self,right_sib):
    self.right_sib = right_sib


a1 = GeneralTreeNode(value='a1')
b1 = GeneralTreeNode(value='b1')
b2 = GeneralTreeNode(value='b2')
a1.set_child(b1)
b1.set_parent(a1)
b1.set_right(b2)
b2.set_left(b1)

a1.get_child().get_right().get_value()
>>>> 'b2'