Урок за структурата на дървесните данни за начинаещи

Въведение

Дървото в софтуера е като биологично дърво, но със следните разлики:

• Рисува се с главата надолу.
• Той има само един корен и няма стъбло.
• Клоните излизат от корена.
• Точка, в която клон излита от друг клон или коренът, се нарича възел.
• Всеки възел има стойност.

Клоновете на софтуерното дърво са представени с прави линии. Добър пример за софтуерно дърво, което може да сте използвали, е дървото на директориите на твърдия диск на вашия компютър.

Има различни видове дървета. Има общото дърво, от което са получени други дървета. Други дървета се получават чрез въвеждане на ограничения в общото дърво. Например, може да искате дърво, където не повече от два клона произлизат от възел; такова дърво би било наречено двоично дърво.  Тази статия описва общото дърво и как да получите достъп до всички негови възли.

Хипервръзката за изтегляне на кода е дадена в долната част на тази статия.

За да разберете примерните кодове в тази статия, трябва да имате основни познания по JavaScript (ECMAScript). Ако нямате тези знания, можете да ги получите от http: // www.широка мрежа.com / ChrysanthusForcha-1 / ECMAScript-2015-Course.htm

Диаграма на общото дърво

„A“ е основният възел; това е възел от първо ниво. B, C, D са на втория ред; това са възли от второ ниво. E, F, G, H, I, J, K са на третия ред и са възли от трето ниво. Четвърти ред би създал възли от четвърто ниво и т.н.

Свойства на дърво

- Всички клонове за всички нива на възли имат един източник, който е основният възел.

- Дървото има N - 1 клона, където N е общият брой възли. Горната диаграма за общото дърво има 11 възли и 10 клона.

- За разлика от хората, където всяко дете има двама родители, със софтуерното дърво всяко дете има само един родител. Коренният възел е най-големият родител-предшественик. Родителят може да има повече от едно дете. Всеки възел, с изключение на главния възел, е дете.

Речник на дърветата

• Основен възел: Това е най-високият възел в дървото и той няма родител. Всеки друг възел има родител.
• Листни възли: Листният възел е възел, който няма дете. Те обикновено са в долната част на дървото, а понякога са в лявата и / или дясната страна на дървото.
• Ключ: Това е стойността на едно дърво. Може да е число; може да е низ; дори може да бъде оператор като + или - или x.
• Нива: Коренният възел е на първо ниво. Децата му са на второ ниво; Децата на възлите от второ ниво са на трето ниво и т.н.
• Родителски възел: Всеки възел, с изключение на главния възел, има родителски възел, свързан с него чрез клон. Всеки възел, с изключение на главния възел, е дъщерен възел.
• Възли на братя и сестри: Възли на братя и сестри са възли, които имат един и същ родител.
• Път: Клоновете (прави линии), които свързват един възел с друг, чрез други възли, образуват път. Клоновете могат да бъдат или да не са стрелки.
• Възел на предците: Всички по-високи възли, свързани с дете, включително родителския и главния възел, са възли на предшественици.
• Възходящ възел: Всички долни възли, свързани към възел, чак до свързаните листа, са възходящи възли. Въпросният възел не е част от низходящите възли. Въпросният възел не трябва да бъде главният възел.
• Поддърво: Възел плюс всички негови потомци чак до свързаните листа формира поддърво. Стартовият възел е включен и не е задължително да е коренът; в противен случай това би било цялото дърво.
• Степен: Броят на децата, които има възел, се нарича степента на възела.

Преминаване през всички възли на дърво

Всички възли на дърво могат да бъдат достъпни за четене или промяна на всяка стойност на възела. Това обаче не се прави произволно. Има три начина за това, като всеки от тях включва обхождане на дълбочина - първо, както следва:

1) По поръчка: Просто казано, в тази схема първо се преминава през лявото поддърво; след това се осъществява достъп до коренния възел; след това се преминава през дясното поддърво. Тази схема е символизирана като ляво-> корен-> дясно. Фигура 1 е отново показана тук за лесна справка:

Ако приемем, че има двама братя и сестри на възел; след това наляво-> корен-> надясно означава, че първо влизате в най-долния и най-левия възел, след това в родителя на възела и след това в дясното братче. Когато има повече от двама братя и сестри, вземете първия като левия, а останалите десни възли като десния. За общото дърво по-горе, долното ляво поддърво има достъп до [EBF]. Това е поддърво. Родителят на това поддърво е A; така че следващият достъп се получава, за да има [EBF] A. След това се осъществява достъп до поддървото [GCHI], за да има по-голямо поддърво, [[EBF] A [GCHI]]. Можете да видите ляв-> корен-> десен профил, който се изобразява. Това голямо ляво поддърво ще има поддървото, [JDK] отдясно, за да завърши обхождането, за да получи, [[EBF] A [GCHI]] [JDK].

2) Предварителна поръчка: Просто казано, в тази схема първо се осъществява достъп до коренния възел, след това се преминава към лявото поддърво и след това към дясното поддърво. Тази схема е символизирана като корен-> ляво-> дясно. Фигура 1 е отново показана тук за лесна справка.

Ако приемем, че има двама братя и сестри на възел; след това root-> ляво-> дясно означава, първо имате достъп до корен, след това до лявото непосредствено дете и след това до дясното непосредствено дете. Когато има повече от двама братя и сестри, вземете първия като левия, а останалите десни възли като десния. Най-лявото дете на лявото дете е следващото, до което има достъп. За общото дърво по-горе коренното поддърво е [ABCD]. Вляво от това поддърво имате поддърво [EF], даващо последователността за достъп, [ABCD] [EF]. Вдясно от това по-голямо поддърво имате две поддървета, [GHI] и [JK], даващи пълната последователност, [ABCD] [EF] [GHI] [JK]. Можете да видите корен-> ляв-> десен профил, който се изобразява.

3) Следваща поръчка: Просто казано, в тази схема първо се преминава през лявото поддърво, след това се преминава през дясното поддърво и след това се осъществява достъп до корен. Тази схема е символизирана като ляв-> десен-> корен. Фигура 1 е отново показана тук за лесна справка.

За това дърво поддърветата са [EFB], [GHIC], [JKD] и [A], които образуват последователността, [EFB], [GHIC], [JKD] [A]. Можете да видите ляв-> десен-> профил на корена, който се изобразява.

Създаване на дървото

Горното дърво ще бъде създадено с помощта на ECMAScript, което е като последната версия на JavaScript. Всеки възел е масив. Първият елемент от всеки масив на възел е родителят на възела, друг масив. Останалите елементи на възела са деца на възела, започвайки от най-лявото дете. Има карта на ECMAScript, която свързва всеки масив със съответния низ (буква). Първият кодов сегмент е: