Структуры - Алгоритмы - Дерево в виде списка списков - Python

Создадим класс Tree. С помощью дандер метода init установим начальные условия для нашего дерева: корень r и два пустых наследника, правый и левый.

Пропишем методы вставки значений для каждой ветки, правой insertRight и левой insertLeft:

1) копируем существующее дерево - список-списков, инициализированное в init, забираем первый элемент, для левой ветки, и второй элемент, для правой ветки.

2) Если ветка пустая: то добавляем новое значение и две дополнительных пустых ветки к ней(правую и левую), если же ветка непустая, то добавляем всех родителей добавленного нового значения.

Прописываем методы получения значений каждой ветки, корня, и изменения корня.

class Tree:
def __init__(self, r):
self.root = [r, [], []]

def insertLeft(self, newBranch):
root = self.root
t = root.pop(1)
if len(t) > 1:
root.insert(1,[newBranch,t,[]])
else:
root.insert(1,[newBranch, [], []])
return root

def insertRight(self, newBranch):
root = self.root
t = root.pop(2)
if len(t) > 1:
root.insert(2,[newBranch,[],t])
else:
root.insert(2,[newBranch,[],[]])
return root

def getRootVal(self):
return self.root[0]

def setRootVal(self,newVal):
self.root[0] = newVal

def getLeftChild(self):
return self.root[1]

def getRightChild(self):
return self.root[2]

r = Tree(3)
r.insertLeft(4)
r.insertLeft(5)
r.insertRight(6)
r.insertRight(7)
l = r.getLeftChild()
print(l)

Код взят с книги Брэда Миллер и Дэвид Рэнума - Структура и Алгоритмы