Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Скриптовые языки программирования > Python
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 22.02.2017, 18:38   #1
hunter24
Пользователь
 
Регистрация: 13.04.2016
Сообщений: 13
По умолчанию Поиск элементов бинарного дерева - Python

Всем привет, нужна помощь. Дана простая реализация бинарного дерева в виде класса Tree. В классе реализован метод добавления элементов к дереву. Задача – реализовать еще два метода: 
метод find(value). В качестве аргумента метод принимает значение (число). Метод должен возвращать True, если элемент найден в дереве или False, если такой элемент отсутствует. 
метод print(). Этот метод не принимает никаких аргументов. Результат работы метода – вывод структуры дерева (значений его элементов и иерархии) на экран (вывод может иметь любой осмысленный вид, но запрещается выводить все элементы в одну строку).
Плюсом будет имплементация специального метода для возможности использовать с инстансом класса Tree конструкцию вида:
root = Tree(10)
if 10 in root:
...

Код:
class Tree: 
 
    def __init__(self, value, root=None):
        # left and right child nodes
        self.lchild = None
        self.rchild = None 
        # node value
        self.value = value
        # parent element for current node
        self.root = root 
 
    def add(self, value):
        # track current node (level)
        current_node = self 
        # track parent node
        last_node = None
        # search the place to insert new node
        while current_node:
            last_node = current_node 
 
            if value > current_node.value: 
               current_node = current_node.rchild
            elif value < current_node.value:
                 current_node = current_node.lchild
            else: # element already presented in tree
                return False 
 # create new node and link it with parent
        new_node = Tree(value, last_node)
        if value > last_node.value:
           last_node.rchild = new_node
        else:
            last_node.lchild = new_node
            return True
Пример работы класса:
>> root = Tree(10)
>> root.add(9)
>> root.add(8)
>> root.add(11)
>> root.add(15)
>> root.add(16)
>> root.add(12)
>> root.add(2)

‘‘‘ Поиск элемента ‘‘‘
>> root.find(11)
True
>> root.find(5)
False

‘‘‘ Вывод элементов дерева ‘‘‘
>> root.print() 10
9 11
8 15
2 12 16
hunter24 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Поиск предка 2-ух элементов бинарного дерева (Cи) torren108 Помощь студентам 0 11.09.2012 22:48
преобразование бинарного дерева Lerris Общие вопросы C/C++ 0 09.03.2012 21:12
Haskell поиск пути от корня бинарного дерева до узла [x,y] Fill_x Помощь студентам 0 10.11.2011 18:34
Поиск суммы элементов дерева Sparky Помощь студентам 1 07.03.2010 16:12