Визуелни приказ разматраних концепата приказан је на доњој слици:
Овај водич објашњава процес штампања свих лисних чворова бинарног стабла покривајући доле наведене одељке:
- Како препознати чворове листа?
- Како одштампати све лисне чворове бинарног стабла с лева на десно у ЈаваСцрипт-у?
- Бонус савет: Штампање лисних чворова бинарног стабла с десна на лево
- Закључак
Како препознати чворове листа?
„ Лист ” чворови су они који немају подређене чворове, или да будемо прецизни који имају „ висина ” од “ 0 ”. Ако чвор има „ висина ' веће од ' 0 ” тада тај чвор може бити унутрашњи чвор или коријенски чвор. „ Лист ” чворови се обично враћају уназад да би се идентификовао оригинални извор одакле је овај чвор генерисан. Углавном се користи у алгоритмима за претрагу или проналажење грешака да би се пронашао узрок грешке или проблема.
Како одштампати све лисне чворове бинарног стабла с лева на десно у ЈаваСцрипт-у?
Постоје два приступа' рекурзивне ' и ' итеративно ” да изаберете све лисне чворове доступне у датом бинарном стаблу у жељеном „ лево ' до ' јел тако ' правац. Практична примена ових приступа је приказана у доле наведеним одељцима:
- Рекурзивно одштампајте све лисне чворове бинарног стабла с лева на десно
- Одштампајте све лисне чворове бинарног стабла користећи итеративни приступ
Метод 1: Рекурзивно одштампајте све лисне чворове бинарног стабла с лева на десно
Рекурзивни приступ бира све чворове у а алгоритам претраге у дубину начин који прво прелази цео леве бочне чворове, затим средњи чвор и на крају десне бочне чворове. Ова операција се изводи рекурзивно за сваки чвор и када нема даљег преласка „ Лист ” чворови се идентификују. Да бисте боље разумели овај концепт, посетите доњи исечак кода:
класа Чвор{
конструктор ( )
{
ово . садржаја = 0 ;
ово . лево = нула ;
ово . јел тако = нула ;
}
} ;
где дисплаиЛеафНодес = ( роотНоде ) =>
{
ако ( роотНоде == нула )
повратак ;
ако ( роотНоде. лево == нула && роотНоде. јел тако == нула )
{
документ. писати ( роотНоде. садржаја + ' ' ) ;
повратак ;
}
ако ( роотНоде. лево != нула )
дисплаиЛеафНодес ( роотНоде. лево ) ;
ако ( роотНоде. јел тако != нула )
дисплаиЛеафНодес ( роотНоде. јел тако ) ;
}
био самплеНоде = ( вал ) =>
{
је био темпНоде = Нова Чвор ( ) ;
темпНоде. садржаја = вал ;
темпНоде. лево = нула ;
темпНоде. јел тако = нула ;
повратак темпНоде ;
}
је роотНоде = провНоде ( 3 ) ;
роотНоде. лево = провНоде ( 6 ) ;
роотНоде. јел тако = провНоде ( 9 ) ;
роотНоде. лево . лево = провНоде ( 12 ) ;
роотНоде. лево . јел тако = провНоде ( петнаест ) ;
роотНоде. лево . јел тако . јел тако = провНоде ( 24 ) ;
роотНоде. јел тако . лево = провНоде ( 18 ) ;
роотНоде. јел тако . јел тако = провНоде ( двадесет један ) ;
дисплаиЛеафНодес ( роотНоде ) ;
Објашњење горњег блока кода је наведено у наставку:
- Прво направите класу под називом „ чвор ”, који креира нови чвор и поставља његову вредност на „ 0 ”. У прилогу ' лево ' и ' јел тако ” бочни чворови су подешени на “ нула ” подразумевано користећи конструктор класе.
- Затим дефинишите „ дисплаиЛеафНодес() ” функција која прихвата један параметар од “ роотНоде ”. Ова параметарска вредност се сматра тренутно изабраним чвором бинарног стабла.
- Унутар функције, „ ако ” изјава се користи да се провери да ли је „ роотНоде ” је нула или не. У случају ' нула ” даље извршење је заустављено за тај чвор. У другом случају, роотЧвор “ лево ' и ' јел тако ” бочни чворови су проверени за “ нула ”. Ако су оба нула, вредност тог „ чвор ” се штампа.
- Ако је „ лево ” или “ јел тако ” чвор није „нулл”, а затим проследите ту страну чвора на „ дисплаиЛеафНодес() ” функција за рекурзивну операцију.
- Дефинишите нову функцију под називом „ провНоде() ” који прихвата један параметар од „ вал ”. Унутар функције креирајте нову инстанцу „ Чвор ” класа под називом “ темпНоде ”. Додели параметарски „ вал ” као вредност својства класе “ садржаја ” и подесите „ лево ' и ' јел тако ” бочни чворови на “ нула ' подразумевано.
- На крају, креирајте објекат под називом „ роотНоде ' за ' провНоде() ” и проследите вредност чвора као овај параметар функције. Креирајте леви и десни бочни чвор додавањем „ лево ' и ' јел тако ” кључне речи са „роотНоде” и доделите им вредност користећи исту функцију „ провНоде() ”.
- „ лево ” означава леву позицију основног чвора и „ лево.лево “ позиција значи лево од леве, исти приступ се примењује у случају “ јел тако ' и ' јел тако ”
- Након што дефинишете стабло, проследите „роотНоде“ као аргумент за „ дисплаиЛеадНодес() ” функција за одабир и штампање свих лисних чворова креираног стабла.
Излаз генерисан након компилације потврђује да је листни чвор датог стабла преузет и одштампан преко конзоле:
Метод 2: Одштампајте све лисне чворове бинарног стабла користећи итеративни приступ
„ итеративно ” приступ је најефикаснији приступ, користи концепт “ гурати ' и ' поп ” да бисте изабрали „ Лист ” чворови. Кључне тачке или рад овог приступа су наведени у наставку:
класа Чвор{
конструктор ( вредност )
{
ово . података = вредност ;
ово . лево = нула ;
ово . јел тако = нула ;
}
} ;
где дисплаиЛеафНодес = ( роотНоде ) =>
{
ако ( ! роотНоде )
повратак ;
нека листа = [ ] ;
листа. гурати ( роотНоде ) ;
док ( листа. дужина > 0 ) {
роотНоде = листа [ листа. дужина - 1 ] ;
листа. поп ( ) ;
ако ( ! роотНоде. лево && ! роотНоде. јел тако )
документ. писати ( роотНоде. података + ' ' ) ;
ако ( роотНоде. јел тако )
листа. гурати ( роотНоде. јел тако ) ;
ако ( роотНоде. лево )
листа. гурати ( роотНоде. лево ) ;
}
}
је роотНоде = Нова Чвор ( 3 ) ;
роотНоде. лево = Нова Чвор ( 6 ) ;
роотНоде. јел тако = Нова Чвор ( 9 ) ;
роотНоде. лево . лево = Нова Чвор ( 12 ) ;
роотНоде. лево . јел тако = Нова Чвор ( петнаест ) ;
роотНоде. лево . јел тако . јел тако = Нова Чвор ( 24 ) ;
роотНоде. јел тако . лево = Нова Чвор ( 18 ) ;
роотНоде. јел тако . јел тако = Нова Чвор ( двадесет један ) ;
дисплаиЛеафНодес ( роотНоде ) ;
Објашњење горњег кода је написано у наставку:
- Прво направите „ Чвор ” класа која прима један параметар “ вредност ” који је постављен као вредност новокреираног чвора, а лева и десна страна су подешене на нулл. Баш као што је урађено у горњем примеру.
- Затим креирајте функцију ' дисплаиЛеафНодес() ” који прихвата један параметар од „ роотНоде ”. Овај „роотНоде“ се сматра бинарним стаблом и прво се проверава његова празнина.
- Ако чвор није празан, онда је празна листа под називом „ листа ” се креира и „ роотНоде ” параметар се у њега убацује помоћу „ пусх() ” метод.
- Затим ' док() ” се користи који се извршава до дужине „ листа ”. Унутар петље, елемент који се налази на дну дрвета или „ листа ” се уклања помоћу „ поп() ” метод.
- Сада, постојање „ лево ' и ' јел тако ” стране „роотНоде” су проверене, а ако обе стране не постоје, то значи да нема подређени чвор. Затим се овај чвор приказује преко екрана и идентификује као лисни чвор.
- Ако постоји чвор на левој или десној страни значи да има децу. Тада ' лево ' и ' јел тако ” чвор се гура у „ листа ” за даљу операцију проналажења лисног чвора.
- На крају, креирајте прилагођено бинарно стабло прослеђивањем вредности чвора као параметара за „ Чвор ” конструктор класе. Након креирања, проследите стабло „роотНоде“ као аргумент за „ дисплаиЛеафНодес() ” функција.
Излаз генерисан након компилације показује да су листови чворова датог стабла штампани:
Бонус савет: Штампање лисних чворова бинарног стабла с десна на лево
Да бисте преузели све лисне чворове који немају подређене чворове у „ јел тако ' до ' лево ” рекурзивни приступ се највише препоручује због своје лакоће. На пример, исто дрво о којем се говори у горњим одељцима ће се користити за преузимање лисног чвора, али у „ јел тако ' до ' лево ” смер, као што је приказано у наставку:
класа Чвор{
конструктор ( вредност )
{
ово . података = вредност ;
ово . лево = нула ;
ово . јел тако = нула ;
}
} ;
функција дисплаиЛеафНодес ( корен )
{
ако ( корен == нула )
{
повратак ;
}
ако ( корен. лево == нула && корен. јел тако == нула )
{
документ. писати ( корен. података + ' ' ) ;
повратак ;
}
ако ( корен. јел тако != нула )
{
дисплаиЛеафНодес ( корен. јел тако ) ;
}
ако ( корен. лево != нула )
{
дисплаиЛеафНодес ( корен. лево ) ;
}
}
је роотНоде = Нова Чвор ( 3 ) ;
роотНоде. лево = Нова Чвор ( 6 ) ;
роотНоде. јел тако = Нова Чвор ( 9 ) ;
роотНоде. лево . лево = Нова Чвор ( 12 ) ;
роотНоде. лево . јел тако = Нова Чвор ( петнаест ) ;
роотНоде. лево . јел тако . јел тако = Нова Чвор ( 24 ) ;
роотНоде. јел тако . лево = Нова Чвор ( 18 ) ;
роотНоде. јел тако . јел тако = Нова Чвор ( двадесет један ) ;
дисплаиЛеафНодес ( роотНоде ) ;
Горе наведени код функционише овако:
- Прво, час „ Чвор ” је креиран који користи подразумевани конструктор за додавање новог чвора у стабло само везу направљену у горњим примерима.
- Затим, „ дисплаиЛеадНодес() ” креира се функција која прихвата један параметар од “ роотНоде ”. Овај параметар се проверава за „ нула ” услов преко „ ако ' изјава.
- Ако наведени чвор није тачан, онда је „ лево ' и ' јел тако ” бочни чворови су проверени за “ нула ' стање. Ако су оба нула, онда ће чвор бити идентификован као „ Лист ” и одштампан преко веб странице.
- Након тога, прођите „ јел тако ' и ' лево ” чворови од “ роотНоде ' до ' дисплаиЛеафНодес() ” функција.
- Доделите позицију сваког чвора креирањем инстанци користећи „ Нова ” кључна реч и „ чвор() ” конструктор и наводећи позицију као параметар конструктора.
- „ лево ” означава леву позицију основног чвора и „ лево.лево ” позиција значи лево или лево. Исти приступ се примењује у случају „ јел тако ' и ' јел тако ”.
- На крају, проследите „ роотНоде “ као аргумент за “ дисплаиЛеафНоде() ” функција.
Генерисани излаз показује да се листови чворови штампају у смеру здесна налево.
То је све о штампању свих лисних чворова бинарног стабла у било ком жељеном правцу.
Закључак
Да бисте одштампали све лисне чворове бинарног стабла, креирајте случајну класу која креира и додељује вредности чворовима стабла. Затим креирајте случајну функцију која прихвата један чвор стабла у хијерархији од врха до дна. Ова функција садржи више „ ако ” услови који проверавају да ли је „ чвор ” није празан и нема чворове у „ лево ' и ' јел тако ” смер, онда се тај чвор сматра као „ Лист ” и приказује се на конзоли. Овај водич је објаснио процедуру штампања свих лисних чворова бинарног стабла с лева на десно или здесна налево.