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_intermediate: bool, prompt_final: bool, final_value=None):
        """
        Спускается от self по коду '0'/'1'. Если необходимый child is None:
         - для промежуточных позиций (не последний символ):
             если prompt_intermediate=True → спрашиваем, иначе создаём пустой;
         - для последнего символа:
             если prompt_final=True      → спрашиваем,
             else (prompt_final=False)  → создаём пустой.
        В конце, если final_value не None, записывает его в node.data.
        """
        node = self
        length = len(code)
        for i, c in enumerate(code):
            last = (i == length - 1)
            branch = 'left' if c == '0' else 'right'
            child = getattr(node, branch)
            if child is None:
                # решить, спрашивать ли у пользователя
                need_prompt = (not last and prompt_intermediate) or (last and prompt_final)
                if need_prompt:
                    while True:
                        text = input(
                            f"Введите целое для {'промежуточного' if not last else 'конечного'} "
                            f"узла '{code[:i+1]}' (от '{code[:i]}'): "
                        ).strip()
                        if text.isdigit():
                            child = Node(int(text))
                            break
                        print("Ошибка: нужно целое неотрицательное число.")
                else:
                    child = Node()
                setattr(node, branch, child)
            node = child

        if final_value is not None:
            node.data = final_value
        return node

    def insert_from_file(self):
        """
        Читает весь INPUT_FILE, собирает (number, code), сортирует по длине кода,
        затем для каждой пары: ensure_path(..., prompt_intermediate=True, prompt_final=False, final_value=number).
        """
        entries = []
        try:
            with open(INPUT_FILE, 'r', encoding='utf-8') as f:
                for lineno, line in enumerate(f, 1):
                    text = line.strip()
                    if not text: continue
                    parts = text.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
                    entries.append((int(parts[0]), parts[1]))
        except FileNotFoundError:
            print(f"Ошибка: файл '{INPUT_FILE}' не найден.")
            exit(1)

        entries.sort(key=lambda x: len(x[1]))
        for number, code in entries:
            node = self.ensure_path(
                code,
                prompt_intermediate=True,   # спрашиваем только промежуточные
                prompt_final=False,         # НЕ спрашиваем конечный
                final_value=number          # сразу записываем из файла
            )
            # если тут node.data уже не равно number → был конфликт
            if node.data != number:
                print(f"[Код '{code}'] узел уже = {node.data}, пропуск {number}.")

    def insert_manually(self):
        """
        Сначала собираем список вводимых пар, затем строим дерево точно так же,
        но конечный узел НЕ спрашиваем (prompt_final=False), поскольку пользователь ввёл его сам.
        """
        entries = []
        print("Ручной ввод. Формат: <число> <код 0/1>, '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
            entries.append((int(parts[0]), parts[1]))

        entries.sort(key=lambda x: len(x[1]))
        for number, code in entries:
            node = self.ensure_path(
                code,
                prompt_intermediate=True,   # спрашиваем промежуточные
                prompt_final=False,         # НЕ спрашиваем конечный
                final_value=number          # записываем введённое число
            )
            if node.data != number:
                print(f"[Код '{code}'] узел уже = {node.data}, пропуск {number}.")

    def collect(self, path="", out=None):
        """Собирает [(код_пути, data), ...] всех узлов."""
        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()