Apskatīto jēdzienu vizuālais attēlojums ir parādīts zemāk esošajā attēlā:
Šajā rokasgrāmatā ir izskaidrots visu binārā koka lapu mezglu drukāšanas process, aptverot tālāk minētās sadaļas:
- Kā identificēt lapu mezglus?
- Kā JavaScript izdrukāt visus binārā koka lapu mezglus no kreisās uz labo pusi?
- Bonusa padoms: binārā koka lapu mezglu drukāšana no labās puses uz kreiso pusi
- Secinājums
Kā identificēt lapu mezglus?
' lapu mezgli ir tie, kuriem nav pakārtotu mezglu, vai, ja precīzāk, tiem ir augstums ” no “ 0 ”. Ja mezglam ir “ augstums ' lielāks nekā ' 0 ”, tad šis mezgls var būt iekšējais mezgls vai saknes mezgls. ' lapu ” mezgli parasti tiek atgriezti, lai identificētu sākotnējo avotu, no kura šis mezgls ir ģenerēts. To galvenokārt izmanto meklēšanas vai kļūdu meklēšanas algoritmos, lai atrastu kļūdas vai problēmas cēloni.
Kā JavaScript izdrukāt visus binārā koka lapu mezglus no kreisās uz labo pusi?
Ir divas pieejas ' rekursīvs ' un ' iteratīvs ”, lai atlasītajā binārajā kokā visus pieejamos lapu mezglus vēlamajā pa kreisi 'uz' pa labi ” virziens. Šo pieeju praktiskā īstenošana ir parādīta tālāk norādītajās sadaļās.
- Rekursīvi drukājiet visus binārā koka lapu mezglus no kreisās puses uz labo
- Drukājiet visus binārā koka lapu mezglus, izmantojot iteratīvo pieeju
1. metode: rekursīvi drukājiet visus binārā koka lapu mezglus no kreisās puses uz labo
Rekursīvā pieeja atlasa visus a mezglus dziļuma pirmās meklēšanas algoritms veids, kas vispirms šķērso visus kreisās puses mezglus, tad vidējo mezglu un labās puses mezglus beigās. Šī darbība tiek veikta rekursīvi katram mezglam un, kad vairs nav jāšķērso “ lapu ” mezgli tiek identificēti. Lai labāk izprastu šo koncepciju, apmeklējiet tālāk norādīto koda fragmentu.
klasē Mezgls{
konstruktors ( )
{
šis . saturu = 0 ;
šis . pa kreisi = null ;
šis . pa labi = null ;
}
} ;
kur tiek parādīti LeafNodes = ( rootNode ) =>
{
ja ( rootNode == null )
atgriezties ;
ja ( rootNode. pa kreisi == null && rootNode. pa labi == null )
{
dokumentu. rakstīt ( rootNode. saturu + ' ' ) ;
atgriezties ;
}
ja ( rootNode. pa kreisi != null )
displejsLeafNodes ( rootNode. pa kreisi ) ;
ja ( rootNode. pa labi != null )
displejsLeafNodes ( rootNode. pa labi ) ;
}
bija sampleNode = ( val ) =>
{
bija tempNode = jauns Mezgls ( ) ;
tempNode. saturu = val ;
tempNode. pa kreisi = null ;
tempNode. pa labi = null ;
atgriezties tempNode ;
}
bija rootNode = provNode ( 3 ) ;
rootNode. pa kreisi = provNode ( 6 ) ;
rootNode. pa labi = provNode ( 9 ) ;
rootNode. pa kreisi . pa kreisi = provNode ( 12 ) ;
rootNode. pa kreisi . pa labi = provNode ( piecpadsmit ) ;
rootNode. pa kreisi . pa labi . pa labi = provNode ( 24 ) ;
rootNode. pa labi . pa kreisi = provNode ( 18 ) ;
rootNode. pa labi . pa labi = provNode ( divdesmitviens ) ;
displejsLeafNodes ( rootNode ) ;
Iepriekš minētā koda bloka skaidrojums ir norādīts zemāk:
- Vispirms izveidojiet klasi ar nosaukumu ' mezgls ”, kas izveido jaunu mezglu un iestata tā vērtību uz “ 0 ”. Pievienotais ' pa kreisi ' un ' pa labi ' sānu mezgli ir iestatīti uz ' null ” pēc noklusējuma, izmantojot klases konstruktoru.
- Pēc tam definējiet ' displejsLeafNodes() ' funkcija, kas pieņem vienu '' parametru rootNode ”. Šī parametra vērtība tiek uzskatīta par pašlaik atlasīto binārā koka mezglu.
- Funkcijā “ ja ' paziņojums tiek izmantots, lai pārbaudītu, vai ' rootNode ” ir nulle vai nav. Gadījumā, ja ' null ” tālākā izpilde apstājās šim mezglam. Citā gadījumā rootNode ' pa kreisi ' un ' pa labi ' sānu mezgli ir pārbaudīti ' null ”. Ja abi ir nulles, šī vērtība mezgls ” tiek izdrukāts.
- Ja “ pa kreisi ” vai “ pa labi ” mezgls nav “null”, tad nododiet šo mezgla pusi uz “ displejsLeafNodes() ” funkcija rekursīvai darbībai.
- Definējiet jaunu funkciju ar nosaukumu ' provNode() ', kas pieņem vienu parametru ' val ”. Funkcijā izveidojiet jaunu ' Mezgls 'klase ar nosaukumu ' tempNode ”. Piešķiriet parametru ' val ' kā klases īpašuma vērtību ' saturu un iestatiet pa kreisi ' un ' pa labi ' sānu mezgli uz ' null ' pēc noklusējuma.
- Visbeidzot izveidojiet objektu ar nosaukumu ' rootNode ' priekš ' provNode() ” funkciju un nodod mezgla vērtību kā šo funkcijas parametru. Izveidojiet kreisās un labās puses mezglus, pievienojot “ pa kreisi ' un ' pa labi ' atslēgvārdus ar 'rootNode' un piešķiriet tiem vērtību, izmantojot to pašu funkciju ' provNode() ”.
- ' pa kreisi ' nozīmē saknes mezgla kreiso pozīciju un ' pa kreisi.pa kreisi ” pozīcija nozīmē, ka pa kreisi no kreisās puses, tā pati pieeja tiek piemērota gadījumā pa labi ' un ' pa labi ”
- Pēc koka definēšanas nododiet “rootNode” kā argumentu “ displayLeadNodes() ” funkciju, lai atlasītu un izdrukātu visus izveidotā koka lapu mezglus.
Pēc kompilācijas ģenerētā izvade apstiprina, ka nodrošinātā koka lapas mezgls ir izgūts un izdrukāts pa konsoli:
2. metode: drukājiet visus binārā koka lapu mezglus, izmantojot iteratīvo pieeju
' iteratīvs 'pieeja ir visefektīvākā pieeja, tā izmanto jēdzienu ' spiediet ' un ' pop ”, lai atlasītu lapu ” mezgli. Šīs pieejas galvenie punkti vai darbība ir norādīta zemāk:
klasē Mezgls{
konstruktors ( vērtību )
{
šis . datus = vērtību ;
šis . pa kreisi = null ;
šis . pa labi = null ;
}
} ;
kur tiek parādīti LeafNodes = ( rootNode ) =>
{
ja ( ! rootNode )
atgriezties ;
ļaujiet sarakstu = [ ] ;
sarakstu. spiediet ( rootNode ) ;
kamēr ( sarakstu. garums > 0 ) {
rootNode = sarakstu [ sarakstu. garums - 1 ] ;
sarakstu. pop ( ) ;
ja ( ! rootNode. pa kreisi && ! rootNode. pa labi )
dokumentu. rakstīt ( rootNode. datus + ' ' ) ;
ja ( rootNode. pa labi )
sarakstu. spiediet ( rootNode. pa labi ) ;
ja ( rootNode. pa kreisi )
sarakstu. spiediet ( rootNode. pa kreisi ) ;
}
}
bija rootNode = jauns Mezgls ( 3 ) ;
rootNode. pa kreisi = jauns Mezgls ( 6 ) ;
rootNode. pa labi = jauns Mezgls ( 9 ) ;
rootNode. pa kreisi . pa kreisi = jauns Mezgls ( 12 ) ;
rootNode. pa kreisi . pa labi = jauns Mezgls ( piecpadsmit ) ;
rootNode. pa kreisi . pa labi . pa labi = jauns Mezgls ( 24 ) ;
rootNode. pa labi . pa kreisi = jauns Mezgls ( 18 ) ;
rootNode. pa labi . pa labi = jauns Mezgls ( divdesmitviens ) ;
displejsLeafNodes ( rootNode ) ;
Iepriekš minētā koda skaidrojums ir rakstīts zemāk:
- Vispirms izveidojiet ' Mezgls 'klase, kas saņem vienu parametru' vērtību ”, kas ir iestatīta kā jaunizveidotā mezgla vērtība, un kreisā un labā puse ir iestatīta uz nulli. Tāpat kā iepriekš minētajā piemērā.
- Pēc tam izveidojiet funkciju ' displejsLeafNodes() ', kas pieņem vienu parametru ' rootNode ”. Šis “saknes mezgls” tiek uzskatīts par bināro koku un vispirms tiek pārbaudīts tā tukšums.
- Ja mezgls nav tukšs, tad tukšs saraksts ar nosaukumu “ sarakstu tiek izveidots un ' rootNode ' parametrs tiek ievietots tajā, izmantojot ' push () ” metode.
- Pēc tam ' kamēr () tiek izmantots, kas tiek izpildīts līdz ' sarakstu ”. Cilpas iekšpusē elements, kas atrodas koka apakšā vai “ sarakstu 'tiek noņemts, izmantojot ' pop () ” metode.
- Tagad pastāv ' pa kreisi ' un ' pa labi 'RootNode' puses ir pārbaudītas, un, ja abas puses neeksistē, tas nozīmē, ka tai nav pakārtota mezgla. Pēc tam šis mezgls tiek parādīts ekrānā un identificēts kā lapas mezgls.
- Ja kreisajā vai labajā pusē ir mezgls, tas nozīmē, ka tam ir bērni. Tad tas ' pa kreisi ' un ' pa labi mezgls tiek nospiests sarakstu ” turpmākai darbībai lapas mezgla atrašanā.
- Beigās izveidojiet pielāgotu bināro koku, nododot mezgla vērtības kā parametrus ' Mezgls ” klases konstruktors. Pēc izveides nododiet koku “rootNode” kā argumentu “ displejsLeafNodes() ” funkcija.
Pēc kompilācijas ģenerētā izvade parāda, ka nodrošinātā koka lapu mezgli ir izdrukāti:
Bonusa padoms: binārā koka lapu mezglu drukāšana no labās puses uz kreiso pusi
Lai izgūtu visus lapu mezglus, kuriem nav bērnu mezglu pa labi 'uz' pa kreisi ” virzienā, rekursīvā pieeja ir ieteicamākā tās viegluma dēļ. Piemēram, tas pats koks, kas tika apspriests iepriekš minētajās sadaļās, tiks izmantots, lai izgūtu lapas mezglu, bet ' pa labi 'uz' pa kreisi ” virziens, kā parādīts zemāk:
klasē Mezgls{
konstruktors ( vērtību )
{
šis . datus = vērtību ;
šis . pa kreisi = null ;
šis . pa labi = null ;
}
} ;
funkcija displayLeafNodes ( sakne )
{
ja ( sakne == null )
{
atgriezties ;
}
ja ( sakne. pa kreisi == null && sakne. pa labi == null )
{
dokumentu. rakstīt ( sakne. datus + ' ' ) ;
atgriezties ;
}
ja ( sakne. pa labi != null )
{
displejsLeafNodes ( sakne. pa labi ) ;
}
ja ( sakne. pa kreisi != null )
{
displejsLeafNodes ( sakne. pa kreisi ) ;
}
}
bija rootNode = jauns Mezgls ( 3 ) ;
rootNode. pa kreisi = jauns Mezgls ( 6 ) ;
rootNode. pa labi = jauns Mezgls ( 9 ) ;
rootNode. pa kreisi . pa kreisi = jauns Mezgls ( 12 ) ;
rootNode. pa kreisi . pa labi = jauns Mezgls ( piecpadsmit ) ;
rootNode. pa kreisi . pa labi . pa labi = jauns Mezgls ( 24 ) ;
rootNode. pa labi . pa kreisi = jauns Mezgls ( 18 ) ;
rootNode. pa labi . pa labi = jauns Mezgls ( divdesmitviens ) ;
displejsLeafNodes ( rootNode ) ;
Iepriekš minētais kods darbojas šādi:
- Pirmkārt, klase ' Mezgls Tiek izveidots, kas izmanto noklusējuma konstruktoru, lai kokam pievienotu jaunu mezglu, tikai saiti, kas veikta iepriekš minētajos piemēros.
- Tālāk “ displayLeadNodes() Tiek izveidota funkcija ', kas pieņem vienu parametru ' rootNode ”. Šis parametrs ir pārbaudīts ' null ' nosacījums, izmantojot ' ja ' paziņojums, apgalvojums.
- Ja norādītais mezgls nav patiess, tad tā ' pa kreisi ' un ' pa labi ' sānu mezgli ir pārbaudīti ' null ” nosacījums. Ja abi ir nulles, mezgls tiks identificēts kā ' lapu ” mezglā un izdrukāts virs tīmekļa lapas.
- Pēc tam ejiet garām ' pa labi ' un ' pa kreisi ' mezgli ' rootNode 'uz' displejsLeafNodes() ” funkcija.
- Piešķiriet katra mezgla pozīciju, izveidojot gadījumus, izmantojot ' jauns ' atslēgvārds un ' Mezgls () ” konstruktoru un kā konstruktora parametru norādot pozīciju.
- ' pa kreisi ' nozīmē saknes mezgla kreiso pozīciju un ' pa kreisi.pa kreisi ” pozīcija nozīmē pa kreisi vai pa kreisi. Tāda pati pieeja tiek piemērota gadījumā ' pa labi ' un ' pa labi ”.
- Visbeidzot, nododiet ' rootNode ' kā argumentu ' displejsLeafNode() ” funkcija.
Ģenerētā izvade parāda, ka lapu mezgli tiek drukāti virzienā no labās puses uz kreiso.
Tas viss attiecas uz visu binārā koka lapu mezglu drukāšanu jebkurā vēlamajā virzienā.
Secinājums
Lai drukātu visus binārā koka lapu mezglus, izveidojiet nejaušu klasi, kas izveido un piešķir vērtības koka mezgliem. Pēc tam izveidojiet nejaušu funkciju, kas pieņem vienu koka mezglu hierarhijā no augšas uz leju. Šī funkcija satur vairākus ' ja ' nosacījumi, kas pārbauda, vai ' mezgls ' nav tukšs, un tajā nav mezglu pa kreisi ' un ' pa labi ' virzienā, tad šis mezgls tiek uzskatīts par ' lapu ” mezgls un tiek parādīts konsolē. Šajā rokasgrāmatā ir izskaidrota visu binārā koka lapu mezglu drukāšanas procedūra no kreisās puses uz labo vai no labās uz kreiso pusi.