Дървета ориентирана, подреден и двоичен
Wood - графика, която се характеризира със следните свойства:
1. Съществува уникален елемент (възел или връх), която не се отнася до всеки друг елемент - и която се нарича корена.
2. Започвайки в основата и след за някои указатели верига, съдържащи се в елементите, е възможно да се достъп до всяка структура елемент.
Името "дървото" идва от логично равностойността на дървовидна структура абстрактно дърво в теория на графите. Комуникационната връзка между двойка възли в клоните на дърветата, обикновено се нарича. Тези възли, които не се отнасят до всякакви други възлови точки в дървото, наречени лист (или крайни възли) възлова точка, която не е листа или корен, тя се счита за междинен възел или клон (или nonterminal вътрешен връх).
За насочено графика на броя на ръбовете, произтичащи от някои първоначални връх V, се нарича outdegree този връх. Броят на ръбовете, за които връх V е крайно, наречен indegree връх V, и сумата от outdegree и определяне на върховете V наречени пълната степен на върха.
По-долу ще бъдат представени на важен клас графики - ориентирани дървета - и съответната терминология. Дървета трябва да опише всяка структура с йерархия. Традиционните примери за такива структури: семейни дървета, десетична класификация на книги в библиотеките, йерархията на позициите в рамките на организацията, алгебричен израз, включваща операции, които се предписват определени приоритетни правила.
Ориентирани дърво - е такава, ацикличен насочено графика на (диграфа), в която един връх наречен корен, има indegree 0, а останалите - indegree на 1. ориентирани дърво трябва да има поне един връх. Изолираният връх също е ориентирана дърво.
Vertex базирани дърво outdegree от които е нула, то се нарича край (суспензия) или върха на листа; всички други върховете на дървото се нарича клон върхове. Дължината от корена до върха, наречена LEVEL (LAYER НОМЕР) на този връх. дървена основа корен ниво е равно на нула, и нивото на всеки друг връх е разстоянието (т.е. разликата в абсолютни стойности на нивата на върховете) между този връх и корена. Ориентирано дърво е ацикличен граф, по целия път в него елементарен.
В много приложения на относителния ред на върховете в всяко ниво има специфично значение. Когато в дървовидния изглед на компютъра се въвежда автоматично такава заповед, дори ако тя самата е произволна. Последователността на върха в определен от първи ред, лесно можете да въведете, отбелязвайки връх, както и първия, и от друга - като второто, и т.н. Вместо да се разпорежда върховете да укажете реда, по краищата. Ако ориентирано дърво на всяко ниво се дава от порядъка на върховете, като дърво е наредено дърво.
Ние също въведе някои от концепциите, свързани с дървета.
Node X се нарича предшественик (или баща), и Y и Z са наречени възли наследник (или синове) между тях съответно се наричат братя. И от ляво е син на най-големия син, а в дясно - най-младият. Броят на поддървета на даден връх се нарича степента на върхове. (В този пример, X е 2 поддърво следователно СТЕПЕН връх X е
Ако в основата на дървото и премахване на ребрата, които се свързват корена с върховете на първото ниво, можете да получите много несвързани дървета. Комплектът се нарича горски дървета несвързан
Видяхме, че могат да се определят последователностите и списъци, да споделят както следва: всяка последователност (спин-сок) с основа тип Т - това е:
празна последователност (списък); или
конкатенация (верига) на елементите, и последователността на степента на Т потока с основа тип Т.
Тук, за принципите на определение структуриране (следва проучване или-повторение), използвайки рекурсия. След итерация и са толкова чести, че те обикновено са Сдз-стопи фундаментален "образ", както структури от данни и програми "Управление". Въпреки това, винаги трябва да се помни, че с помощта на рекурсия те могат да бъдат определени само-lyat но рекурсия може да бъде ефективно и елегантно използва ваната, за да се определи по-сложни структури.
Добре известен пример е дърветата. Нека vovidnaya-ядро структура се определя както следва: Ядро-vovidnaya база тип структура с Т - или е:
1) празен структура; или
2) комплект от типа Т, която е свързана с краен брой дървовидна структура-TION с основа тип Т наречената любопитни revyami.
От сходството на рекурсивни дефиниции последователно stey и дървесни структури може да се види, че последователността (списък) е дървовидна структура, в която всеки възел има най-много един "поддървото". Ето защо, последовател-ност (списъка) се нарича още дегенерат дърво.
Има различни начини, дървовидна структура на изображението. Да предположим например, база тип Т е набор от букви; това дърво структура по различни начини изо-припой на фиг. Всички тези идеи показват една и съща структура, поради което еквивалент. С pomoschyugrafa можете да визуализирате разклоняващи връзки, които разбираемо са довели до obscheupotrebitel-Term Терминът "дърво". Въпреки това, достатъчно странно, де дървета бяха решили да рисувам с главата надолу, или - ако някой предпочита да изрази този факт по различен начин - да представлява корените на дървото. Но последната форма е подвеждащо, като горния възел (А) е обикновено nazyvayutkornem. Въпреки mysoznaem че естеството на дърветата не са-много по-сложен, отколкото структури нашия абстракция, ние ще способства дървовидна структура, наречена едно дърво.
Поръчано дърво - дърво, което е kazh-дого възел нареди клонове. Вследствие на това нареди неправителствена tree- две е специален, различен от другите дървета. Node у, който е директно под х възел се нарича (директно) потомък х; ако л е naurovneI, ние казваме chtou - на urovnei - \ - \. Напротив, uzelh нарича (пряко) предшественик от. Смята се, че в основата на дървото се намира на ниво 1. Maxi-мал ниво на всеки елемент на дървото се нарича дълбочина или височина.
Ако елементът има не потомството се нарича терминал член или член лист и не-терминал, nazyvaetsyavnutrennim възел. Брой (Nepo-sredstvenno) потомци вътрешен възел наречен egostepenyu. Максималната степен на всички възли е сила, де-рев. Броят на клоновете или ръбове, които трябва да преминат, за да се премине от корена до uzluh, nazyvaetsyadlinoy .Koren път има дължина на пътя от 1, неговите преки потомци - .. 2 дължина на пътя и т.н. Като цяло, един възел на ниво и е с дължина на пътя с дължина L на дърво се определя като сумата от дължините PU-Дрен на всички единици. Тя се нарича дължината на рамките на това начина, по който. Например дължината на вътрешната пътя на дърво е показано на фиг. 2.1, равен на 52.
Фигура 2.1.Predstavleniya дървовидна структура.
За да се определи това, което се нарича дължина на външен път, ние ще допълни специален дърво възел всеки път, когато vstre-chaetsya нула поддърво. В същото време, ние вярваме, че всички възли трябва да имат една и съща степен - степента на дърво. Track-ствие, като разширение на дървото включва запълване на празните клони, разбира се, специалните части имат по-нататъшни потомци. Дървото е показано на фиг. 2.1, комплемент-nennoe специални възли, показани на Фиг. 2.3, където възли спе-циално представени чрез квадрати.
Фиг. 2.2 Две различни двоично дърво.
Фиг. 2.3. Тройна дърво със специални възли.
Дължината на външния път сега се определя като сума dlinputey всички специални единици. Едно дърво, показано на фиг. 2.3, дължината на външния път 153 е равна.
Броят на специални възли m да се добавят към дървото на степен г, е в пряка зависимост от броя п е-Khodnev възли. Имайте предвид, че всеки възел показва точно един клон. Следователно, има разширена поддърво м -F- п клонове. От друга страна, от всеки източник възел г разклонява и на специални възли - аудио. В този, всички клонове imeetsyadn -F- 1 (1 позволява клон, сочещи към корена-проводящ). От тези две уравнения, получаваме следния равенство настоящото-M между броя на специални компоненти и п-ЛИЗАЦИЯ изходен възел: DN + 1 = m -F- п, или
Максималният брой възли в дърво предварително определена височина ч се постига в случай, когато всички възли имат г поддървета изключение ниво часа, без да имат възли. След това, степен г дървото първо ниво 1 включва възел (корен) г 2 Ниво съдържа своите деца, Ниво 3 съдържа детските d2 г Етап 2 възли и т.н. Това дава следната стойност ..:
като максималният брой на възли за дърво с височина часа и степен г. За г = 2 получаваме
Поръчаните дървета от степен 2 имат особено важна роля. Те се наричат двоични дървета. Ние дефинираме подредена двоично дърво като ограничен набор от елементи, ченгета (възли), всеки от които е или празна или sostoitiz корен (възел), свързана към две различни binarnymiderevyami, наречена ляво и дясно поддърво на корена. В следващите параграфи на този раздел, ние разглеждаме само двоични дървета и защо ние консумираме-lyat думата "дърво", което означава "едно подредено двоично дърво." Дървета със степен по-голяма от 2, се наричат силно разклонени дървета (multiwaytrees). ,
Познати примери за двоични дървета са семейство (семейство) дърво с баща си и човешката майка като неговите наследници, историята на турнира по тенис, където всеки възел е игра, определен от победителя му и поддървета - предишните две игри противници; (!) аритметичен израз с двойни операции където kazhdayaoperatsiya е разклонения възел операнди като поддървета.