Структура данных «Дерево». Представление деревьев.

Определение

Дерево — это иерархическая структура данных, состоящая из вершин (узлов) и ребер, которые их соединяют. Дерево — это особый тип графа, который не содержит циклов.

Основные способы представления деревьев:

1. Список дочерних узлов (Child List) - каждый узел хранит список ссылок на его дочерние узлы. Этот способ хорошо подходит для общих деревьев, где количество дочерних узлов каждого узла не ограничено. Однако он может быть неэффективным для бинарных деревьев, так как в нем есть много нулевых ссылок.
2. Ссылка на родителя (Parent Link) - каждый узел хранит ссылку на своего родителя. Это может быть полезно для быстрого доступа к родительскому узлу, но может занимать дополнительное место в памяти и усложнять операции вставки и удаления.
3. Список смежности (Adjacency List) - этот метод используется в графах, где каждый узел хранит список своих смежных узлов. В деревьях каждый узел имеет только одного родителя, поэтому каждый элемент списка смежности соответствует дочернему узлу.
4. Массив или список с индексацией (Array or Indexed List - дерево может быть представлено в виде массива или списка, где каждый узел имеет определенный индекс. Например, для бинарного дерева индексация может быть выполнена с использованием формулы left_child_index = 2 * parent_index + 1 и right_child_index = 2 * parent_index + 2. Этот способ представления деревьев удобен для доступа к узлам по индексу, но требует больше памяти для хранения нулевых элементов, если дерево не является полным.

Бинарное дерево

class BinaryTree:  
    def __init__(self, val):  
        self.value = val  
        self.parent = None  
        self.left = None  
        self.right = None  
	  
    def printChildren(self):  
        print(self)  
        if self.left:  
            self.left.printChildren()  
        if self.right:  
            self.right.printChildren()  
	  
    def addLeft(self, val):  
        node = BinaryTree(val)  
        node.parent = self  
        self.left = node  
	  
    def addRight(self, val):  
        node = BinaryTree(val)  
        node.parent = self  
        self.right = node  
	  
    def __str__(self):  
        return str(self.value)

N-арное дерево

class Tree:  
    def __init__(self, val):  
        self.value = val  
        self.parent = None  
        self.children = []  
	
    def add(self, val):  
        node = Tree(val)  
        node.parent = self  
        self.children.append(node)