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):
        """
        Спускается от self по строке code ('0'/'1'),
        автоматически создаёт любые отсутствующие узлы
        (промежуточные и конечный) с data=None.
        Возвращает узел в конце пути.
        """
        node = self
        for c in code:
            if c == '0':
                if node.left is None:
                    node.left = Node()
                node = node.left
            else:  # c == '1'
                if node.right is None:
                    node.right = Node()
                node = node.right
        return node

    def insert_from_file(self):
        """
        1) Считывает весь файл INPUT_FILE, собирает пары (number, code).
        2) Сортирует их по длине кода (чтобы предки вставлялись раньше потомков).
        3) Пробегает по отсортированному списку и для каждой пары:
           - гарантирует путь (ensure_path),
           - если data ещё None, записывает number; иначе — пишет предупреждение.
        """
        entries = []
        try:
            with open(INPUT_FILE, 'r', encoding='utf-8') as f:
                for lineno, line in enumerate(f, start=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}] Пропущена: требуется '<число> <код_пути из 0/1>'.")
                        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)
            if node.data is not None:
                print(f"[Код '{code}'] Предупреждение: узел уже содержит {node.data}, перезапись пропущена.")
            else:
                node.data = number

    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]
            # Для ручного режима всё ещё спрашиваем промежуточные узлы
            node = self.ensure_path(code)
            if node.data is not None:
                print(f"Ошибка: узел '{code}' уже заполнен значением {node.data}.")
            else:
                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):
        """
        Горизонтальный вывод дерева:
        правые дети выше, левые — ниже.
        Отступ каждого уровня = 4 пробела.
        """
        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():
    display = path or "root"
    print(f"{display:>5} : {val}")

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