19. Дерева¶
Як і зв'язкові списки, дерева складаються із вузлів. Широко відомо бінарне дерево, кожен вузол якого містить посилання на два інші вузли (або None ). Ці посилання вказують на ліве та праве піддерев'я. Як і вузли зв'язкових списків, вузли дерев також містять корисні дані. Наступна діаграма представляє дерево:
Найвищий вузол дерева називається корінням. Посилання на корінь є посиланням на все дерево. Розвиваючи метафору з деревом, інші вузли називають гілками, а кінцеві вузли, які не мають посилань на інші, листям.
(Можливо, вам здається дивним, що дерево намальоване коренем вгору та листям униз? Але це не найдивніше з того, що пов'язане з деревами.)
Щодо дерев також використовується метафора сім'ї. Тому вузол, що посилається на інші, іноді називають батьківським*, а вузли, на які він посилається дочірніми. Вузли, які мають спільного батька, називають сестринськими.
І, нарешті, говорячи про дерева, користуються словами, що позначають сторони та напрямки. Ми вже згадали ліве та праве піддерев'я, але також є напрямки вгору (до батьків та кореня) та вниз (до дітей та листя). А всі вузли, що знаходяться на однаковій відстанню від кореня, становлять рівень дерево.
Подібно до зв'язкових списків, дерева також є рекурсивними структурами, оскільки їх визначення рекурсивне. Дерево є:
- порожнє дерево, представлене значенням None , або
- вузол, що містить дані та посилання на дерева.
У випадку бінарного дерева вузол містить два посилання.
19.2. Побудова дерев¶
Побудова дерева схожа на побудову зв'язкового списку. Кожен виклик конструктора створює один вузол.
class Tree: def __init__(self, cargo, left=None, right=None): self.cargo = cargo self.left = left self.right = right def __str__(self): return str(self.cargo)
Параметр cargo , що представляє дані, може бути будь-якого типу, а параметри left і right мають бути вузлами дерев. left і right опціональні та мають значення за замовчуванням None .
Щоб вивести на друк вузол, виводитимемо його дані, cargo .
Один із способів збудувати дерево — знизу вгору. Створимо спочатку дочірні вузли:
left = Tree(2) right = Tree(3)
Потім створимо батьківський вузол і зв'яжемо його з дочірніми:
tree = Tree(1, left, right);
Можна записати цей код компактніше:
>>> tree = Tree(1, Tree(2), Tree(3))
В обох випадках ми отримаємо дерево, зображене на малюнку на початку розділу.
19.3. Обхід дерев¶
Щоразу, коли ви зустрічаєтеся з новою структурою даних, перше запитання, яке ви поставили, має бути: як перебрати всі елементи цієї структури? Найбільш природний спосіб обійти дерево, відвідавши всі його вузли – рекурсивний. Наприклад, якщо вузли дерева містять цілі числа як дані, то наступна функція підраховує їх суму:
def total(tree): if tree == None: return 0 return total(tree.left) + total(tree.right) + tree.cargo
Базовий випадок тут порожнє дерево, яке містить даних; для нього повертається 0. На кожному кроці рекурсії робляться два виклики функції total для підрахунку суми дочірніх дерев. До суми результатів рекурсивних викликів додаються батьківські дані та повертається сума.
19.4. Дерева виразів¶
Дерева природно представляють структуру виразів. На відміну з інших способів уявлення, дерево визначає порядок обчислень однозначно. Наприклад, інфікний вираз 1 + 2 * 3 неоднозначно, якщо не взяти до уваги, що множення є пріоритетнішою операцією, ніж додавання.
Дерево на наступному малюнку представляє цей вираз:
Вузлами дерева, що представляє вираз, можуть бути операнди, наприклад, 1 і 2 , та оператори, + , * та інші. Операнди будуть листами, а вузли-оператори будуть посилатися на вузли-операнди.
Можна збудувати це дерево таким чином:
>>> tree = Tree('+', Tree(1), Tree('*', Tree(2), Tree(3)))
При погляді на це дерево не виникає питання про порядок операцій.
Дерева виразів мають численні застосування. Далі в цьому розділі дерева використовуються для того, щоб переводити вирази в постфіксний, префіксний або інфікований запис.
19.5.
Ми можемо обійти дерево виразу і вивести його на друк таким чином:
def print_tree(tree): if tree == None: return print tree.cargo, print_tree(tree.left) print_tree(tree.right)
Як бачите, для виведення дерева на друк ми спочатку виводимо корінь, потім ліве піддерево, потім праве. упорядкованим обходом, або обходом у прямому порядку, тому що батьківський вузол відвідується перед відвідинами дочірніх вузлів.
>>> tree = Tree('+', Tree(1), Tree('*', Tree(2), Tree(3))) >>> print_tree(tree) + 1 * 2 3
Така форма запису виразу відрізняється і від постфіксної, і від інфіксної. префіксною.
Ви, напевно, вже запідозрили, що при обході дерева іншим способом вийде інший запис виразу. Так воно і є.
def print_tree_postorder(tree): if tree == None: return print_tree_postorder(tree.left) print_tree_postorder(tree.right) print tree.cargo,
Результат, 1 2 3 * + , є постфіксним записом! Такий порядок обходу дерева називається поступорядкованим, або обходом у зворотному порядку. Справді, спочатку виводиться листя, наприкінці — корінь.
Зрештою, для виконання симетричного обходу потрібно спочатку вивести ліве піддерево, потім його батька, а потім праве дерево:
def print_tree_inorder(tree): if tree == None: return print_tree_inorder(tree.left) print tree.cargo, print_tree_inorder(tree.right)
Отримай інфіксний запис виразу: 1 + 2 * 3 .
Якщо бути до кінця чесними, треба сказати, що ми допустили суттєве спрощення. Іноді для запису інфіксних виразів потрібно використовувати дужки, щоб зберегти порядок виконання операцій. Тому симетричний обхід не завжди достатній для створення повноцінного інфікного виразу.
Тим не менш, після деякої доопрацювання, дерево виразів та його обхід різними способами надають засоби для перекладу виразів з однієї форми до іншої.
Якщо в процесі симетричного обходу дерева ми стежитимемо за тим, на якому рівні дерева знаходимося, ми зможемо отримати графічне уявлення дерева:
def print_tree_indented(tree, level=0): if tree == None: return print_tree_indented(tree.right, level+1) print ' ' * level + str(tree.cargo) print_tree_indented(tree.left, level+1)
Параметр level (англ. рівень) повідомляє нам, на якому рівні дерева ми знаходимося. Спочатку він дорівнює 0. Щоразу, коли ми робимо рекурсивний виклик, ми передаємо level+1 як параметр, оскільки рівень дочірнього вузла завжди на 1 більше, ніж рівень батьківського. Дані вузла при виведенні на друк зсуваються вправо пропорційно до рівня. Отримуємо таке:
>>> print_tree_indented(tree) 3 * 2 + 1
Якщо подивитись отриманий висновок збоку, можна побачити подібність дерева, зображеного на малюнку вище.
19.6. Побудова дерева виразу¶
У цьому розділі ми виконаємо розбір інфіксних виразів і побудуємо відповідні дерева. Наприклад, вираз (3 + 7) * 9 дасть нам наступне дерево:
Ми спростили малюнок, опустивши імена атрибутів.
Синтаксичний аналізатор, або парсер, який ми напишемо, буде працювати з виразами, що включають числа, дужки та оператори + і * . Виходитимемо з припущення, що вихідний вираз вже розбитий на лексеми, які поміщені в список Python (отримайте цей список самі як вправу). Список лексем для вираження (3 + 7) * 9 наступний:
Лексема end грає роль обмежувача списку, запобігаючи виходу парсера за його кордон.
Перша функція, яку ми напишемо, це функція get_token , що приймає як параметри список лексем і очікувану лексему. Функція порівнює очікувану лексему з першою у списку. Якщо вони рівні, лексема видаляється зі списку, та функція повертає True . В іншому випадку повертається False :
def get_token(token_list, expected): if token_list[0] == expected: del token_list[0] return True else: return False
Бо змінна token_list посилається на об'єкт, що змінюється, зроблені в функції зміни доступні через будь-яку змінну, що посилається на той же об'єкт.
Наступна функція, get_number працює з операндами. Якщо наступна лексема у списку token_list є числом, то get_number видаляє її зі списку та повертає вузол, що містить це число. В іншому випадку повертається None .
def get_number(token_list): x = token_list[0] if type(x) != type(0): return None del token_list[0] return Tree(x, None, None)
Перед тим, як йти далі, варто протестувати функцію get_number . Надамо список чисел змінної. token_list , Викликаємо get_number і виведемо на друк результат, а також те, що залишилося в token_list :
>>> token_list = [9, 11, 'end'] >>> x = get_number(token_list) >>> print_tree_postorder(x) 9 >>> print token_list [11, 'end']
Наступна потрібна нам функція, це get_product (англ.: отримати твір), яка будує дерево для твору. 3 * 7 .
Ось версія get_product для найпростіших творів.
def get_product(token_list): a = get_number(token_list) if get_token(token_list, '*'): b = get_number(token_list) return Tree ('*', a, b) else: return a
Припускаючи, що get_number повертає вузол з першим операндом, привласнюємо його змінною a . Якщо наступна лексема. * , то одержуємо другий операнд і будуємо дерево вираження за допомогою a , b та оператора твору.
Якщо ж наступна лексема не * , то повертаємо вузол-лист першого операнда, a . Наведемо два приклади:
>>> token_list = [9, '*', 11, 'end'] >>> tree = get_product(token_list) >>> print_tree_postorder(tree) 9 11 *
>>> token_list = [9, '+', 11, 'end'] >>> tree = get_product(token_list) >>> print_tree_postorder(tree) 9
Як видно з другого прикладу, єдиний операнд розглядається як свого роду твір.
А тепер візьмемо складніший твір, наприклад, 3 * 5 * 13 . Цей вираз можна розглядати як добуток творів, а саме: 3 * (5 * 13) . Отримуємо наступне дерево:
Трохи доопрацювавши get_product , ми зможемо мати справу з творами довільної довжини:
def get_product(token_list): a = get_number(token_list) if get_token(token_list, '*'): b = get_product(token_list) # this line changed return Tree('*', a, b) else: return a
Іншими словами, твір може бути або деревом з єдиним вузлом, або деревом з коренем * , дочірнім вузлом-операндом зліва та дочірнім вузлом-твором праворуч. Рекурсивні визначення, подібні до цього, вже повинні здаватися вам звичними.
Протестуємо нову версію функції зі складним твором:
>>> token_list = [2, '*', 3, '*', 5 , '*', 7, 'end'] >>> tree = get_product(token_list) >>> print_tree_postorder(tree) 2 3 5 7 * * *
А тепер реалізуємо синтаксичний розбір сум. І знову скористаємося дещо несподіваним визначенням. Сума для нас чи дерево з коренем + , дочірнім вузлом-твором зліва і дочірнім вузлом-сумою справа, або дерево з єдиним вузлом-твором.
Якщо ви придивитеся до цього визначення уважніше, то виявите чудову властивість: ми можемо уявити будь-який вираз без дужок як суму творів. На цій властивості ґрунтується наш алгоритм синтаксичного аналізу.
Функція get_sum намагається побудувати дерево з дочірнім вузлом-твором зліва і дочірнім вузлом-сумою справа. Але якщо функція не виявляє + вона просто повертає твір.
def get_sum(token_list): a = get_product(token_list) if get_token(token_list, '+'): b = get_sum(token_list) return Tree('+', a, b) else: return a
Протестуємо функцію з виразом 9 * 11 + 5 * 7 :
>>> token_list = [9, '*', 11, '+', 5, '*', 7, 'end'] >>> tree = get_sum(token_list) >>> print_tree_postorder(tree) 9 11 * 5 7 * +
Ми майже закінчили, залишилося лише навчитися працювати зі дужками. У будь-якому місці виразу, де може бути число, може бути сума, укладена в дужки. Змінимо get_number так, щоб обробляти підвираження:
def get_number(token_list): if get_token(token_list, '('): x = get_sum(token_list) # get the subexpression get_token(token_list, ')') # remove the closing parenthesis return x else: x = token_list[0] if type(x) != type(0): return None token_list[0:1] = [] return Tree(x, None, None)
Протестуємо цей код із виразом 9 * (11 + 5) * 7 :
>>> token_list = [9, '*', '(', 11, '+', 5, ')', '*', 7, 'end'] >>> tree = get_sum(token_list) >>> print_tree_postorder(tree) 9 11 5 + 7 * *
Наш парсер обробив дужки коректно, додавання виконується перед множенням.
Фінальна версія get_number було б непогано дати інше ім'я, що краще описує її функціональність.
19.7. Обробка помилок¶
Досі під час розробки парсера ми вважали, що у вхід надходять коректні висловлювання. Наприклад, коли ми досягаємо кінця подвыражения, ми вважаємо, що наступною лексемою буде дужка, що закриває. Однак, якщо це не так, програма має впоратися із ситуацією.
def get_number(token_list): if get_token(token_list, '('): x = get_sum(token_list) if not get_token(token_list, ')'): raise 'BadExpressionError', 'missing parenthesis' return x else: # the rest of the function omitted
Пропозиція raise створює виняток; в даному випадку ми створюємо новий вид виключення з ім'ям BadExpressionError . Якщо функція, що викликала get_number , або інша функція в поточному стеку дзвінків обробляє цей виняток, програма зможе продовжити роботу. Інакше Python виведе повідомлення про помилку та завершиться.
19.8. Дерево тварин¶
У цьому розділі ми розробимо невелику програму, яка використовує дерево для створення бази знань.
Програма, взаємодіючи з користувачем, створює дерево питань та назв тварин. Ось приклад виконання цієї програми:
Are you thinking of an animal? y Is it a bird? n What is the animal's name? dog What question would distinguish a dog from a bird? Can it fly If the animal були dog the answer would be? n Are you thinking of an animal? y Can it fly? n Is it a dog? n What is the animal's name? cat What question would distinguish a cat from a dog? Does it bark If the animal were cat the answer would be? n Are you thinking of an animal? y Can it fly? n Does it bark? y Is it a dog? y I rule! Are you thinking of an animal? n
Ось дерево, яке будує цей діалог:
Кожне опитування програма починає з кореня дерева, і задає питання, що міститься в ньому. Залежно від відповіді програма переходить до лівого або правого дочірнього вузла і ставить запитання, що міститься в цьому вузлі. І так далі, поки не буде досягнуто кінцевого вузол-аркуша. Тоді програма висловлює здогад. Якщо ця здогад не вірна, програма просить користувача ввести назву нової тварини та питання, яке дозволить відрізнити цю тварину від тварини, запропонованої програмою. Потім до дерева додається новий вузол з питанням та назвою тварини, введеними користувачем.
def yes(ques): ans = raw_input(ques).lower() return ans[0] == 'y' def animal(): # start with a singleton root = Tree("bird") # loop until the user quits while True: print if not yes("Are you thinking of an animal? "): break # walk the tree tree = root while tree.left != None: prompt = tree.cargo + "? " if yes(prompt): tree = tree.right else: tree = tree.left # make a guess guess = tree.cargo prompt = "Is it a" + guess + "? " if yes(prompt): print "I rule!" continue # get new information prompt = "What is the animal's name? " animal = raw_input(prompt) prompt = "What question would distinguish a %s from a %s? " question = raw_input(prompt % (animal, guess)) # add new information to the tree tree.cargo = question prompt = "If the animal were %s the answer would be? " if yes(prompt % animal): tree.left = Tree(guess) tree.right = Tree(animal) else: tree.left = Tree(animal) tree.right = Tree(guess)
Допоміжна функція yes друкує запрошення та приймає введення користувача. Якщо відповідь користувача починається з y або Y, то функція повертає True .
Умовою зовнішнього циклу функції animal є True . Це означає, що цикл триватиме доти, доки не виконається пропозиція break (у разі, коли користувач не задумав тварину).
У внутрішньому циклі while відбувається переміщення по дереву від кореня до листя, кероване відповідями користувача.
Коли до дерева додається новий вузол, поточний вузол отримує нове питання і два дочірні вузли: один з новою твариною і один з оригінальним (початковим) питанням.
Недоліком цієї програми є те, що коли вона завершується, вона забуває про все, чого ви її навчили! Вирішіть цю проблему як вправу.
19.9. Глосарій¶
Бінарний оператор Оператор, який вимагає два операнди. бінарне дерево Дерево, кожен вузол якого посилається на нуль, один або два дочірні вузли. дочірній вузол дерева Вузол, який посилається батьківський вузол. Вузол дерева, що не має батьківського. Вузол дерева, що не має дочірніх вузлів. вираз у дужках, що розглядається як операнд об'ємного виразу. Спосіб обходу дерева, при якому кожен вузол відвідується перед відвідуванням його дочірніх вузлів.префіксний запис Спосіб запису математичного виразу, при якому оператор передує операндам. Спосіб обходу дерева, при якому кожен вузол відвідується після відвідування його дочірніх вузлів. батьківський вузол дерева Вузол, що посилається на інші (дочірні) вузли. сестринські вузли дерева Вузли, що мають спільний батьківський вузол. симетричний обхід дерева Спосіб обходу дерева, при якому для кожного вузла спочатку відвідується лівий дочірній вузол потім сам цей вузол, потім правий дочірній вузол. Безліч вузлів, рівновіддалених від кореня.
19.10. Вправи¶
- Змініть функцію print_tree_inorder так, щоб вона ставила дужки навколо кожного оператора з кількома операндами. Чи працює вона коректно та однозначно? Чи завжди потрібні дужки?
- Напишіть лексичний аналізатор, тобто функцію, яка приймає рядок з виразом і повертає список лексем.
- Знайдіть ще місця у функціях, що працюють з деревом виразу, де можуть виникнути помилки, та додайте відповідні пропозиції raise . Протестуйте ваш код із некоректними виразами.
- Придумайте різні способи збереження дерева тварин у файлі. Реалізуйте той, який вважаєте найпростішим.
Структури даних: що таке дерева?
Найбільш простою та зрозумілою структурою даних є звичайний масив. З тим, як улаштовані масиви, рідко виникають питання. Чого не можна сказати про таку структуру даних, як дерева. Пропонуємо розібратися з деревами – нелінійною структурою, де дані впорядковуються ієрархічно.
Трохи про ієрархію
Мабуть, одним із прикладів ієрархій, з яким багато хто стикається щодня, є каталоги в операційній системі.У вашому комп'ютері завжди є кореневий каталог, будь то кореневий каталог на Linux або, наприклад, локальний диск на Windows. У кожному з цих кореневих каталогів знаходяться папки, всередині яких так само є папки, всередині яких також можуть бути папки, таким чином це може тривати практично до нескінченності. Хоча так було не завжди, і довжина шляху до Windows за умовчанням обмежена 260 символами. Приклад каталогу можна побачити на зображенні нижче.
Приклавши трішки уяви в цій картинці, дійсно можна побачити перевернене дерево.
Приклад каталогу
Як же влаштовані дерева?
Розглянемо основні елементи дерева з прикладу картинки вище.
Дерево є набір об'єктів, званих вузлами. Кожен вузол містить значення чи дані, і може мати чи мати дочірній вузол. Вузли, які не мають дочірніх вузлів називаються листям.
На картинці вузлами є всі представлені папки, при цьому листям є тільки ті, всередині яких немає папок, наприклад lib, disc, mail, X11 і т.д. п.
Усі вузли дерев з'єднані ребрами, ребра показують зв'язок між вузлами.
На прикладі з картинки, за допомогою ребер ми можемо ходити каталогами і розуміти, що знаходиться всередині кожної папки. Також від кожної папки по ребра можна повернутися до кореня.
На вершині дерева знаходиться корінь - такий вузол, який не має батьківських вузлів, але при цьому є один або більше дочірніх вузлів.
У нашому випадку коренем є каталог "/".
Основні елементи дерева
Чи може виникнути питання, чому ж корінь знаходиться на вершині? Відповідь проста: ми – програмісти, ми так бачимо 🙂
Характеристики дерева
Є дві важливі характеристики дерева, які потрібно знати під час роботи з ним:
Висота дерева – це довжина найдовшого шляху до листа.Глибина вузла – це відстань від вузла до його кореня.
Для дерева, представленого вище, висота дерева дорівнюватиме трьом. Глибина вузла, наприклад «local» дорівнюватиме двом.
У чому перевага дерев?
Перевага дерев у тому, що, незважаючи на відносну складність їхнього формування, всі операції з ними є дуже простими. Так, наприклад, операції вставки, видалення та пошуку елементів у дереві виконуються в тисячі, а то й десятки тисяч разів швидше за аналогічні операції з невпорядкованим масивом. Точнішими цифрами по кожному виду дерев поділимося в наступних матеріалах.
А що взагалі робити із деревами?
Області застосування дерев дуже широкі і різноманітні, причому не тільки в програмуванні. У більшості випадків саме завдяки використанню деревоподібних структур вдається значно прискорити роботу з даними, і в багатьох базах даних рішення, що базуються на їх застосуванні, успішно використовуються.
Ще більше корисностей про дерева ми розповімо в наступних статтях!
Уроки 77 - 79
Дерева. Основні поняття
(§ 43. Дерева)
Як ви знаєте з підручника 10 класу, дерево - це структура, що відображає ієрархію (відносини підпорядкованості, багаторівневі зв'язки). Нагадаємо, деякі основні поняття, пов'язані з деревами.
Дерево складається з вузлів та зв'язків між ними (вони називаються дугами). Найперший вузол, розташований на верхньому рівні (до нього не входить жодна стрілка-дуга), - це корінь дерева. Кінцеві вузли, з яких не виходить жодна дуга, називаються листям. Всі інші вузли, крім кореня та листя, – це проміжні вузли.
З двох пов'язаних вузлів той, що знаходиться на вищому рівні, називається батьком, а інший сином. Корінь - це єдиний вузол, який не має батька; у листя немає синів.
Використовуються також поняття «предок» та «нащадок». Нащадок якогось вузла - це вузол, в який можна перейти за стрілками від вузла-предка. Відповідно, предок якогось вузла - це вузол, з якого можна перейти за стрілками в даний вузол.
У дереві на рис. 6.11 Батько вузла Е - це вузол В, а предки вузла Е - це вузли А і В, для яких вузол Е - нащадок. Нащадками вузла А (кореня дерева) є решта вузлів.
Висота дерева - це найбільша відстань (кількість дуг) від кореня до листа.
Висота дерева, наведеного на рис. 6.11, дорівнює 2.
Мал. 6.11
Формально дерево можна визначити так:
1) порожня структура - це дерево;
2) дерево - це корінь і кілька пов'язаних з ним окремих (не пов'язаних між собою) дерев.
Тут безліч об'єктів (дерев) визначається через саме це безліч на основі простого базового випадку (порожнього дерева). Такий прийом називається рекурсією (див. Розділ 8 підручника для 10 класу). Відповідно до цього визначення, дерево – це рекурсивна структура даних. Тому очікується, що з роботі з деревами будуть корисні рекурсивні алгоритми.
Найчастіше в інформатиці використовуються двійкові (або бінарні) дерева, тобто такі, в яких кожен вузол має не більше двох синів. Їх також можна визначити рекурсивно.
Двійкове дерево:
1) порожня структура - це двійкове дерево;
2) двійкове дерево - це корінь і два пов'язані з ним окремі двійкові дерева (ліве і праве піддерева).
Дерева широко застосовуються у наступних задачах:
• пошук у великому масиві даних, що не змінюються;
• сортування даних;
• обчислення арифметичних виразів;
• оптимальне кодування даних (метод стиснення Хаффмана).
Завантажити матеріали уроку
