Ang visual na representasyon ng mga tinalakay na konsepto ay ipinapakita sa figure sa ibaba:
Ipinapaliwanag ng gabay na ito ang proseso ng pag-print ng lahat ng mga node ng dahon ng isang binary tree sa pamamagitan ng pagsakop sa mga nabanggit na seksyon sa ibaba:
- Paano Makikilala ang mga Leaf Node?
- Paano I-print ang lahat ng Leaf Node ng isang Binary Tree Mula Kaliwa hanggang Kanan sa JavaScript?
- Tip sa Bonus: Pagpi-print ng Mga Leaf Node ng Binary Tree Mula Kanan Patungo sa Kaliwang Direksyon
- Konklusyon
Paano Makikilala ang mga Leaf Node?
Ang ' dahon Ang mga 'node ay ang mga walang child node, o upang maging tiyak na mayroong ' taas 'ng' 0 ”. Kung ang node ay may ' taas ' mahigit sa ' 0 ” kung gayon ang node na iyon ay maaaring ang panloob na node o root node. Ang ' dahon ” Ang mga node ay karaniwang ibinabalik upang matukoy ang orihinal na pinagmulan kung saan nabuo ang node na ito. Ito ay kadalasang ginagamit sa paghahanap o error-finding algorithm upang mahanap ang sanhi ng isang error o isyu.
Paano I-print ang lahat ng Leaf Node ng isang Binary Tree Mula Kaliwa hanggang Kanan sa JavaScript?
Mayroong dalawang diskarte ' recursive 'at' umuulit ” para piliin ang lahat ng leaf node na available sa ibinigay na binary tree sa nais na “ umalis 'sa' tama ” direksyon. Ang praktikal na pagpapatupad ng mga pamamaraang ito ay ipinapakita sa mga nakasaad na seksyon sa ibaba:
- I-print ang Lahat ng Leaf Node ng isang Binary Tree Mula Kaliwa Pakanan nang Recursively
- I-print ang Lahat ng Leaf Node ng Binary Tree Gamit ang Iterative Approach
Paraan 1: I-print ang Lahat ng Leaf Node ng isang Binary Tree Mula Kaliwa Pakanan Recursively
Pinipili ng recursive approach ang lahat ng node sa a depth-first search algorithm paraan na unang tumawid sa buong kaliwang bahagi ng mga node pagkatapos ay sa gitnang node at sa kanang bahagi ng mga node sa dulo. Ang operasyong ito ay isinasagawa nang paulit-ulit para sa bawat node at kapag wala nang lampasan ang ' dahon ” makikilala ang mga node. Upang mas maunawaan ang konseptong ito, bisitahin ang snippet ng code sa ibaba:
klase Node{
tagabuo ( )
{
ito . nilalaman = 0 ;
ito . umalis = wala ;
ito . tama = wala ;
}
} ;
kung saan ang displayLeafNodes = ( rootNode ) =>
{
kung ( rootNode == wala )
bumalik ;
kung ( rootNode. umalis == wala && rootNode. tama == wala )
{
dokumento. magsulat ( rootNode. nilalaman + '' ) ;
bumalik ;
}
kung ( rootNode. umalis != wala )
displayLeafNodes ( rootNode. umalis ) ;
kung ( rootNode. tama != wala )
displayLeafNodes ( rootNode. tama ) ;
}
ay sampleNode = ( val ) =>
{
ay tempNode = bago Node ( ) ;
tempNode. nilalaman = val ;
tempNode. umalis = wala ;
tempNode. tama = wala ;
bumalik tempNode ;
}
ay rootNode = provNode ( 3 ) ;
rootNode. umalis = provNode ( 6 ) ;
rootNode. tama = provNode ( 9 ) ;
rootNode. umalis . umalis = provNode ( 12 ) ;
rootNode. umalis . tama = provNode ( labinlima ) ;
rootNode. umalis . tama . tama = provNode ( 24 ) ;
rootNode. tama . umalis = provNode ( 18 ) ;
rootNode. tama . tama = provNode ( dalawampu't isa ) ;
displayLeafNodes ( rootNode ) ;
Ang paliwanag ng bloke ng code sa itaas ay nakasaad sa ibaba:
- Una, lumikha ng isang klase na pinangalanang ' node ”, na lumilikha ng bagong node at nagtatakda ng halaga nito sa “ 0 ”. Ang kalakip na ' umalis 'at' tama 'Ang mga side node ay nakatakda sa ' wala ” bilang default gamit ang tagabuo ng klase.
- Susunod, tukuyin ang isang ' displayLeafNodes() ” function na tumatanggap ng isang parameter ng “ rootNode ”. Ang parametric value na ito ay itinuturing na kasalukuyang napiling node ng isang binary tree.
- Sa loob ng function, ang ' kung 'Ang pahayag ay ginagamit upang suriin kung ang ' rootNode ” ay null o hindi. Sa kaso ng ' wala ” huminto ang karagdagang execution para sa node na iyon. Sa kabilang kaso, ang rootNode ' umalis 'at' tama 'Ang mga side node ay sinusuri para sa' wala ”. Kung pareho ay null, ang halaga ng ' node ” nalilimbag.
- kung ang ' umalis 'o' tama ' ang node ay hindi 'null', pagkatapos ay ipasa ang bahaging iyon ng node sa ' displayLeafNodes() ” function para sa recursive na operasyon.
- Tukuyin ang isang bagong function na pinangalanang ' provNode() ' na tumatanggap ng solong parameter ng ' val ”. Sa loob ng function ay lumikha ng isang bagong halimbawa ng ' Node 'class na pinangalanan' tempNode ”. Italaga ang parametric ' val 'bilang halaga para sa pag-aari ng klase ' nilalaman 'at itakda ang' umalis 'at' tama 'mga side node sa' wala ” bilang default.
- Sa wakas, lumikha ng isang bagay na pinangalanang ' rootNode ' para sa ' provNode() ” function at ipasa ang halaga ng node bilang parameter ng function na ito. Lumikha ng kaliwa at kanang bahagi ng mga node sa pamamagitan ng pagdaragdag ng “ umalis 'at' tama ” mga keyword na may “rootNode” at italaga ang mga ito ng halaga gamit ang parehong function na “ provNode() ”.
- Ang ' umalis ” ay nangangahulugang ang kaliwang posisyon ng root node at ang “ kaliwa.kaliwa Ang ibig sabihin ng posisyon ay kaliwa ng kaliwa ang parehong diskarte ay inilapat sa kaso ng ' tama 'at' tama ”
- Pagkatapos tukuyin ang puno, ipasa ang 'rootNode' bilang argumento para sa ' displayLeadNodes() ” function upang piliin at i-print ang lahat ng mga node ng dahon ng nilikhang puno.
Kinukumpirma ng output na nabuo pagkatapos ng compilation na ang leaf node ng ibinigay na puno ay nakuha at na-print sa ibabaw ng console:
Paraan 2: I-print ang Lahat ng Leaf Node ng Binary Tree Gamit ang Iterative Approach
Ang ' umuulit Ang diskarte ay ang pinaka mahusay na diskarte, ginagamit nito ang konsepto ng ' itulak 'at' pop ” para piliin ang “ dahon ” mga node. Ang mga pangunahing punto o gumagana ng diskarteng ito ay nakasaad sa ibaba:
klase Node{
tagabuo ( halaga )
{
ito . datos = halaga ;
ito . umalis = wala ;
ito . tama = wala ;
}
} ;
kung saan ang displayLeafNodes = ( rootNode ) =>
{
kung ( ! rootNode )
bumalik ;
hayaan mong ilista = [ ] ;
listahan. itulak ( rootNode ) ;
habang ( listahan. haba > 0 ) {
rootNode = listahan [ listahan. haba - 1 ] ;
listahan. pop ( ) ;
kung ( ! rootNode. umalis && ! rootNode. tama )
dokumento. magsulat ( rootNode. datos + '' ) ;
kung ( rootNode. tama )
listahan. itulak ( rootNode. tama ) ;
kung ( rootNode. umalis )
listahan. itulak ( rootNode. umalis ) ;
}
}
ay rootNode = bago Node ( 3 ) ;
rootNode. umalis = bago Node ( 6 ) ;
rootNode. tama = bago Node ( 9 ) ;
rootNode. umalis . umalis = bago Node ( 12 ) ;
rootNode. umalis . tama = bago Node ( labinlima ) ;
rootNode. umalis . tama . tama = bago Node ( 24 ) ;
rootNode. tama . umalis = bago Node ( 18 ) ;
rootNode. tama . tama = bago Node ( dalawampu't isa ) ;
displayLeafNodes ( rootNode ) ;
Ang paliwanag ng code sa itaas ay nakasulat sa ibaba:
- Una, lumikha ng ' Node 'class na tumatanggap ng isang parameter' halaga ” na itinakda bilang halaga ng bagong likhang node, at ang kaliwa at kanang bahagi ay nakatakda sa null. Katulad ng ginawa sa halimbawa sa itaas.
- Susunod, lumikha ng isang function na ' displayLeafNodes() ' na tumatanggap ng isang parameter ng ' rootNode ”. Ang 'rootNode' na ito ay itinuturing na binary tree at ang kawalan ng laman nito ay unang sinusuri.
- Kung ang node ay walang laman, pagkatapos ay isang walang laman na listahan na pinangalanang ' listahan ' ay nilikha at ang ' rootNode 'Ang parameter ay ipinasok dito gamit ang ' push() ” paraan.
- Pagkatapos, ang ' habang() ' ay ginagamit na nagsasagawa hanggang sa haba ng isang ' listahan ”. Sa loob ng loop, ang elementong naninirahan sa ilalim ng isang puno o ' listahan 'tinatanggal gamit ang ' pop() ” paraan.
- Ngayon, ang pagkakaroon ng ' umalis 'at' tama ” ang mga gilid ng “rootNode” ay may check, at kung ang magkabilang panig ay hindi umiiral, nangangahulugan ito na wala itong child node. Pagkatapos, ang node na ito ay ipapakita sa screen at makikilala bilang isang leaf node.
- Kung may node sa kaliwa o kanang bahagi ay nangangahulugang mayroon itong mga anak. Tapos iyon ' umalis 'at' tama ' itinutulak ang node sa ' listahan ” para sa karagdagang operasyon ng paghahanap ng leaf node.
- Sa huli, lumikha ng custom na binary tree sa pamamagitan ng pagpasa sa mga halaga ng node bilang mga parameter para sa “ Node ” tagabuo ng klase. Pagkatapos ng paglikha, ipasa ang punong 'rootNode' bilang argumento para sa ' displayLeafNodes() ” function.
Ang output na nabuo pagkatapos ng compilation ay nagpapakita na ang mga leaf node ng ibinigay na puno ay naka-print:
Tip sa Bonus: Pagpi-print ng Mga Leaf Node ng Binary Tree Mula Kanan Patungo sa Kaliwang Direksyon
Upang kunin ang lahat ng leaf node na walang child node sa ' tama 'sa' umalis ” direksyon, ang recursive na diskarte ay ang pinaka inirerekomenda dahil sa kadalian nito. Halimbawa, ang parehong punong tinalakay sa mga seksyon sa itaas ay gagamitin upang kunin ang leaf node ngunit sa ' tama ' sa ' umalis ” direksyon, tulad ng ipinapakita sa ibaba:
klase Node{
tagabuo ( halaga )
{
ito . datos = halaga ;
ito . umalis = wala ;
ito . tama = wala ;
}
} ;
function displayLeafNodes ( ugat )
{
kung ( ugat == wala )
{
bumalik ;
}
kung ( ugat. umalis == wala && ugat. tama == wala )
{
dokumento. magsulat ( ugat. datos + '' ) ;
bumalik ;
}
kung ( ugat. tama != wala )
{
displayLeafNodes ( ugat. tama ) ;
}
kung ( ugat. umalis != wala )
{
displayLeafNodes ( ugat. umalis ) ;
}
}
ay rootNode = bago Node ( 3 ) ;
rootNode. umalis = bago Node ( 6 ) ;
rootNode. tama = bago Node ( 9 ) ;
rootNode. umalis . umalis = bago Node ( 12 ) ;
rootNode. umalis . tama = bago Node ( labinlima ) ;
rootNode. umalis . tama . tama = bago Node ( 24 ) ;
rootNode. tama . umalis = bago Node ( 18 ) ;
rootNode. tama . tama = bago Node ( dalawampu't isa ) ;
displayLeafNodes ( rootNode ) ;
Ang code sa itaas ay gumagana tulad nito:
- Una, ang klase ' Node ” ay nilikha na gumagamit ng default na tagabuo upang magdagdag ng bagong node sa puno lamang ang link na ginawa sa mga halimbawa sa itaas.
- Susunod, ang ' displayLeadNodes() Ang function na ” ay nilikha na tumatanggap ng isang parameter ng “ rootNode ”. Ang parameter na ito ay sinuri para sa ' wala 'kondisyon sa pamamagitan ng' kung ” pahayag.
- Kung ang ibinigay na node ay hindi totoo, kung gayon ang ' umalis 'at' tama 'Ang mga side node ay sinusuri para sa' wala ' kundisyon. Kung pareho ay null, ang node ay makikilala bilang ' dahon ” node at naka-print sa webpage.
- Pagkatapos nito, ipasa ang ' tama 'at' umalis 'mga node ng' rootNode ' sa ' displayLeafNodes() ” function.
- Ilaan ang posisyon ng bawat node sa pamamagitan ng paglikha ng mga pagkakataon gamit ang “ bago 'keyword at ang' Node() ” constructor at tinukoy ang posisyon bilang parameter ng constructor.
- Ang ' umalis ” ay nangangahulugang ang kaliwang posisyon ng root node at ang “ kaliwa.kaliwa ” ang ibig sabihin ng posisyon ay kaliwa o kaliwa. Ang parehong diskarte ay inilapat sa kaso ng ' tama 'at' tama ”.
- Sa wakas, ipasa ang ' rootNode 'bilang argumento para sa' displayLeafNode() ” function.
Ang nabuong output ay nagpapakita na ang mga leaf node ay naka-print sa kanan-papuntang-kaliwa na direksyon.
Iyon lang ang tungkol sa pag-print ng lahat ng mga node ng dahon ng isang binary tree sa anumang nais na direksyon.
Konklusyon
Upang i-print ang lahat ng mga node ng dahon ng isang binary tree, lumikha ng isang random na klase na lumilikha at nagtatalaga ng mga halaga sa mga node ng puno. Susunod, lumikha ng isang random na function na tumatanggap ng isang node ng puno sa isang top-to-bottom hierarchy. Ang function na ito ay naglalaman ng maramihang ' kung 'mga kundisyon na nagsusuri kung ang ' node Ang ” ay walang laman at wala itong mga node sa “ umalis 'at' tama ” direksyon, kung gayon ang node na iyon ay itinuturing bilang isang “ dahon ” node at ipinapakita sa console. Ipinaliwanag ng gabay na ito ang pamamaraan ng pag-print ng lahat ng leaf node ng isang binary tree mula kaliwa pakanan o kanan papuntang kaliwang direksyon.