Позоваването. 15
Масивите и свързани списъци определят колекция от предмети, които са достъпни последователно. Такава структура данни, наречена линейна (линейни) списъци, тъй като те имат уникални първия и последния елементи и всеки вътрешен елемент, има само един наследник. Линеен списък е абстракция, която позволява да се манипулират данните, отчетени по различни начини - масиви, стекове, опашки и свързани списъци.
В много приложения се установи, нелинейна ред на обектите, в които елементите могат да имат няколко наследници. Така например, в родословното дърво, родителят може да има няколко деца (деца). Фиг. 1 показва три поколения на семейството. Тази подредба се нарича наслояване.
В тази статия ще разгледаме нелинейна структура, наречена дърво (дърво), който се състои от възли и клонове и е с посока от корените към външни възли, наречени листа. Тези структури са подобни на комуникационната мрежа, показана на фиг. 2, изискват специални алгоритми и се използват в специални приложения.
дървовидна структура се характеризира с множество възли (възли), с произход от един първоначален възел нарича корен (корен). Фиг. 3 е корен възловата точка А. По отношение на родословно дърво възлова точка може да се разглежда като родител (изходен), което показва, 0, 1 или повече възли, наречени синове (деца). Например, възловата точка В е синове майки Е и F. майка възел Н - възел Г. дървото може да бъде семейството няколко поколения. възли синове и синовете си и синовете си, се наричат потомци (низходящи), както и родители и прародители - предците (предци) на възела. Например, възли Е, F, I, J - потомци на възел В. Всеки не-корен възел има само един родител, и всеки родител има 0 или повече сина. Възелът е без деца (Е, G, Н, I, J), наречена листа (листа).
Всеки възел на дървото е корен на поддърво (поддърво), което се определя от даден възел и всички потомци на този възел. F е корен възел на поддърво съдържащ възли F, I и J. Възелът G е корен на поддърво, без потомство. Това определение предполага, че възловата точка А е корен на поддървото, която се е дърво.
Преходът от възела майка за детето и на другите потомци извършва по пътя (път). Например, на фиг. 4. път от корена на възловата точка F простира от А до В и от В до F. Фактът, че всеки не-корен възел има един родител, гарантира, че има уникален път от всеки възел на децата си. Дължината на пътя от корена до този възел има ниво на възел. корен ниво е равно на 0. Всяка дете на корен възел е ниво 1, следващото поколение - възли 2 ниво, и т.н. Например, на фиг. 4 е възел на възел F 2 ниво 2 с дължина на пътя.
Дълбочина (дълбочина) на дървото е максималното си ниво. дълбочина концепция също може да бъде описан от гледна точка на пътя. Дълбочината на дървото е дължината на най-дългия път от корена до възела.
Фигура 4 на дълбочината на дървото е 3.
Фигура 4. ниво възел и дължината на пътя
Въпреки че общата форма на дърветата са достатъчно важни, ние ще се съсредоточи върху ограничен кръг дървета, където всеки родител има най-много двама сина (фиг. 5). Такива двоични дървета (двоично дърво) имат единна структура, която позволява преминаването на различни алгоритми и ефективен достъп до елементите. Проучването на двоични дървета дава възможност за разрешаване на най-често срещаните проблеми, свързани с дървета, тъй като всяко общо вид дърво може да бъде представен чрез еквивалентен двоично дърво.
Всеки възел на двоично дърво може да бъде 0, 1, или 2 сина. По отношение на възела в ляво ще се използва терминът син ляво (вляво дете), и по отношение на възел в дясно - дясното син (вдясно дете). Имената на "ляво" и "дясно" се отнасят за графичното представяне на дървото. А двоичен дървовидна структура е рекурсивен. Всеки възел - е в основата на собствената си поддърво. Той има синове, които от своя страна са корените на дърветата, наречени леви и десни поддървета съответно. По този начин, на процедурата за обработка на рекурсивни дървета. Тук е рекурсивно определение на двоично дърво:
Binary дърво - това е набор от възли, B, което
а) В е дърво, ако възел набор е празна (празна дърво - едно и също дърво);
б) В е разделена на три несвързани подгрупи:
· Ляв поддърво R
· Право поддърво R
На всяко ниво на п двоично дърво може да има от 1 до 2n възли. Броят на дяловете, дължащи се на нивото на индикатор за гъстотата на насажденията. Интуитивно, плътността е мярка за стойността на дървото (броят на възли) по отношение на дълбочината на дървото. Фиг. 5 Графика А съдържа 8 възли на дълбочина 3, докато Графика В съдържа 5 възли в дълбочина 4. последния случай е определена форма, наречена дегенеративен (дегенеративен) дърво, което има един лист (Е) и всеки не-листо възел има само един син. Дегенеративна дърво е еквивалентно на списъка свързани.
Фигура 5. двоични дървета
Дървета с висока плътност е много важно, тъй като структури от данни, тъй като те съдържат пропорционално повече елементи в близост до основата, т.е. с по-къси пътища от корена. Плътни дърво ви позволява да съхранявате големи колекции от данни и прилагане на ефективен достъп до елементите. Бързо търсене - най-важното, което прави използването на дървета за съхранение на данни.
Единични дървета са в мярката за плътност. В другата крайност - пълно двоични дървета (завършат двоично дърво) дълбочина N, където всяко ниво е 0. N - 1 има пълен набор от възли, и оставя всички нива N се намират в ляво. Пълният двоично дърво съдържащ 2N възли на ниво N, е пълна. Фиг. 6 показва пълно и пълни двоични дървета.
Фигура 6. Класификация на двоични дървета
Двоични дървета, се класифицират по няколко причини. Ние въвеждане на концепцията за степента и обхвата на дърво сайт. Степента на възел в дървото е броят на дъгите, което излиза от него. Степента на дървото е равна на максималната степен на възел, включени в дървото. Въз основа на определяне на степента тя разбира, че степента на възел двоично дърво не надвишава броя две. Когато това се оставя в дървото са върховете, които имат степен на нула.
Фигура 7. двоично дърво
Друга важна характеристика на структурната класификация на двоично дърво е двоично дърво строгост. Строго двоично дърво се състои от възли, които имат степен на степен две или нула. Неформално двоично дърво съдържа възли със степен равен на единица.
Фигура 8. Пълна и частична двоични дървета
Фигура 9. Строго не строго двоични дървета
Двоични дървета могат да бъдат представени като просто списъци или масиви. списъчен изглед двоично дърво на основата на елементите, съответстващи на възлите на дървото. Всеки елемент има поле за данни и двата показалеца области. Указателят се използва за свързване на елемент с дясната дете, а другият отляво. Листата са празни низходящи указатели. С този метод на представяне на дървото, не забравяйте да запишете указател към възела, който е в основата на дървото.
Може да се отбележи, че този метод на представяне е подобно на простите линейни списъци. И това сходство не е случайно. Всъщност смята за начин за представяне на двоичен дърво е вид multispiska формира от набор от линейна комбинация от списъци. Всеки линеен списък комбинира възли по пътя от корена на дървото на един от листата.
Фигура 10. Представителство на двоично дърво и списък структура
В масив лесният изглежда пълно двоично дърво, защото то винаги има строго определен брой върхове във всяко ниво. Върховете могат да бъдат номерирани последователно от ляво на дясно през нивата и използва тези номера като индекс в едномерен масив.
Фигура 11. Представителство на двоично дърво в масив
Ако броят на нивата на дървото по време на лечението няма да се промени значително, такъв начин на представяне на пълно двоично дърво ще бъде много по-икономичен от всеки списък структура.
Основният недостатък обсъжда начини да представляват двоичен дърво е, че структурата на данните е статична. Размерът на масива се избира въз основа на максималния възможен брой двоични нива на дърветата. И малко от пълна дървен материал, толкова по-малко памет се използва ефективно.
на [I], състоящ се от 15 елемента (1 до 15) - Масивът се използва като пример за използването на двоично дърво в масив. В резултат на това дърво трябва да изглежда така:
