Создадим класс 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)
Код взят с книги Брэда Миллер и Дэвид Рэнума - Структура и Алгоритмы
