Vizualni prikaz razmatranih koncepata prikazan je na donjoj slici:
Ovaj vodič objašnjava postupak ispisa svih lisnih čvorova binarnog stabla pokrivanjem dolje navedenih odjeljaka:
- Kako identificirati lisne čvorove?
- Kako ispisati sve lisne čvorove binarnog stabla slijeva nadesno u JavaScriptu?
- Dodatni savjet: Ispis lisnih čvorova binarnog stabla s desna na lijevo
- Zaključak
Kako identificirati lisne čvorove?
' list ” čvorovi su oni koji nemaju podređene čvorove, ili da budemo specifični koji imaju „ visina ” od “ 0 ”. Ako čvor ima ' visina ” veći od ” 0 ” tada taj čvor može biti unutarnji ili korijenski čvor. ' list ” čvorovi se obično vraćaju unazad kako bi se identificirao izvorni izvor odakle je ovaj čvor generiran. Uglavnom se koristi u algoritmima za pretraživanje ili pronalaženje pogrešaka kako bi se pronašao uzrok pogreške ili problema.
Kako ispisati sve lisne čvorove binarnog stabla slijeva nadesno u JavaScriptu?
Postoje dva pristupa' ponavljajući ' i ' iterativni ” za odabir svih lisnih čvorova dostupnih u danom binarnom stablu u željenom “ lijevo ” do “ pravo ” smjer. Praktična provedba ovih pristupa prikazana je u sljedećim odjeljcima:
- Rekurzivno ispišite sve lisne čvorove binarnog stabla s lijeva na desno
- Ispišite sve lisne čvorove binarnog stabla pomoću iterativnog pristupa
Metoda 1: Rekurzivno ispišite sve lisne čvorove binarnog stabla s lijeva na desno
Rekurzivni pristup odabire sve čvorove u a algoritam pretraživanja u dubinu način koji prvo prelazi cijele lijeve bočne čvorove zatim srednji čvor i na kraju desne bočne čvorove. Ova se operacija izvodi rekurzivno za svaki čvor i kada nema daljnjeg obilaska ' list ” identificiraju se čvorovi. Da biste bolje razumjeli ovaj koncept, posjetite donji isječak koda:
razreda Čvor{
konstruktor ( )
{
ovaj . sadržaj = 0 ;
ovaj . lijevo = ništavan ;
ovaj . pravo = ništavan ;
}
} ;
gdje displayLeafNodes = ( rootNode ) =>
{
ako ( rootNode == ništavan )
povratak ;
ako ( rootNode. lijevo == ništavan && rootNode. pravo == ništavan )
{
dokument. pisati ( rootNode. sadržaj + ' ' ) ;
povratak ;
}
ako ( rootNode. lijevo != ništavan )
displayLeafNodes ( rootNode. lijevo ) ;
ako ( rootNode. pravo != ništavan )
displayLeafNodes ( rootNode. pravo ) ;
}
bio sampleNode = ( val ) =>
{
bio je tempNode = novi Čvor ( ) ;
tempNode. sadržaj = val ;
tempNode. lijevo = ništavan ;
tempNode. pravo = ništavan ;
povratak tempNode ;
}
bio rootNode = provNode ( 3 ) ;
rootNode. lijevo = provNode ( 6 ) ;
rootNode. pravo = provNode ( 9 ) ;
rootNode. lijevo . lijevo = provNode ( 12 ) ;
rootNode. lijevo . pravo = provNode ( petnaest ) ;
rootNode. lijevo . pravo . pravo = provNode ( 24 ) ;
rootNode. pravo . lijevo = provNode ( 18 ) ;
rootNode. pravo . pravo = provNode ( dvadeset i jedan ) ;
displayLeafNodes ( rootNode ) ;
Objašnjenje gornjeg bloka koda navedeno je u nastavku:
- Prvo kreirajte klasu pod nazivom ' čvor ', koji stvara novi čvor i postavlja njegovu vrijednost na ' 0 ”. Priloženi “ lijevo ' i ' pravo ” bočni čvorovi postavljeni su na “ ništavan ” prema zadanim postavkama koristeći konstruktor klase.
- Zatim definirajte ' displayLeafNodes() ' funkcija koja prihvaća jedan parametar od ' rootNode ”. Ova parametarska vrijednost smatra se trenutno odabranim čvorom binarnog stabla.
- Unutar funkcije, ' ako ' naredba se koristi za provjeru je li ' rootNode ” je nula ili nije. U slučaju ' ništavan ” daljnje izvršenje zaustavljeno za taj čvor. U drugom slučaju, rootNode ' lijevo ' i ' pravo ” bočni čvorovi se provjeravaju za “ ništavan ”. Ako su obje null, vrijednost tog ' čvor ” se ispisuje.
- Ako ' lijevo ' ili ' pravo ” čvor nije „nula”, zatim tu stranu čvora proslijedite u „ displayLeafNodes() ” za rekurzivnu operaciju.
- Definirajte novu funkciju pod nazivom ' provNode() ' koji prihvaća jedan parametar od ' val ”. Unutar funkcije stvorite novu instancu ' Čvor ' klasa pod nazivom ' tempNode ”. Dodijelite parametar ' val ” kao vrijednost za svojstvo klase “ sadržaj ' i postavite ' lijevo ' i ' pravo ” bočni čvorovi do “ ništavan ” prema zadanim postavkama.
- Na kraju, stvorite objekt pod nazivom ' rootNode ' za ' provNode() ” i proslijedite vrijednost čvora kao ovaj parametar funkcije. Stvorite lijevi i desni bočni čvor dodavanjem ' lijevo ' i ' pravo ' ključne riječi s 'rootNode' i dodijelite im vrijednost pomoću iste funkcije ' provNode() ”.
- ' lijevo ” znači lijevi položaj korijenskog čvora i „ lijevo.lijevo ' položaj znači lijevo od lijevo isti pristup se primjenjuje u slučaju ' pravo ' i ' pravo ”
- Nakon definiranja stabla, proslijedite 'rootNode' kao argument za ' displayLeadNodes() ” za odabir i ispis svih lisnih čvorova stvorenog stabla.
Izlaz generiran nakon kompilacije potvrđuje da je lisni čvor danog stabla dohvaćen i ispisan preko konzole:
Metoda 2: Ispis svih listova čvorova binarnog stabla korištenjem iterativnog pristupa
' iterativni ” pristup je najučinkovitiji pristup, on koristi koncept “ gurnuti ' i ' pop ' za odabir ' list ” čvorova. Ključne točke ili rad ovog pristupa navedeni su u nastavku:
razreda Čvor{
konstruktor ( vrijednost )
{
ovaj . podaci = vrijednost ;
ovaj . lijevo = ništavan ;
ovaj . pravo = ništavan ;
}
} ;
gdje displayLeafNodes = ( rootNode ) =>
{
ako ( ! rootNode )
povratak ;
neka lista = [ ] ;
popis. gurnuti ( rootNode ) ;
dok ( popis. duljina > 0 ) {
rootNode = popis [ popis. duljina - 1 ] ;
popis. pop ( ) ;
ako ( ! rootNode. lijevo && ! rootNode. pravo )
dokument. pisati ( rootNode. podaci + ' ' ) ;
ako ( rootNode. pravo )
popis. gurnuti ( rootNode. pravo ) ;
ako ( rootNode. lijevo )
popis. gurnuti ( rootNode. lijevo ) ;
}
}
bio rootNode = novi Čvor ( 3 ) ;
rootNode. lijevo = novi Čvor ( 6 ) ;
rootNode. pravo = novi Čvor ( 9 ) ;
rootNode. lijevo . lijevo = novi Čvor ( 12 ) ;
rootNode. lijevo . pravo = novi Čvor ( petnaest ) ;
rootNode. lijevo . pravo . pravo = novi Čvor ( 24 ) ;
rootNode. pravo . lijevo = novi Čvor ( 18 ) ;
rootNode. pravo . pravo = novi Čvor ( dvadeset i jedan ) ;
displayLeafNodes ( rootNode ) ;
Objašnjenje gornjeg koda napisano je u nastavku:
- Prvo stvorite ' Čvor ' klasa koja prima jedan parametar ' vrijednost ” koja je postavljena kao vrijednost novostvorenog čvora, a lijeva i desna strana su postavljene na null. Baš kao što je učinjeno u gornjem primjeru.
- Zatim stvorite funkciju ' displayLeafNodes() ' koji prihvaća jedan parametar od ' rootNode ”. Ovaj 'rootNode' se smatra binarnim stablom i prvo se provjerava njegova praznina.
- Ako čvor nije prazan, prazna lista pod nazivom ' popis ' se stvara i ' rootNode ” u njega se umeće parametar pomoću „ gurnuti() ” metoda.
- Onda ' dok() ' koristi se koji se izvršava do duljine ' popis ”. Unutar petlje, element koji se nalazi na dnu stabla ili ' popis ' se uklanja pomoću ' pop() ” metoda.
- Sada, postojanje ' lijevo ' i ' pravo ” strane “rootNode” se provjeravaju, a ako obje strane ne postoje, to znači da nema podređeni čvor. Zatim se ovaj čvor prikazuje preko zaslona i identificira kao listni čvor.
- Ako postoji čvor na lijevoj ili desnoj strani znači da ima potomke. Onda to ' lijevo ' i ' pravo ” čvor se gura u „ popis ” za daljnju operaciju pronalaženja čvora lista.
- Na kraju, stvorite prilagođeno binarno stablo prosljeđivanjem vrijednosti čvorova kao parametara za ' Čvor ” konstruktor klase. Nakon stvaranja, proslijedite stablo 'rootNode' kao argument za ' displayLeafNodes() ” funkcija.
Izlaz generiran nakon kompilacije pokazuje da su lisni čvorovi danog stabla ispisani:
Dodatni savjet: Ispis lisnih čvorova binarnog stabla s desna na lijevo
Za dohvaćanje svih lisnih čvorova koji nemaju podređene čvorove u ' pravo ” do “ lijevo ” smjeru, rekurzivni pristup se najviše preporučuje zbog svoje lakoće. Na primjer, isto stablo o kojem se raspravlja u gornjim odjeljcima koristit će se za dohvaćanje lisnog čvora, ali u ' pravo ' prema ' lijevo ”, kao što je prikazano u nastavku:
razreda Čvor{
konstruktor ( vrijednost )
{
ovaj . podaci = vrijednost ;
ovaj . lijevo = ništavan ;
ovaj . pravo = ništavan ;
}
} ;
funkcija displayLeafNodes ( korijen )
{
ako ( korijen == ništavan )
{
povratak ;
}
ako ( korijen. lijevo == ništavan && korijen. pravo == ništavan )
{
dokument. pisati ( korijen. podaci + ' ' ) ;
povratak ;
}
ako ( korijen. pravo != ništavan )
{
displayLeafNodes ( korijen. pravo ) ;
}
ako ( korijen. lijevo != ništavan )
{
displayLeafNodes ( korijen. lijevo ) ;
}
}
bio rootNode = novi Čvor ( 3 ) ;
rootNode. lijevo = novi Čvor ( 6 ) ;
rootNode. pravo = novi Čvor ( 9 ) ;
rootNode. lijevo . lijevo = novi Čvor ( 12 ) ;
rootNode. lijevo . pravo = novi Čvor ( petnaest ) ;
rootNode. lijevo . pravo . pravo = novi Čvor ( 24 ) ;
rootNode. pravo . lijevo = novi Čvor ( 18 ) ;
rootNode. pravo . pravo = novi Čvor ( dvadeset i jedan ) ;
displayLeafNodes ( rootNode ) ;
Gore navedeni kod radi ovako:
- Prvo, razred ' Čvor ” kreiran je koji koristi zadani konstruktor za dodavanje novog čvora u stablo samo vezu napravljenu u gornjim primjerima.
- Zatim, ' displayLeadNodes() ' stvorena je funkcija koja prihvaća jedan parametar ' rootNode ”. Ovaj parametar se provjerava za ' ništavan ' stanje putem ' ako ” izjava.
- Ako navedeni čvor nije istinit, tada je njegov ' lijevo ' i ' pravo ” bočni čvorovi se provjeravaju za “ ništavan ” stanje. Ako su oba nula, tada će čvor biti identificiran kao ' list ” čvor i ispisan preko web stranice.
- Nakon toga prođite ' pravo ' i ' lijevo ' čvorovi ' rootNode ' prema ' displayLeafNodes() ” funkcija.
- Dodijelite položaj svakom čvoru stvaranjem instanci pomoću ' novi ' ključna riječ i ' Čvor() ” konstruktor i navođenje pozicije kao parametra konstruktora.
- ' lijevo ” znači lijevi položaj korijenskog čvora i „ lijevo.lijevo ” položaj znači lijevo ili lijevo. Isti pristup primjenjuje se u slučaju ' pravo ' i ' pravo ”.
- Na kraju prođite ' rootNode ' kao argument za ' displayLeafNode() ” funkcija.
Generirani izlaz pokazuje da se lisni čvorovi ispisuju u smjeru zdesna nalijevo.
To je sve o ispisu svih lisnih čvorova binarnog stabla u bilo kojem željenom smjeru.
Zaključak
Za ispis svih lisnih čvorova binarnog stabla, stvorite slučajnu klasu koja stvara i dodjeljuje vrijednosti čvorovima stabla. Zatim stvorite nasumičnu funkciju koja prihvaća jedan čvor stabla u hijerarhiji od vrha do dna. Ova funkcija sadrži više ' ako ' uvjeti koji provjeravaju je li ' čvor ” nije prazno i nema čvorova u ” lijevo ' i ' pravo ”, onda se taj čvor smatra “ list ” čvor i prikazuje se na konzoli. Ovaj vodič je objasnio postupak ispisa svih lisnih čvorova binarnog stabla slijeva na desno ili zdesna nalijevo.