Tartışılan kavramların görsel temsili aşağıdaki şekilde gösterilmektedir:
Bu kılavuz, aşağıdaki bölümleri kapsayarak bir ikili ağacın tüm yaprak düğümlerinin yazdırılma sürecini açıklamaktadır:
- Yaprak Düğümleri Nasıl Tanımlanır?
- JavaScript'te İkili Ağacın Tüm Yaprak Düğümlerini Soldan Sağa Nasıl Yazdırabilirim?
- Bonus İpucu: İkili Ağacın Yaprak Düğümlerini Sağdan Sola Yazdırma
- Çözüm
Yaprak Düğümleri Nasıl Tanımlanır?
“ yaprak ” düğümleri, alt düğümleri olmayan veya daha spesifik olmak gerekirse “ yükseklik ' ile ilgili ' 0 ”. Düğümün bir “ yükseklik ' daha büyük ' 0 ” o zaman bu düğüm iç düğüm veya kök düğüm olabilir. “ yaprak Düğümler genellikle bu düğümün oluşturulduğu orijinal kaynağı belirlemek için geriye doğru izlenir. Çoğunlukla bir hatanın veya sorunun nedenini bulmak için arama veya hata bulma algoritmalarında kullanılır.
JavaScript'te İkili Ağacın Tüm Yaprak Düğümlerini Soldan Sağa Nasıl Yazdırabilirim?
İki yaklaşım var” özyinelemeli ' Ve ' yinelemeli ” istenilen şekilde sağlanan ikili ağaçta bulunan tüm yaprak düğümleri seçmek için sol ' ile ' Sağ ' yön. Bu yaklaşımların pratik uygulaması aşağıdaki bölümlerde gösterilmektedir:
- Bir İkili Ağacın Tüm Yaprak Düğümlerini Soldan Sağa Yinelemeli Olarak Yazdır
- Yinelemeli Yaklaşımı Kullanarak İkili Ağacın Tüm Yaprak Düğümlerini Yazdırma
Yöntem 1: İkili Ağacın Tüm Yaprak Düğümlerini Soldan Sağa Yinelemeli Olarak Yazdır
Özyinelemeli yaklaşım bir dizideki tüm düğümleri seçer. derinlik öncelikli arama algoritması Bu yöntem ilk olarak sol taraftaki düğümlerin tamamını, ardından ortadaki düğümü ve son olarak da sağ taraftaki düğümleri geçer. Bu işlem her düğüm için yinelemeli olarak ve daha fazla geçiş olmadığında gerçekleştirilir. yaprak ” düğümleri tanımlanır. Bu kavramı daha iyi anlamak için aşağıdaki kod parçacığını ziyaret edin:
sınıf Düğüm{
yapıcı ( )
{
Bu . içerik = 0 ;
Bu . sol = hükümsüz ;
Bu . Sağ = hükümsüz ;
}
} ;
displayLeafNodes nerede = ( kökDüğüm ) =>
{
eğer ( kökDüğüm == hükümsüz )
geri dönmek ;
eğer ( rootNode. sol == hükümsüz && rootNode. Sağ == hükümsüz )
{
belge. yazmak ( rootNode. içerik + ' ' ) ;
geri dönmek ;
}
eğer ( rootNode. sol != hükümsüz )
displayLeafNode'lar ( rootNode. sol ) ;
eğer ( rootNode. Sağ != hükümsüz )
displayLeafNode'lar ( rootNode. Sağ ) ;
}
sampleNode idi = ( val ) =>
{
tempNode'du = yeni Düğüm ( ) ;
tempNode. içerik = val ;
tempNode. sol = hükümsüz ;
tempNode. Sağ = hükümsüz ;
geri dönmek tempNode ;
}
rootNode idi = proNode ( 3 ) ;
rootNode. sol = proNode ( 6 ) ;
rootNode. Sağ = proNode ( 9 ) ;
rootNode. sol . sol = proNode ( 12 ) ;
rootNode. sol . Sağ = proNode ( on beş ) ;
rootNode. sol . Sağ . Sağ = proNode ( 24 ) ;
rootNode. Sağ . sol = proNode ( 18 ) ;
rootNode. Sağ . Sağ = proNode ( yirmi bir ) ;
displayLeafNode'lar ( kökDüğüm ) ;
Yukarıdaki kod bloğunun açıklaması aşağıda belirtilmiştir:
- Öncelikle “adlı bir sınıf oluşturun. düğüm ”, bu yeni bir düğüm oluşturur ve değerini “ 0 ”. Ekte yer alan “ sol ' Ve ' Sağ ” yan düğümler “ olarak ayarlandı hükümsüz ” varsayılan olarak sınıf yapıcısını kullanır.
- Daha sonra bir ' tanımlayın displayLeafNodes() ' tek bir parametreyi kabul eden ' işlevi kökDüğüm ”. Bu parametrik değer, ikili ağacın o anda seçili düğümü olarak kabul edilir.
- Fonksiyonun içinde “ eğer ' ifadesi olup olmadığını kontrol etmek için kullanılır. kökDüğüm ” null veya değil. Bu durumuda ' hükümsüz ” o düğüm için daha fazla yürütme durduruldu. Diğer durumda, rootNode “ sol ' Ve ' Sağ ” yan düğümler kontrol edilir” hükümsüz ”. Her ikisi de null ise bunun değeri “ düğüm ” basılıyor.
- Eğer ' sol ' veya ' Sağ ” düğümü “null” değilse, o zaman düğümün o tarafını “ displayLeafNodes() Özyinelemeli işlem için ” işlevi.
- “adında yeni bir işlev tanımlayın proNode() ' tek parametresini kabul eden ' val ”. Fonksiyonun içinde '' ifadesinin yeni bir örneğini yaratın. Düğüm “sınıf” adı tempNode ”. Parametriği atayın ' val “sınıf özelliğinin değeri olarak” içerik ” ve “ sol ' Ve ' Sağ ” yan düğümleri “ hükümsüz ' varsayılan olarak.
- Son olarak “adlı bir nesne oluşturun. kökDüğüm ' için ' proNode() ” fonksiyonunu kullanın ve düğüm değerini bu fonksiyon parametresi olarak iletin. '' ekleyerek sol ve sağ taraftaki düğümleri oluşturun. sol ' Ve ' Sağ “rootNode” anahtar kelimelerini kullanın ve aynı işlevi kullanarak onlara değer atayın “ proNode() ”.
- “ sol ” kök düğümün sol konumu anlamına gelir ve “ sol sol ' konumu, soldan sola anlamına gelir, ' durumunda aynı yaklaşım uygulanır Sağ ' Ve ' Sağ ”
- Ağacı tanımladıktan sonra “rootNode”u “” için argüman olarak iletin. displayLeadNodes() Oluşturulan ağacın tüm yaprak düğümlerini seçip yazdırmak için ” işlevi.
Derleme sonrasında oluşturulan çıktı, sağlanan ağacın yaprak düğümünün alındığını ve konsol üzerinden yazdırıldığını doğrular:
Yöntem 2: Yinelemeli Yaklaşımı Kullanarak İkili Ağacın Tüm Yaprak Düğümlerini Yazdırma
“ yinelemeli yaklaşımı en verimli yaklaşımdır, “kavramını kullanır” itmek ' Ve ' pop “ seçeneğini seçmek için yaprak ” düğümleri. Bu yaklaşımın kilit noktaları veya işleyişi aşağıda belirtilmiştir:
sınıf Düğüm{
yapıcı ( değer )
{
Bu . veri = değer ;
Bu . sol = hükümsüz ;
Bu . Sağ = hükümsüz ;
}
} ;
displayLeafNodes nerede = ( kökDüğüm ) =>
{
eğer ( ! kökDüğüm )
geri dönmek ;
listeleyelim = [ ] ;
liste. itmek ( kökDüğüm ) ;
sırasında ( liste. uzunluk > 0 ) {
kökDüğüm = liste [ liste. uzunluk - 1 ] ;
liste. pop ( ) ;
eğer ( ! rootNode. sol && ! rootNode. Sağ )
belge. yazmak ( rootNode. veri + ' ' ) ;
eğer ( rootNode. Sağ )
liste. itmek ( rootNode. Sağ ) ;
eğer ( rootNode. sol )
liste. itmek ( rootNode. sol ) ;
}
}
rootNode idi = yeni Düğüm ( 3 ) ;
rootNode. sol = yeni Düğüm ( 6 ) ;
rootNode. Sağ = yeni Düğüm ( 9 ) ;
rootNode. sol . sol = yeni Düğüm ( 12 ) ;
rootNode. sol . Sağ = yeni Düğüm ( on beş ) ;
rootNode. sol . Sağ . Sağ = yeni Düğüm ( 24 ) ;
rootNode. Sağ . sol = yeni Düğüm ( 18 ) ;
rootNode. Sağ . Sağ = yeni Düğüm ( yirmi bir ) ;
displayLeafNode'lar ( kökDüğüm ) ;
Yukarıdaki kodun açıklaması aşağıda yazılmıştır:
- İlk önce bir ' Düğüm “tek parametre alan sınıf” değer ” yeni oluşturulan düğümün değeri olarak ayarlanır ve sol ve sağ taraflar null olarak ayarlanır. Tıpkı yukarıdaki örnekte yapıldığı gibi.
- Daha sonra bir işlev oluşturun ' displayLeafNodes() ' tek bir parametreyi kabul eden ' kökDüğüm ”. Bu “rootNode” ikili ağaç olarak kabul edilir ve ilk önce boşluğu kontrol edilir.
- Düğüm boş değilse “adlı boş bir liste” liste ” oluşturulur ve “ kökDüğüm ” parametresi “ kullanılarak eklenir. itmek() ' yöntem.
- Sonra ' sırasında() ' uzunluğuna kadar çalıştırılan ' kullanılır liste ”. Döngünün içinde, bir ağacın altında bulunan öğe veya “ liste ”,“ kullanılarak kaldırılır pop() ' yöntem.
- Artık varlığı “ sol ' Ve ' Sağ “rootNode”un “tarafları işaretlidir, her iki taraf da yoksa alt düğümü yok demektir. Daha sonra bu düğüm ekranda görüntülenir ve yaprak düğüm olarak tanımlanır.
- Sol veya sağ tarafta bir düğüm varsa çocukları var demektir. Sonra bu ' sol ' Ve ' Sağ ” düğümü “ içine itilir liste ” yaprak düğümünü bulmanın daha ileri işlemleri için.
- Sonunda, düğüm değerlerini '' için parametre olarak ileterek özel bir ikili ağaç oluşturun. Düğüm ” sınıf yapıcısı. Oluşturulduktan sonra “rootNode” ağacını “” için argüman olarak iletin. displayLeafNodes() ' işlev.
Derleme sonrasında oluşturulan çıktı, sağlanan ağacın yaprak düğümlerinin yazdırıldığını gösterir:
Bonus İpucu: İkili Ağacın Yaprak Düğümlerini Sağdan Sola Yazdırma
Alt düğümleri olmayan tüm yaprak düğümleri almak için ' Sağ ' ile ' sol ” yönünde, özyinelemeli yaklaşım kolaylığı nedeniyle en çok tavsiye edilen yaklaşımdır. Örneğin, yukarıdaki bölümlerde tartışılan ağacın aynısı yaprak düğümünü almak için kullanılacaktır ancak “ Sağ 'e' sol ” yönünde, aşağıda gösterildiği gibi:
sınıf Düğüm{
yapıcı ( değer )
{
Bu . veri = değer ;
Bu . sol = hükümsüz ;
Bu . Sağ = hükümsüz ;
}
} ;
işlev ekranıLeafNodes ( kök )
{
eğer ( kök == hükümsüz )
{
geri dönmek ;
}
eğer ( kök. sol == hükümsüz && kök. Sağ == hükümsüz )
{
belge. yazmak ( kök. veri + ' ' ) ;
geri dönmek ;
}
eğer ( kök. Sağ != hükümsüz )
{
displayLeafNode'lar ( kök. Sağ ) ;
}
eğer ( kök. sol != hükümsüz )
{
displayLeafNode'lar ( kök. sol ) ;
}
}
rootNode idi = yeni Düğüm ( 3 ) ;
rootNode. sol = yeni Düğüm ( 6 ) ;
rootNode. Sağ = yeni Düğüm ( 9 ) ;
rootNode. sol . sol = yeni Düğüm ( 12 ) ;
rootNode. sol . Sağ = yeni Düğüm ( on beş ) ;
rootNode. sol . Sağ . Sağ = yeni Düğüm ( 24 ) ;
rootNode. Sağ . sol = yeni Düğüm ( 18 ) ;
rootNode. Sağ . Sağ = yeni Düğüm ( yirmi bir ) ;
displayLeafNode'lar ( kökDüğüm ) ;
Yukarıda belirtilen kod şu şekilde çalışır:
- İlk olarak sınıf ' Düğüm ”, yukarıdaki örneklerde yapılan bağlantıya benzer şekilde ağaca yeni bir düğüm eklemek için varsayılan yapıcıyı kullanan oluşturulur.
- Daha sonra “ displayLeadNodes() “ tek bir parametreyi kabul eden ” fonksiyonu oluşturuldu kökDüğüm ”. Bu parametre “ hükümsüz ' koşulu ' aracılığıyla eğer ' ifade.
- Sağlanan düğüm doğru değilse, o zaman ' sol ' Ve ' Sağ ” yan düğümler kontrol edilir” hükümsüz ' durum. Her ikisi de boşsa, düğüm '' olarak tanımlanacaktır. yaprak ” düğümü oluşturulur ve web sayfası üzerine yazdırılır.
- Bundan sonra “ Sağ ' Ve ' sol 'düğümleri' kökDüğüm 'e' displayLeafNodes() ' işlev.
- “” kullanarak örnekleri oluşturarak her düğümün konumunu tahsis edin. yeni ” anahtar kelimesi ve “ Düğüm() ” yapıcısı ve yapıcı parametresi olarak konumun belirtilmesi.
- “ sol ” kök düğümün sol konumu anlamına gelir ve “ sol sol ” konumu sol veya sol anlamına gelir. Aynı yaklaşım şu durumda da uygulanır: Sağ ' Ve ' Sağ ”.
- Son olarak “ kökDüğüm '' için bir argüman olarak displayLeafNode() ' işlev.
Oluşturulan çıktı, yaprak düğümlerin sağdan sola yönde yazdırıldığını gösterir.
Bu tamamen bir ikili ağacın tüm yaprak düğümlerini istenen herhangi bir yönde yazdırmakla ilgilidir.
Çözüm
Bir ikili ağacın tüm yaprak düğümlerini yazdırmak için, ağaç düğümlerine değerler oluşturup atayan rastgele bir sınıf oluşturun. Daha sonra, yukarıdan aşağıya hiyerarşide ağacın tek bir düğümünü kabul eden rastgele bir işlev oluşturun. Bu işlev birden fazla “ eğer ' olup olmadığını kontrol eden koşullar' düğüm ” boş değil ve “ içinde düğümleri yok sol ' Ve ' Sağ ” yönüne sahipse o düğüm bir “ yaprak ” düğümü ve konsolda görüntülenir. Bu kılavuz, bir ikili ağacın tüm yaprak düğümlerinin soldan sağa veya sağdan sola yazdırılma prosedürünü açıklamıştır.