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'. На каждом шаге:
          - если узел отсутствует:
              • если это НЕ последний символ (промежуточный) и prompt_intermediate=True → спрашиваем у пользователя
              • если это последний символ и prompt_final=True            → спрашиваем у пользователя
              • иначе создаём пустой узел автоматически
        В конце, если final_value задан (не None), присваиваем node.data = final_value.
        Возвращает получившийся узел.
        """
        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"Введите целое неотрицательное для узла '{code[:i+1]}' "
                            f"({'промежуточный' if not last else 'конечный'}) : "
                        ).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) в список → сортируем по len(code) →
        затем для каждой пары вызываем ensure_path(code, 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
            )
            # если узел уже имел data (каким-то образом) — предупреждаем
            if node.data != number:
                # если node.data был None, мы записали number → всё ок.
                # иначе (node.data != None и != number) — был конфликт.
                if node.data is not None:
                    print(f"[Код '{code}'] Узел уже = {node.data}, пропущена запись {number}.")

    def insert_manually(self):
        """
        Сначала собираем все пары в список, пока пользователь не введёт 'q'.
        Затем сортируем по len(code) и вызываем ensure_path(...) с prompt_intermediate=True, prompt_final=True.
        """
        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=True,
                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)  # по условию корень сразу содержит 0

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

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

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