0

Нужно написать дерево, которое хранило бы в ячейках символы из слов, которые были добавлены.

Задание звучит так: Хранение и распознавания слов на основе бинарного дерева. интерфейс основного класса должен содержать методы для добавления и роспизнавання указанного слова. Каждый узел дерева представляет собой объект, содержащий определенный символ, и ссылки на две ветви Left и Right. переход по ветви Left осуществляется если текущий символ строке распознаваемого совпадает с символом хранящейся в данном узле дерева. если символы не совпали осуществляется переход по ветке Right.

вот пример

введите сюда описание изображения

в таком порядке слова и были добавлены.

вот ещё код, который за это отвечает: https://hastebin.com/nekivugoni.py

текущая проблема: дерево не строится должным образом. введите сюда описание изображения

что я делаю не так?

8
  • ну... правильность тут не в счёт. они просто должны быть такими по условию. это практическая в университете. и я пытаюсь разобраться, что я делаю не так. ну и можно сказать, что в первом примере неправильно то, что первого слова (tesa) нет - оно пере записалось почему-то. на счёт кода - просто мне казалось, что его довольно много (60 строк) и будет удобнее смотреть там. наверное, можно что-то убрать, но даже не знаю, что.
    – Oleg Brony
    14 мар 2018 в 10:18
  • ну... я могу дать весь текст задачи. но он только породит больше вопросов. я попытался максимально упросить в меру своих возможностей. "вот так должно быть - а вот так по факту". материала из учебника (как и самого учебника) нет.
    – Oleg Brony
    14 мар 2018 в 10:22
  • может вас просят Двоичное дерево поиска реализовать?
    – jfs
    14 мар 2018 в 10:37
  • Хранение и распознавания слов на основе бинарного дерева. интерфейс основного класса должен содержать методы для добавления и роспизнавання указанного слова. Каждый узел дерева представляет собой объект, содержащий определенный символ, и ссылки на две ветви Left и Right. переход по ветви Left осуществляется если текущий символ строке распознаваемого совпадает с символом хранящейся в данном узле дерева. если символы не совпали осуществляется переход по ветке Right. вот всё задание. к сожалению, это не дерево для поиска. я уже писал деревья с цифрами. с ними проблем не возникло.
    – Oleg Brony
    14 мар 2018 в 10:39
  • Зачем повторять один и тот же вопрос с одними и теми же ошибками в коде? left_child и right_child как были None, так навсегда и остались.
    – Amaro Vita
    14 мар 2018 в 10:49

1 ответ 1

2

Каждый узел дерева представляет собой объект, содержащий определенный символ, и ссылки на две ветви Left и Right.

В Питоне:

from dataclasses import dataclass

@dataclass
class Node:
    value: str
    left: 'Node' = None
    right: 'Node' = None

Переход по ветви Left осуществляется если текущий символ строке распознаваемого совпадает с символом хранящейся в данном узле дерева. если символы не совпали осуществляется переход по ветке Right.

def extend_node(node, chars):
    for char in chars:
        node.left = Node(char)
        node = node.left

class BinaryTree:
    def __init__(self, words=()):
        self.__tree = None
        for word in words:
            self.add(word)

    def add(self, word):
        if not word:
            return  # do nothing
        chars = iter(word)
        if not self.__tree:  # first word
            node = self.__tree = Node(next(chars))
            extend_node(node, chars)
        else:
            parent = node = self.__tree
            assert node
            for char in chars:
                while True:
                    if not node:
                        node = Node(char)
                        setattr(parent, child, node)
                        extend_node(node, chars)
                        break
                    elif node.value == char:
                        parent, node, child = node, node.left, 'left'
                        break
                    else:
                        parent, node, child = node, node.right, 'right'

Чтобы из стандартного ввода слова прочитать:

tree = BinaryTree(map(str.strip, sys.stdin))
tree.to_dot(sys.stdout)

где to_dot() просто дерево в виде, понимаемом graphviz печатает:

$ echo $'tesa\nterm' | python . | dot -Tpng | display

binary-tree-tesa-term

4
  • | python . | - это не ошибка? 14 мар 2018 в 15:13
  • 1
    нет. Файл назван __main__.py (посмотрите по ссылке) — это позволяет текущую директорию (имя .) выполнить.
    – jfs
    14 мар 2018 в 15:15
  • наверное стоит добавить этот комментарий в ответ... Я думаю немногие знают о таком способе запуска скриптов... Например я не знал 14 мар 2018 в 15:17
  • @MaxU: эта возможность в Питоне с Python 2.6 присутствует, ~лет 10.
    – jfs
    14 мар 2018 в 15:31

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.