import re

INPUT_FILE = 'input.txt'

class Node:
    def __init__(self, data=None):
        self.data = data
        self.left = None
        self.right = None

    def ensure_path(self, code, prompt_final):
        """
        Спускаемся по коду code от self.
        - Промежуточные узлы (всегда) создаём с запросом пользовательского ввода.
        - Конечный узел (последний символ) создаём:
            - если prompt_final=True  → с запросом,
            - если False              → автоматически (без запроса).
        Возвращает узел на конце пути.
        """
        node = self
        for i, c in enumerate(code):
            last = (i == len(code)-1)
            if c == '0':
                child = node.left
                if child is None:
                    # если это не финальный шаг — или финальный, но prompt_final
                    if not last or prompt_final:
                        while True:
                            val = input(f"Введите число для узла '{code[:i+1]}' (лево от '{code[:i]}'): ").strip()
                            if val.isdigit():
                                child = Node(int(val))
                                break
                            print("Нужно целое неотрицательное число.")
                    else:
                        # автоматом создаём пустой узел
                        child = Node()
                    node.left = child
                node = child
            else:  # c == '1'
                child = node.right
                if child is None:
                    if not last or prompt_final:
                        while True:
                            val = input(f"Введите число для узла '{code[:i+1]}' (право от '{code[:i]}'): ").strip()
                            if val.isdigit():
                                child = Node(int(val))
                                break
                            print("Нужно целое неотрицательное число.")
                    else:
                        child = Node()
                    node.right = child
                node = child
        return node

    def insert_from_file(self):
        try:
            with open(INPUT_FILE, 'r', encoding='utf-8') as f:
                for lineno, line in enumerate(f, 1):
                    txt = line.strip()
                    if not txt:
                        continue
                    parts = txt.split()
                    if len(parts)!=2 or not parts[0].isdigit() or any(ch not in '01' for ch in parts[1]):
                        print(f"[{lineno}] Пропущена: ожидается '<число> <код>'")
                        continue
                    number, code = int(parts[0]), parts[1]
                    # prompt_final=False: не спрашиваем для конечного узла
                    node = self.ensure_path(code, prompt_final=False)
                    if node.data is not None:
                        print(f"[{lineno}] Ошибка: узел '{code}' уже = {node.data}")
                    else:
                        node.data = number
        except FileNotFoundError:
            print(f"Файл '{INPUT_FILE}' не найден.")
            exit(1)

    def insert_manually(self):
        print("Ввод вручную (q — выход): <число> <код>")
        while True:
            s = input("> ").strip()
            if s.lower()=='q':
                break
            parts = s.split()
            if len(parts)!=2 or not parts[0].isdigit() or any(ch not in '01' for ch in parts[1]):
                print("Неверно, повторите.")
                continue
            number, code = int(parts[0]), parts[1]
            # prompt_final=True: спрашиваем и для конечного узла
            node = self.ensure_path(code, prompt_final=True)
            if node.data is not None:
                print(f"Ошибка: узел '{code}' уже = {node.data}")
            else:
                node.data = number

    def collect(self, path="", out=None):
        if out is None:
            out = []
        out.append((path, self.data))
        if self.left:
            self.left.collect(path+"0", out)
        if self.right:
            self.right.collect(path+"1", out)
        return out

    def print_tree(self, level=0):
        if self.right:
            self.right.print_tree(level+1)
        print("    "*level + f"-> {self.data}")
        if self.left:
            self.left.print_tree(level+1)


# ===== 主逻辑 =====
print("Построение дерева по кодам путей")
mode = input("1 — из файла, 2 — ручной ввод: ").strip()
root = Node(0)

if mode=='1':
    root.insert_from_file()
else:
    root.insert_manually()

print("\nСписок узлов (путь : значение):")
for path, val in root.collect():
    print(f"{path or 'root':>5} : {val}")

print("\nГоризонтальное представление:")
root.print_tree()