nastya1

class Node:
    def __init__(self, data=None, left=None, right=None):#описание труктуры узла дерева
        self.data = data#данные,которые хранит узел
        self.left = left#ссылка на левого сына
        self.right = right#ссылка на правого сына

    def __str__(self):#переопределение метода str()д для корректного отображения узла
        return 'Node [' + str(self.data) + ' Левый: ' + str(self.left) + ' Правый: ' + str(self.right) + ']'


class Tree:

    def __init__(self):
        self.root = None#ссылка на корень дерева

    def __str__(self):#переопределение метода str()д для корректного отображения дерева
        return str(self.root)

    def createTree(self, node, treelist, nodePath, data):#создание сцепленного предтавления дерева
        node.data = int(data)#присвоение узлу данных
        for nodes in treelist:#перебор всех строк
            if nodes[0][:-1:] == str(nodePath): # если узел с данным путем найден
                if nodes[0][len(nodes[0]) - 1] == "0":#описание для левого узла
                    node.left = Node()
                    self.createTree(node.left, treelist, nodes[0], nodes[1])
                elif nodes[0][len(nodes[0]) - 1] == "1":#описание для правого узла
                    node.right = Node()
                    self.createTree(node.right, treelist, nodes[0], nodes[1])

    def recurse(self, node):#выполнение задачи рекурсивным методом
        value = 0#инициализация переенной для хранения суммы значений узлов поддеревьев
        if node != None:#если узел существует
            value += self.recurse(node.left) + self.recurse(node.right)#ссумируем значения его сыновей
            if node.left != None or node.right != None:#если это не лист
                node.data = value#присваиваем значению узла значение переменной
        else:#если лист отсутствует
            return 0#возвращаем нуль
        return int(node.data)#возвращаем значение данного узла

    def nonrecurse(self):#выполнение задачи нерекурсивным методом
        node = self.root# начальный обход начинается с корня
        stack = []#инициализация стека для хранения узлов
        lastNodeVisited = None#иницилизация
        while stack != [] or node != None:#пока стек не опустел
            value = 0
            if node != None:
                stack.append(node)
                node = node.left
            else:
                peekNode = stack[len(stack) - 1]
                if peekNode.left == None and peekNode.right == None:
                    value = peekNode.data
                if peekNode.right != None and lastNodeVisited != peekNode.right:
                    node = peekNode.right
                else:
                    if peekNode.right != None:
                        value += peekNode.right.data
                    if peekNode.left != None:
                        value += peekNode.left.data
                    peekNode.data = value
                    lastNodeVisited = stack[len(stack) - 1]
                    stack.pop()


def main():
    treelist1 = []#инициализация списков для хранения узлов при считывании из txt
    file1 = open('Tree1.txt', 'r')#открытие файлов
    for line in file1:
        treelist1.append(line.split())#копирование строк в список
    tree2 = Tree()
    tree2.root = Node()
    tree2.createTree(tree2.root, treelist1, 0, treelist1[0][1])
    tree1 = Tree()
    tree1.root = Node()#инициализация деревьев
    tree1.createTree(tree1.root, treelist1, 0, treelist1[0][1])#создание сцепленной структуры дерева
    print("Дерево 1: " + str(tree1))#вывод сцеленной труктуры дерева
    tree1.recurse(tree1.root)#выполнение рекурсивного метода
    print("Дерево 1 рекурсивно: " + str(tree1))#вывод состояние дерева после рекурсивного метода
    tree2.nonrecurse()#выполнение нерекурсивного метода
    print("Дерево 1 не рекурсивно: " + str(tree1))#вывод состояние дерева после рекурсивного метода


if __name__ == '__main__':
    main()