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()