19. Дървета¶
19.1. Запознайте се с дървото¶
Подобно на свързаните списъци, дърветата са съставени от възли. Добре известнодвоично дърво, всеки възел на което съдържа връзки към два други възела (или Нито един). Тези връзки сочат към ляво и дясно поддървета. Подобно на свързаните списъчни възли, дървовидните възли също съдържат полезни данни. Следната диаграма представя дървото:
(Може би смятате, че е странно едно дърво да е изтеглено с корена нагоре и листата надолу? Но това не е най-странното нещо при дърветата.)
Дърветата се използват и като семейна метафора. Следователно възел, който препраща към други, понякога се наричародител*, а възлите, към които препраща, се наричат деца. Възлите, които имат общ родител, се наричат братя и сестри.
И накрая, когато говорят за дървета, те използват думи, обозначаващи страни и посоки. Вече споменахме леви и десни поддървета, но има и посоки нагоре (към родители и корен) и надолу (към деца и листа). И всички възли, които са на еднакво разстояние от корена, съставляватнивото на дървото.
Подобно на свързаните списъци, дърветата също са рекурсивни структури, защото тяхната дефиниция е рекурсивна. Дървото е:
- празното дърво, представено от стойността Няма, или
- възел, съдържащ данни и връзки към дървета.
В случай на двоично дърво, възелът съдържа две връзки.
19.2. Изграждане на дървета¶
Изграждането на дърво е подобно на изграждането на свързан списък. Всяко извикване на конструктор създава един възел.
Товарният параметър, представляващ данните, може да бъде от всякакъв тип, а левият и десният параметри трябва да са дървовидни възли. ляво и дясно не са задължителни и по подразбиране са Няма.
За да отпечатате възел,ще изведем неговите данни, cargo .
Един от начините за изграждане на дърво е отдолу нагоре. Нека първо създадем дъщерните възли:
След това създаваме родителски възел и го свързваме с децата:
Можете да напишете този код по-компактно:
И в двата случая ще получим дървото, показано на фигурата в началото на главата.
19.3. Обхождане на дърво¶
Всеки път, когато срещнете нова структура от данни, първият въпрос, който задавате, трябва да бъде: как да преминете през всички елементи на тази структура? Най-естественият начин за обхождане на дърво чрез посещение на всички негови възли е рекурсивен. Например, ако възлите на дървото съдържат цели числа като данни, тогава следната функция изчислява тяхната сума:
Основният случай тук е празно дърво, което не съдържа данни; връща 0. На всяка стъпка от рекурсията се правят две извиквания към общата функция, за да се изчисли сумата от дъщерните дървета. Родителските данни се добавят към сумата от резултатите от рекурсивните извиквания и сумата се връща.
19.4. Изразни дървета¶
Дърветата естествено представляват структурата на изразите. За разлика от други представяния, дървото описва реда на изчисленията недвусмислено. Например, инфиксният израз 1 + 2 * 3 е двусмислен, освен ако не вземете предвид, че умножението има предимство пред събирането.
Дървото на следващата фигура представлява този израз:
Възлите на дървото, представляващи израз, могат да бъдат операнди, като 1 и 2, и оператори, +, * и други. Операндите ще бъдат листа, а операторните възли ще се отнасят до операндните възли. (Всички оператори, които използваме, са двоични, т.е. имат точно два операнда.)
Можете да изградите това дърво по следния начин:
Когато гледате това дърво, няма въпрос заред на операциите. Първо се извършва умножение, за да се изчисли вторият операнд за събиране, а след това се извършва събиране.
Изразните дървета имат много приложения. Дърветата се използват по-късно в тази глава за превод на изрази в постфиксна, префиксна или инфиксна нотация. Подобни дървета се използват вътрешно от компилаторите за анализиране, оптимизиране и превод на програми.
19.5. Преминаване през дървото на израза¶
Можем да преминем през дървото на израза и да го отпечатаме по следния начин:
Както можете да видите, за да отпечатаме дърво, първо отпечатваме корена, след това лявото поддърво, след това дясното. Този вид обхождане на дървото се наричапредварително подредено обхождане или директно обхождане, защото родителският възел се посещава преди да бъдат посетени дъщерните възли. Нека отпечатаме нашето дърво:
Тази форма на писане на израз се различава както от постфикса, така и от инфикса. Нотация, в която операторите предхождат операндите, се наричапрефикс.
Вероятно вече сте подозирали, че ако прекосите дървото по различен начин, ще получите различен запис на израза. Такъв, какъвто е. Например, ще отпечатаме поддървета преди техния родител:
Резултатът, 1 2 3 * + , е постфиксна нотация! Този ред на обхождане на дървото се наричапостподреден или обратно обхождане. Всъщност първо се появяват листата, а накрая коренът.
И накрая, за да извършитесиметрично обхождане, първо отпечатайте лявото поддърво, след това неговия родител и след това дясното дърво:
Получаваме инфиксната нотация на израза: 1 + 2 * 3 .
За да бъдем напълно честни, трябва да кажем, че сме направили значително опростяване. Понякога трябва да използвате скоби, за да напишете инфикс изрази,да спазва реда на операциите. Следователно симетричното преминаване не винаги е достатъчно за генериране на пълноценен инфикс израз.
Въпреки това, с известно усъвършенстване, дървото на изразите и неговото преминаване по различни начини осигуряват средства за превод на изрази от една форма в друга.
Ако следим къде се намираме в дървото, докато обикаляме дървото симетрично, можем да получим графично представяне на дървото:
Параметърът ниво ни казва на какво ниво от дървото се намираме. Първоначално е 0. Всеки път, когато правим рекурсивно извикване, ние предаваме ниво+1 като параметър, тъй като нивото на дъщерния възел винаги е с 1 повече от нивото на родителя. Данните за възела се изместват надясно пропорционално на нивото при отпечатване. Получаваме следното:
Ако погледнете получения резултат отстрани, можете да видите сходство на дървото, показано на фигурата по-горе.
19.6. Изграждане на изразно дърво¶
В този раздел ще анализираме инфикс изрази и ще изградим съответните им дървета. Например изразът (3 + 7) * 9 ще ни даде следното дърво:
Опростихме чертежа, като пропуснахме имената на атрибутите.
Парсерът илипарсер, който ще напишем, ще работи с изрази, които включват числа, скоби и операторите + и *. Нека започнем с предположението, че оригиналният израз вече е токенизиран и поставен в списък на Python (вземете този списък сами като упражнение). Списъкът с токени за израза (3 + 7) * 9 е както следва:
Крайната лексема действа като разделител на списъка, предотвратявайки излизането на парсера извън границите му.
Първата функция, която ще напишем, е функцията get_token, която приема като параметрисписък с токени и очаквания токен. Функцията сравнява очаквания токен с първия в списъка. Ако са равни, токенът се премахва от списъка и функцията връща True. В противен случай се връща False:
Тъй като променливата token_list се отнася до променлив обект, промените, направени във функцията, са достъпни чрез всяка променлива, която се отнася до същия обект.
Следващата функция, get_number, работи с операнди. Ако следващият токен в token_list е число, get_number го премахва от списъка и връща възела, съдържащ този номер. В противен случай се връща None.
Преди да продължите, струва си да тествате функцията get_number. Присвоете списък с числа на променливата token_list, извикайте get_number и отпечатайте резултата и това, което остава в token_list:
Следващата функция, от която се нуждаем, е get_product, която изгражда дърво за продукта. Един прост продукт има две числа като операнди, като например 3 * 7 .
Ето версията на get_product за прости продукти.
Ако приемем, че get_number връща възела с първия операнд, ние го присвояваме на . Ако следващият токен е *, тогава получаваме втория операнд и изграждаме дърво на изрази, използвайки a, b и оператора product.
Ако следващият токен не е *, тогава върнете листовия възел на първия операнд, a. Ето два примера:
Както можете да видите от втория пример, единичният операнд се третира като вид продукт. Въпреки че изглежда необичайно, тази техника се оказва полезна.
А сега нека вземем по-сложен продукт, например 3 * 5 * 13 . Този израз може да се разглежда като произведение на продуктите, а именно: 3 * (5 * 13) . Получаваме следното дърво:
С малко коригиране на get_product можем да се справим с продукти с произволна дължина:
С други думи, продуктът може да бъде или дърво с един възел, или дърво, вкоренено от *, с дъщерен операнд отляво и дъщерен продукт отдясно. Рекурсивни дефиниции като тази би трябвало да са ви познати досега.
Нека тестваме новата версия на функцията със сложен продукт:
И сега прилагаме анализирането на суми. Отново използваме малко неочаквано определение. Сумата за нас е или дърво с корен +, възел дъщерен продукт отляво и възел дъщерен сбор отдясно, или дърво с един възел продукт.
Ако погледнете по-отблизо това определение, ще откриете едно забележително свойство: можем да представим всеки израз без скоби като сбор от продукти. Това свойство е в основата на нашия алгоритъм за анализ.
Функцията get_sum се опитва да изгради дърво с дете продукт отляво и дете сума отдясно. Но ако функцията не намери +, тя просто връща продукта.
Нека тестваме функцията с израза 9 * 11 + 5 * 7 :
Почти сме готови, остава само да се научим да работим със скоби. Навсякъде в израз, който може да бъде число, може да има и сума, оградена в скоби. Нека променим get_number да обработваподизрази :
Нека тестваме този код с израза 9 * (11 + 5) * 7 :
Нашият анализатор се справи правилно със скобите, събирането се извършва преди умножението.
Би било хубаво да се даде различно име на крайната версия на get_number, за да се опише по-добре неговата функционалност.
19.7. Обработка на грешка¶
Досега, когато разработвахме анализатор, предполагахме, че правилните изрази са получени като вход.Например, когато стигнем до края на подизраз, приемаме, че следващият токен ще бъде затварящата скоба. Ако обаче това не е така, програмата трябва да се справи със ситуацията.
Клаузата за повишаване хвърля изключение; в този случай създаваме нов вид изключение, наречено BadExpressionError. Ако функцията, която е извикала get_number или друга функция от текущия стек за извикване, обработва това изключение, тогава програмата може да продължи. В противен случай Python ще отпечата съобщение за грешка и ще излезе.
19.8. Животинско дърво¶
В този раздел ще разработим малка програма, която използва дърво за изграждане на база от знания.
Програмата, взаимодействайки с потребителя, създава дърво от въпроси и имена на животни. Ето пример за стартиране на тази програма:
Ето дървото, което изгражда този диалогов прозорец:
Програмата започва всяко проучване от корена на дървото и задава въпроса, съдържащ се в него. В зависимост от отговора, програмата прескача към левия или десния дъщерен възел и задава въпроса, съдържащ се в този възел. И така нататък, докато се достигне листовия възел. След това програмата прави предположение. Ако това предположение е грешно, програмата иска от потребителя да въведе името на новото животно и въпрос, който ще разграничи това животно от животното, предложено от програмата. След това към дървото се добавя нов възел с въпроса и името на животното, въведени от потребителя.
Ето програмния код:
Помощната функция yes отпечатва подкана и приема въвеждане от потребителя. Ако отговорът на потребителя започва с y или Y, тогава функцията връща True.
Условието на външния цикъл във функцията животно е True. Това означава, че цикълът ще продължи, докато операторът break не бъде изпълнен (в случай, когатопотребителят не е заченал животното).
Вътрешният цикъл while преминава през дървото от корена до листата, движен от отговорите на потребителя.
Когато към дървото се добави нов възел, текущият възел получава нов въпрос и два дъщерни възела: един с новото животно и един с оригиналния (оригинален) въпрос.
Недостатъкът на тази програма е, че като спре, забравя всичко, което сте я научили! Решете този проблем като упражнение.