value = 0
t = 0
summ = 0
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 getNodeString(self, node, nodepath):
        res = str(nodepath) + " " + str(node.data) + "\n"
        if (node.right != None):
            res = res + self.getNodeString(node.right, "\t" + str(nodepath) + "1")
        if (node.left != None):
            res = res + self.getNodeString(node.left, "\t" + str(nodepath) + "0")
        return str(res)

    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):  # выполнение задачи рекурсивным методом
 # инициализация переенной для хранения суммы значений узлов поддеревьев
        global t
        global value
        global summ
        if node != None:  # если узел существует
            if node.left == None and node.right == None:
                t += 1
                summ += value + node.data
            value += node.data
            self.recurse(node.left)
            self.recurse(node.right)
            value -= node.data
        if node != None:
            if node == self.root:
                return summ / t


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

                    else:
                        value -= peekNode.data
                        PrevNodeVisited = stack[len(stack) - 2]
                        lastNodeVisited = peekNode
                        stack.pop()
                        if len(stack) >1:
                            node = stack[len(stack) - 1]
                        elif len(stack) !=0:
                            node = stack[0]
                        else:
                            break
        return summ / t

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