двоични дървета
Цел: Да се разследва ефективно методи за съхранение и обработка на информация от примерните двоични дървета.
Преглед
Binary Tree - динамичен йерархична структура данни, състояща се от възли и дъги, които ги свързват. Във всеки възел, с изключение на един, е точно една дъга. Това едно цяло, се нарича корен на дървото. Всяко дърво възел е свързан определен брой отделни дървета, наречени поддървета. Фигурата показва дърво, чиито възли са символи: Y върхове разположени директно под горната X, наречен директно дете X, X и връх се нарича предшественик на Y. Ако възловата точка все още няма потомство, той се нарича лист, ако има, то се нарича вътрешен връх , Например, връх D, Е са преки потомци на връх В; връх Н, I, J са листата. Очевидно е, че връзките са необходими, за да опише дървото. Ще опишем двоично дърво като тип структура на записите, включващ най-малко два полета - указатели на ляво и дясно поддърво, и поле за данни, като цяло число тип: Основни операции на дървото до основни операции над дърветата, включват: • т влизане в дървото; • пресичане на дървото; • премахване на елемент от дървото.
Поставете елемент в дървото. дърво, чиито елементи са вход за създаване и дисплей и клавиатура са неразделна тип. И за всеки връх в дървото върховете всичко ляво трябва да бъде броят на по-малки, но в правото повече от броя, който се съхранява в горната част. Такова дърво се нарича търсене дърво. Нека да се опише процедурата за поставяне на дърво нов връх. При вкарване на върха се вмъква в дървото или поддървото като съществуващата горната или като един възел на дървото. Ето защо, както отляво, така и отдясно връзка нов връх трябва да бъде равна на нула. Когато дървото е празна, стойността предава под формата на референтния параметър е равен на нула. В този случай, вие трябва да го промените така, че да сочи към новия възел, който се добавя, както е в основата. Когато поставите втория елемент предава от основната програма анод опция вече няма да е равен на нула, и че е необходимо да се реши дали в поддърво е необходимо да се въведе нов връх. Производството на дървени елементи. Опишете процеса на изходните стойности на елементите на двоично дърво на екрана. За да направите това, вие трябва да направите пълно обхождане на дървото. Преминаващи дървото отделни негови върхове са посетили в определен ред. Изходна двоично дърво може да се извършва рекурсивно, изпълнявайки за всеки връх на три: • От номера на продукцията, която се съхранява в възел; • байпас наляво-дървото; • заобикаляйки дясното-дървото. Редът на изпълнение на тези действия определя как прекосява. методи за заобикаляне: • байпас линия (отгоре надолу); • базирана байпас (отляво надясно); • заобикаляйки обратната (отдолу нагоре). симетрична процедура изход дърво е, както следва: Премахване на дърво. Непосредствената отстраняването на даден елемент от подредено дърво се реализира само, ако този възел е най-добрата: или тя идва от само един ръб: Вие трябва да промените връзката в предишните върхове. Ако отстранен от върха оставя два клона, трябва да се намери правилният върха на дървото, което може да бъде поставена на мястото си подвижна отгоре. В този случай, записът да се премахнат трябва да се смени или на най-десния елемент на лявото му поддърво, или на най-левия елемент от правото му поддърво. Тези елементи могат да имат повече от един наследник. Нека следната структура се определя: Спомагателен рутинна Del прави само в третия случай. Това "надолу" по дясната клон на лявата поддървото на отстранения възел Q ^ и след това се замества данни (полеви данни) в съответните стойности на р ^ дясната възел R ^ на лявата поддървото, и след това от R ^ може да избяга. На фигура даден първоначален дървото (а), които последователно се премахва възли със стойности на 13, 15, 5, 10. Получените дървета са показани на Фиг. б - д.
Тестовите въпроси
1. Какво е рекурсивен алгоритъм? 2. Какви са частите изградени определение на рекурсивен алгоритъм? 3. Какво е необходимо във всеки рекурсивен алгоритъм? 4. Възможно ли е да се замени рекурсия итерация? Възможно ли е да се замени итерация рекурсия? 5. Какъв е принципът на динамичната структура на "дървото"? 6. Списък на сходствата и различията на динамични структури като "линеен списък", "стек", "дърво". 7. Списък на структурите, които могат да бъдат представени под формата на дърво, които се случват в ежедневието. 8. Завършете изречението: "Списък - едно дърво, което ...".
През всички тези проблеми, подразбиращи двоични дървета poiska.1. Напишете рекурсивна числова функция, което има значение размера на дървени елементи. 2. Напишете функция, която намира най-големият елемент на дървото. 3. Напишете функция, която намира най-малкият елемент на дървото. 4. Напишете процедура, която премахва дървото четните елементи. 5. Напишете рекурсивна процедура, която определя броя на повторения на конкретен елемент в дървото. 6. Напишете рекурсивна процедура, която отпечатва елементите на всички листата на дървото. 7. Напиши процедура, която показва едно дърво, показваща дълбочината на вдлъбнатината на възли от левия край на екрана. Например, дърво ще бъдат показани, както следва: Група 1 Група 2 1 разбира PMI група 2 3 4 група разбира 8. Добави рекурсивна функция, който определя дълбочината на определен елемент от дърво и се връща -1 ако такъв елемент. 9. Напишете рутинна, че отпечатъци (еднократно) всички на върха на дървото. 10. Напиши процедура, която, предвид н брои всички възли на дълбочина н в определения дървото. 11. Напиши рутина, която намира дълбочината на дървото. 12. Филтър масив А чрез включване в дърво на елементи и копие сортирани данни обратно към А. 13. Предвид последователност от думи. За определяне на честотата на възникване на всяка дума в последователността. Забележка. За решаване на проблема всяка дума се погледна нагоре в дървото, което е първоначално празна. Ако не се намери думата, броят на неговите събития се увеличава по един, ако не, думата е включена в дървото с един брояч стойност. Начало
Свързани статии