1 Тема від DimONN

  • DimONN
  • DimONN
  • Користувач
  • Поза форумом
  • Звідки: Київ
  • Дата реєстрації: 01.02.2018
  • Повідомлень: 44
    • Репутація: 6

Тема: Бінарне дерево і задачі до нього

Доброго дня!

Допоможіть, будь ласка, розібратись з бінарним деревом. Дан клас, який його реалізує. Стоїть задача: Вивести дерево на екран Print(t) з відображенням структури. Але як його взагалі ввести?

classBtree:
    '''Реалізує бінарне дерево.
    ''' def__init__(self):
        '''Створити порожнє дерево.
        '''
        self._data =None    #навантаження кореня дерева
        self._ls =None        #лівий син
        self._rs =None         #правий син

    def isempty(self):
        '''Чипорожнєдерево?.
         '''
         returnself._data ==None and self._ls ==None and self._rs ==None

    def maketree(self, data, t1, t2):
        '''Створити дерево.
          Дані у корені - data, лівий син -t1, правий син - t2
        '''
        self._data = data
        self._ls = t1
        self._rs = t2

    def root(self):
        '''Корінь дерева.
        '''
        if self.isempty():
            print('root: Деревопорожнє')
            exit(1)
        return self._data

    def leftson(self):
        '''Лівий син.
        '''
        if self.isempty():
            t = self
        else:
            t = self._ls
        return t

    def rightson(self):
        '''Правий син.
        '''
        if self.isempty():
            t = self
        else:
            t = self._rs
        return t

    def updateroot(self, data):
        '''Змінити корінь значенням data.
        '''
        if self.isempty():    #якщо дерево порожнє, додати лівого та правого сина
            self._ls = Btree()
            self._rs = Btree()
        self._data = data

    def updateleft(self, t):
        '''Змінити лівого сина значенням t.
        '''
        self._ls = t

    def updateright(self, t):
        '''Змінити правого сина значенням t.
        '''
        self._rs = t

2 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 617
    • Репутація: 13330

Re: Бінарне дерево і задачі до нього

Ну, найтупіше буде якось так:

-Корінь
|-гілка1
||-підгілка1-1
||-підгілка1-2
|-гілка2

Робити найпростіше рекурсією - вивести базу (кілька '|') і значення, викликати Print два рази для гілок зі збільшенням бази на '|'.

koala вебсайт

3 Відповідь від Teg Miles Востаннє редагувалося Teg Miles (23.11.2018 16:05:53)

  • Teg Miles
  • Teg Miles
  • Користувач
  • Поза форумом
  • Дата реєстрації: 20.01.2016
  • Повідомлень: 475
    • Репутація: 84

Re: Бінарне дерево і задачі до нього

Краще зроби функцію обходу по бінарному дереву одним зі методів: прямий обхід(preorder), симетричний обхід(inorder) або зворотній обхід(postorder). І друкуй кожного разу відповідний вузол, коли обходитимеш його.
Або можеш зібрати усе дерево у відповідний список і роздрукувати його.

4 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 617
    • Репутація: 13330

Re: Бінарне дерево і задачі до нього

Просто чудова порада! Ви колись намагалися розібрати, що відбувається в дереві з 15 нод по його списку у прямому порядку? Ну, наприклад, читати формули у польському записі?
Людині треба не у машиночитану форму перевести, а на екран.

koala вебсайт

5 Відповідь від DimONN

  • DimONN
  • DimONN
  • Користувач
  • Поза форумом
  • Звідки: Київ
  • Дата реєстрації: 01.02.2018
  • Повідомлень: 44
    • Репутація: 6

Re: Бінарне дерево і задачі до нього

Переписав бінарне дерево наступним чином:

class MyBTree(object):
    class Item(object):
        def __init__(self, data: int):
            self.left = None
            self.right = None
            self.data = data

    def __init__(self):
        self.root = None

    def is_empty(self):
        return self.root is None

    def insert(self, data):
        item = MyBTree.Item(data)
        if not self.root:
            self.root = item
        else:
            current_item = self.root
            while True:
                if current_item.data <= item.data:
                    if current_item.right is None:
                        current_item.right = item
                        return
                    else:
                        current_item = current_item.right
                else:
                    if current_item.left is None:
                        current_item.left = item
                        return
                    else:
                        current_item = current_item.left

    def print(self):
        self.root
        pass

Так воно заповнюється:

def fill_tree(btree: BTree):
    for i in range(10):
        data = random.randint(1, 101)
        btree.insert(data)
        print(data)


the_tree = BTree()
fill_tree(the_tree)

Підкажіть, будь ласка, як його роздрукувати у вигляді чисел від найменьшого до найбільшого. Тобто треба рекурсивно пройти по гілках від лівої сторони до правої. Але як? Почав писати метод print і затупив). Дякую!

6 Відповідь від koala Востаннє редагувалося koala (06.12.2018 10:40:30)

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 617
    • Репутація: 13330

Re: Бінарне дерево і задачі до нього

def print(self):
  if self.left:
    self.left.print()
  print(value)
  if self.right:
    self.right.print()
Подякували: DimONN1

koala вебсайт

7 Відповідь від P.Y.

  • P.Y.
  • P.Y.
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 19.02.2013
  • Повідомлень: 7 655
    • Репутація: 4983

Re: Бінарне дерево і задачі до нього

Ще можливий дещо складніший варіант з перетворенням дерева на повноцінне iterable (і реалізацією print на його основі).

class MYBTree:
 class Item:
  ...
  def __iter__(self):
    yield from self.left or ()
    yield self.data
    yield from self.right or ()
 ...
 def __iter__(self):
  yield from self.item
 def print(self):
    for i in self:
        print(i)

Що це дає: оскільки дерево тепер iterable, з ним можна робити всі ті штуки, які можна робити зі списком, вектором, рейнджем, рядком і т.д. — напр., передавати як параметр циклу for, або конвертувати в список, або обробляти з допомогою map(), filter() та функцій з itertools, і т.д., і т.п. Втім, це вже виходить за рамки завдання.

Подякували: leofun01, DimONN, koala3

8 Відповідь від DimONN

  • DimONN
  • DimONN
  • Користувач
  • Поза форумом
  • Звідки: Київ
  • Дата реєстрації: 01.02.2018
  • Повідомлень: 44
    • Репутація: 6

Re: Бінарне дерево і задачі до нього

koala написав:
def print(self):
  if self.left:
    self.left.print()
  print(value)
  if self.right:
    self.right.print()

Не можу розібратись як користуватись цією функцією. Можете вписати в мій код? Дякую.

9 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 617
    • Репутація: 13330

Re: Бінарне дерево і задачі до нього

Всередину вашого дерева, звісно.
І так, print(self.value). З телефону не дуже зручно набирати.

koala вебсайт

10 Відповідь від DimONN Востаннє редагувалося DimONN (19.12.2018 12:25:05)

  • DimONN
  • DimONN
  • Користувач
  • Поза форумом
  • Звідки: Київ
  • Дата реєстрації: 01.02.2018
  • Повідомлень: 44
    • Репутація: 6

Re: Бінарне дерево і задачі до нього

# update - друк бінарного дерева

class MyBTree(object):
    class Item(object):
        def __init__(self, data: int):
            self.left = None
            self.right = None
            self.data = data

    def __init__(self):
        self.root = None

    def is_empty(self):
        return self.root is None

    def insert(self, data):
        item = MyBTree.Item(data)
        if not self.root:
            self.root = item
        else:
            current_item = self.root
            while True:
                if current_item.data <= item.data:
                    if current_item.right is None:
                        current_item.right = item
                        return
                    else:
                        current_item = current_item.right
                else:
                    if current_item.left is None:
                        current_item.left = item
                        return
                    else:
                        current_item = current_item.left

    def _print_subtree(self, sub_item: Item):
        """ Comment """
        # 1. Check self.left
        if sub_item.left:
            self._print_subtree(sub_item.left)
        # 2. Print self.data
        print(sub_item.data)
        # 3. Check self.right
        if sub_item.right:
            self._print_subtree(sub_item.right)

    def print(self):
        self._print_subtree(self.root)

і код з друком:

import random

from my_btree import MyBTree as BTree


def fill_tree(btree: BTree):
    for i in range(10):
        data = random.randint(1, 101)
        btree.insert(data)
        print(data)


def main():
    the_tree = BTree()
    print('Fill tree')
    fill_tree(the_tree)
    print('Print tree')
    the_tree.print()
Подякували: koala1