Untitled

Hasli4

Jun 13th, 2025

324

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

Python 6.60 KB | None | 0 0

raw download clone embed print report

import re
# Имя входного файла с данными
INPUT_FILE = 'input.txt'
class Node:
"""
Класс узла двоичного дерева, который умеет сам:
- создавать промежуточные узлы по коду пути,
- вставлять себя из файла или вручную,
- собирать список всех узлов,
- рисовать себя «горизонтально».
"""
def __init__(self, data=None):
# data=None — узел пока пуст, data=int — узел заполнен числом
self.data = data
self.left = None
self.right = None
def ensure_path(self, code):
"""
По строке code из '0' и '1' спускаемся от self
(корня) на уровень целевого узла. Если на пути нет
промежуточного узла, сразу спрашиваем у пользователя,
какое там должно быть число, создаём узел и ставим его
на нужное место. Возвращает узел в конце пути.
"""
node = self
for i, c in enumerate(code):
# решаем: 0→лево, 1→право
if c == '0':
if node.left is None:
# отсутствует узел → спрашиваем у человека
while True:
val = input(f"Введите число для узла с кодом '{code[:i+1]}' (левый от '{code[:i]}'): ")
if val.isdigit():
node.left = Node(int(val))
break
print("Неверно, введите целое неотрицательное число.")
node = node.left
else: # c == '1'
if node.right is None:
while True:
val = input(f"Введите число для узла с кодом '{code[:i+1]}' (правый от '{code[:i]}'): ")
if val.isdigit():
node.right = Node(int(val))
break
print("Неверно, введите целое неотрицательное число.")
node = node.right
return node
def insert_from_file(self):
"""
Читает файл INPUT_FILE, строки вида:
<число> <код_пути>
и последовательно вставляет пары в дерево, создавая
промежуточные узлы по необходимости.
"""
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
number, code = int(parts[0]), parts[1]
node = self.ensure_path(code)
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):
"""
Позволяет пользователю вводить пары <число> <код_пути>
до тех пор, пока он не введёт 'q'.
"""
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):
"""
Рекурсивно собирает все узлы в список out в формате
[(код_пути, значение), ...]
"""
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 = path or "root"
print(f"{display_path:>5} : {val}")
# Горизонтальная печать дерева
print("\nГоризонтальное представление:")
root.print_tree()

Add Comment

Please, Sign In to add comment