Perwakilan visual konsep yang dibincangkan ditunjukkan dalam rajah di bawah:
Panduan ini menerangkan proses mencetak semua nod daun pokok binari dengan merangkumi bahagian yang disebutkan di bawah:
- Bagaimana Mengenalpasti Nod Daun?
- Bagaimana untuk Mencetak semua Nod Daun Pokok Binari Dari Kiri ke Kanan dalam JavaScript?
- Petua Bonus: Mencetak Nod Daun Pokok Binari Dari Arah Kanan ke Kiri
- Kesimpulan
Bagaimana Mengenalpasti Nod Daun?
' daun ' nod ialah nod yang tidak mempunyai nod anak, atau lebih khusus yang mempunyai ' ketinggian 'daripada' 0 ”. Jika nod mempunyai ' ketinggian ' lebih besar daripada ' 0 ” maka nod itu boleh menjadi nod dalam atau nod akar. ' daun ” nod biasanya diundur untuk mengenal pasti sumber asal dari mana nod ini dijana. Ia kebanyakannya digunakan dalam pencarian atau algoritma mencari ralat untuk mencari punca ralat atau isu.
Bagaimana untuk Mencetak semua Nod Daun Pokok Binari Dari Kiri ke Kanan dalam JavaScript?
Terdapat dua pendekatan ' rekursif ” dan “ berulang ' untuk memilih semua nod daun yang tersedia dalam pokok binari yang disediakan dalam yang dikehendaki ' dibiarkan ” kepada “ betul ” arah. Pelaksanaan praktikal pendekatan ini ditunjukkan dalam bahagian yang dinyatakan di bawah:
- Cetak Semua Nod Daun Pokok Binari Dari Kiri ke Kanan Secara Rekursif
- Cetak Semua Nod Daun Pokok Binari Menggunakan Pendekatan Berulang
Kaedah 1: Cetak Semua Nod Daun Pokok Binari Dari Kiri ke Kanan Secara Rekursif
Pendekatan rekursif memilih semua nod dalam a algoritma carian mendalam-pertama cara yang pertama melintasi seluruh nod sebelah kiri kemudian nod tengah dan nod sebelah kanan pada akhirnya. Operasi ini dilakukan secara rekursif untuk setiap nod dan apabila tiada lagi melintasi ' daun ” nod dikenal pasti. Untuk lebih memahami konsep ini, lawati coretan kod di bawah:
kelas Nod{
pembina ( )
{
ini . kandungan = 0 ;
ini . dibiarkan = null ;
ini . betul = null ;
}
} ;
di mana paparanLeafNodes = ( rootNode ) =>
{
jika ( rootNode == null )
kembali ;
jika ( rootNode. dibiarkan == null && rootNode. betul == null )
{
dokumen. menulis ( rootNode. kandungan + ' ' ) ;
kembali ;
}
jika ( rootNode. dibiarkan != null )
paparanLeafNodes ( rootNode. dibiarkan ) ;
jika ( rootNode. betul != null )
paparanLeafNodes ( rootNode. betul ) ;
}
ialah sampleNode = ( val ) =>
{
ialah tempNode = baru Nod ( ) ;
tempNode. kandungan = val ;
tempNode. dibiarkan = null ;
tempNode. betul = null ;
kembali tempNode ;
}
ialah rootNode = provNode ( 3 ) ;
rootNode. dibiarkan = provNode ( 6 ) ;
rootNode. betul = provNode ( 9 ) ;
rootNode. dibiarkan . dibiarkan = provNode ( 12 ) ;
rootNode. dibiarkan . betul = provNode ( lima belas ) ;
rootNode. dibiarkan . betul . betul = provNode ( 24 ) ;
rootNode. betul . dibiarkan = provNode ( 18 ) ;
rootNode. betul . betul = provNode ( dua puluh satu ) ;
paparanLeafNodes ( rootNode ) ;
Penjelasan blok kod di atas dinyatakan di bawah:
- Mula-mula, buat kelas bernama ' nod ”, yang mencipta nod baharu dan menetapkan nilainya kepada “ 0 ”. yang dilampirkan ' dibiarkan ” dan “ betul ” nod sisi ditetapkan kepada “ null ” secara lalai menggunakan pembina kelas.
- Seterusnya, tentukan ' paparanLeafNodes() fungsi ' yang menerima satu parameter ' rootNode ”. Nilai parametrik ini dianggap sebagai nod pokok binari yang dipilih pada masa ini.
- Di dalam fungsi, ' jika pernyataan ' digunakan untuk menyemak sama ada ' rootNode ” adalah batal atau tidak. Dalam kes ' null ” pelaksanaan selanjutnya dihentikan untuk nod itu. Dalam kes lain, rootNode ' dibiarkan ” dan “ betul 'nod sisi diperiksa untuk ' null ”. Jika kedua-duanya adalah batal, nilai ' nod ” akan dicetak.
- Jika ' dibiarkan ” atau “ betul ” nod bukan “null”, kemudian hantar sisi nod itu ke “ paparanLeafNodes() ” fungsi untuk operasi rekursif.
- Tentukan fungsi baharu bernama “ ProvNode() ' yang menerima parameter tunggal ' val ”. Di dalam fungsi buat contoh baharu ' Nod 'kelas bernama' tempNode ”. Tetapkan parametrik ' val ' sebagai nilai untuk harta kelas ' kandungan ” dan tetapkan “ dibiarkan ” dan “ betul ” nod sisi kepada “ null ” secara lalai.
- Akhir sekali, buat objek bernama ' rootNode 'untuk' ProvNode() ” dan lulus nilai nod sebagai parameter fungsi ini. Buat nod sebelah kiri dan kanan dengan menambah “ dibiarkan ” dan “ betul ' kata kunci dengan 'rootNode' dan berikan mereka nilai menggunakan fungsi yang sama ' ProvNode() ”.
- ' dibiarkan ” bermaksud kedudukan kiri nod akar dan “ kiri.kiri Kedudukan ” bermaksud kiri kiri pendekatan yang sama digunakan dalam kes “ betul ” dan “ betul ”
- Selepas mentakrifkan pokok, luluskan 'rootNode' sebagai hujah untuk ' displayLeadNodes() ” fungsi untuk memilih dan mencetak semua nod daun pokok yang dicipta.
Output yang dijana selepas kompilasi mengesahkan bahawa nod daun pokok yang disediakan telah diambil dan dicetak di atas konsol:
Kaedah 2: Cetak Semua Nod Daun Pokok Binari Menggunakan Pendekatan Berulang
' berulang 'pendekatan adalah pendekatan yang paling cekap, ia menggunakan konsep ' menolak ” dan “ pop ” untuk memilih “ daun ” nod. Perkara utama atau kerja pendekatan ini dinyatakan di bawah:
kelas Nod{
pembina ( nilai )
{
ini . data = nilai ;
ini . dibiarkan = null ;
ini . betul = null ;
}
} ;
di mana paparanLeafNodes = ( rootNode ) =>
{
jika ( ! rootNode )
kembali ;
mari senaraikan = [ ] ;
senarai. menolak ( rootNode ) ;
sementara ( senarai. panjang > 0 ) {
rootNode = senarai [ senarai. panjang - 1 ] ;
senarai. pop ( ) ;
jika ( ! rootNode. dibiarkan && ! rootNode. betul )
dokumen. menulis ( rootNode. data + ' ' ) ;
jika ( rootNode. betul )
senarai. menolak ( rootNode. betul ) ;
jika ( rootNode. dibiarkan )
senarai. menolak ( rootNode. dibiarkan ) ;
}
}
ialah rootNode = baru Nod ( 3 ) ;
rootNode. dibiarkan = baru Nod ( 6 ) ;
rootNode. betul = baru Nod ( 9 ) ;
rootNode. dibiarkan . dibiarkan = baru Nod ( 12 ) ;
rootNode. dibiarkan . betul = baru Nod ( lima belas ) ;
rootNode. dibiarkan . betul . betul = baru Nod ( 24 ) ;
rootNode. betul . dibiarkan = baru Nod ( 18 ) ;
rootNode. betul . betul = baru Nod ( dua puluh satu ) ;
paparanLeafNodes ( rootNode ) ;
Penjelasan kod di atas ditulis di bawah:
- Pertama, buat ' Nod 'kelas yang menerima satu parameter' nilai ” yang ditetapkan sebagai nilai nod yang baru dibuat, dan bahagian kiri dan kanan ditetapkan kepada null. Sama seperti yang dilakukan dalam contoh di atas.
- Seterusnya, buat fungsi ' paparanLeafNodes() ' yang menerima satu parameter ' rootNode ”. 'rootNode' ini dianggap sebagai pokok binari dan kekosongannya diperiksa terlebih dahulu.
- Jika nod tidak kosong, maka senarai kosong bernama “ senarai ' dicipta dan ' rootNode parameter ' dimasukkan ke dalamnya menggunakan ' tolak() ” kaedah.
- Kemudian, ' sambil() ' digunakan yang melaksanakan sehingga panjang ' senarai ”. Di dalam gelung, elemen yang berada di bahagian bawah pokok atau “ senarai ” dialih keluar menggunakan “ pop() ” kaedah.
- Kini, kewujudan “ dibiarkan ” dan “ betul ” sisi “rootNode” ditandakan, dan jika kedua-dua belah tidak wujud ia bermakna ia tidak mempunyai nod anak. Kemudian, nod ini akan dipaparkan pada skrin dan dikenal pasti sebagai nod daun.
- Jika terdapat nod di sebelah kiri atau kanan bermakna ia mempunyai anak. Kemudian itu ' dibiarkan ” dan “ betul 'nod ditolak ke dalam' senarai ” untuk operasi selanjutnya mencari nod daun.
- Pada akhirnya, cipta pepohon binari tersuai dengan menghantar nilai nod sebagai parameter untuk ' Nod ” pembina kelas. Selepas penciptaan, hantar pokok 'rootNode' sebagai hujah untuk ' paparanLeafNodes() ” fungsi.
Output yang dihasilkan selepas kompilasi menunjukkan bahawa nod daun pokok yang disediakan dicetak:
Petua Bonus: Mencetak Nod Daun Pokok Binari Dari Arah Kanan ke Kiri
Untuk mendapatkan semula semua nod daun yang tidak mempunyai nod anak dalam “ betul ” kepada “ dibiarkan ” arah, pendekatan rekursif adalah yang paling disyorkan kerana kemudahannya. Sebagai contoh, pokok yang sama yang dibincangkan dalam bahagian di atas akan digunakan untuk mendapatkan nod daun tetapi dalam ' betul ' kepada ' dibiarkan ” arah, seperti yang ditunjukkan di bawah:
kelas Nod{
pembina ( nilai )
{
ini . data = nilai ;
ini . dibiarkan = null ;
ini . betul = null ;
}
} ;
fungsi paparanLeafNodes ( akar )
{
jika ( akar == null )
{
kembali ;
}
jika ( akar. dibiarkan == null && akar. betul == null )
{
dokumen. menulis ( akar. data + ' ' ) ;
kembali ;
}
jika ( akar. betul != null )
{
paparanLeafNodes ( akar. betul ) ;
}
jika ( akar. dibiarkan != null )
{
paparanLeafNodes ( akar. dibiarkan ) ;
}
}
ialah rootNode = baru Nod ( 3 ) ;
rootNode. dibiarkan = baru Nod ( 6 ) ;
rootNode. betul = baru Nod ( 9 ) ;
rootNode. dibiarkan . dibiarkan = baru Nod ( 12 ) ;
rootNode. dibiarkan . betul = baru Nod ( lima belas ) ;
rootNode. dibiarkan . betul . betul = baru Nod ( 24 ) ;
rootNode. betul . dibiarkan = baru Nod ( 18 ) ;
rootNode. betul . betul = baru Nod ( dua puluh satu ) ;
paparanLeafNodes ( rootNode ) ;
Kod yang dinyatakan di atas berfungsi seperti ini:
- Pertama, kelas ' Nod ” dicipta yang menggunakan pembina lalai untuk menambah nod baharu dalam pepohon hanya pautan yang dilakukan dalam contoh di atas.
- Seterusnya, ' displayLeadNodes() fungsi ” dicipta yang menerima satu parameter “ rootNode ”. Parameter ini disemak untuk ' null ” syarat melalui “ jika ” kenyataan.
- Jika nod yang disediakan tidak benar, maka ' dibiarkan ” dan “ betul 'nod sisi diperiksa untuk ' null ” syarat. Jika kedua-duanya adalah nol, maka nod akan dikenal pasti sebagai “ daun ” nod dan dicetak di atas halaman web.
- Selepas itu, lulus ' betul ” dan “ dibiarkan 'nod' rootNode ' kepada ' paparanLeafNodes() ” fungsi.
- Peruntukkan kedudukan setiap nod dengan mencipta kejadian menggunakan ' baru ' kata kunci dan ' Nod() ” pembina dan menentukan kedudukan sebagai parameter pembina.
- ' dibiarkan ” bermaksud kedudukan kiri nod akar dan “ kiri.kiri ” kedudukan bermaksud kiri atau kiri. Pendekatan yang sama digunakan dalam kes ' betul ” dan “ betul ”.
- Akhirnya, lulus ' rootNode 'sebagai hujah untuk' displayLeafNode() ” fungsi.
Output yang dihasilkan menunjukkan bahawa nod daun dicetak dalam arah kanan ke kiri.
Itu sahaja tentang mencetak semua nod daun pokok binari ke mana-mana arah yang dikehendaki.
Kesimpulan
Untuk mencetak semua nod daun pokok binari, cipta kelas rawak yang mencipta dan memberikan nilai kepada nod pokok. Seterusnya, cipta fungsi rawak yang menerima satu nod pokok dalam hierarki atas ke bawah. Fungsi ini mengandungi berbilang ' jika ' syarat yang memeriksa sama ada ' nod ' tidak kosong dan ia tidak mempunyai nod dalam ' dibiarkan ” dan “ betul ' arah, maka nod itu dianggap sebagai ' daun ” nod dan dipaparkan pada konsol. Panduan ini telah menerangkan prosedur mencetak semua nod daun pokok binari dari kiri ke kanan atau kanan ke kiri.