C'deki İkili Ağaç
C'de bir ikili ağaç maksimum sayıda iki alt düğüme sahip olabilecek bir üst düğüme sahip bir ağaç veri yapısının bir örneğidir; 0, 1 veya 2 yavru düğüm. Her bir düğüm bir ikili ağaç kendine ait bir değeri ve çocukları için iki işaretçisi vardır, biri sol çocuk için, diğeri sağ çocuk için.
İkili Ağaç Bildirgesi
A ikili ağaç adlı bir nesne kullanılarak C'de bildirilebilir. yapı ağaçtaki düğümlerden birini tasvir eden.
yapı düğüm {
veri türü var_adı ;
yapı düğüm * sol ;
yapı düğüm * Sağ ;
} ;
Yukarıda birinin beyanı var ikili ağaç düğüm olarak düğüm adı. Üç değere sahiptir; biri veri depolama değişkeni ve diğer ikisi çocuğa işaretçilerdir. (ana düğümün sol ve sağ çocuğu).
İkili Ağacın Gerçekleri
Büyük veri kümeleri için bile, bir ikili ağaç aramayı daha kolay ve hızlı hale getirir. Ağaç dallarının sayısı sınırlı değildir. Bir dizinin aksine, bir bireyin ihtiyacına göre her türden ağaç yapılabilir ve çoğaltılabilir.
C'de İkili Ağaç Uygulaması
Aşağıda, bir uygulamayı uygulamak için adım adım bir kılavuz yer almaktadır. İkili ağaç C'de
1. Adım: Bir İkili Arama Ağacı Bildirin
Data, *left_child ve *right_child gibi üç tür veriye sahip bir yapı düğümü oluşturun; burada veriler tamsayı türünde olabilir ve hem *left_child hem de *right_child düğümleri NULL olarak bildirilebilir veya bildirilemez.
yapı düğüm{
int veri ;
yapı düğüm * sağ_çocuk ;
yapı düğüm * sol_çocuk ;
} ;
2. Adım: İkili Arama Ağacında Yeni Düğümler Oluşturun
Bir tamsayıyı bağımsız değişken olarak kabul eden ve bu değerle oluşturulan yeni düğüme işaretçi sağlayan bir işlev oluşturarak yeni bir düğüm oluşturun. Oluşturulan düğüm için dinamik bellek tahsisi için C'deki malloc() işlevini kullanın. Sol ve sağ çocuğu NULL olarak başlatın ve düğümAdı'nı döndürün.
yapı düğüm * yaratmak ( veri türü verileri )
{
yapı düğüm * düğümAdı = alışveriş merkezi ( boyutu ( yapı düğüm ) ) ;
düğümAdı -> veri = değer ;
düğümAdı -> sol_çocuk = düğümAdı -> sağ_çocuk = HÜKÜMSÜZ ;
geri dönmek düğümAdı ;
}
3. Adım: İkili Ağaca Sağ ve Sol Çocukları Ekleyin
Eklenecek değer ve her iki çocuğun da bağlanacağı düğümün işaretçisi olan iki girişi kabul edecek insert_left ve insert_right işlevlerini oluşturun. Yeni bir düğüm oluşturmak için create işlevini çağırın ve döndürülen işaretçiyi kök ebeveynin sol çocuğunun sol işaretçisine veya sağ çocuğunun sağ işaretçisine atayın.
yapı düğüm * ekle_sol ( yapı düğüm * kök , veri türü verileri ) {kök -> sol = yaratmak ( veri ) ;
geri dönmek kök -> sol ;
}
yapı düğüm * ekle_sağ ( yapı düğüm * kök , veri türü verileri ) {
kök -> Sağ = yaratmak ( veri ) ;
geri dönmek kök -> Sağ ;
}
Adım 4: Geçiş Yöntemlerini Kullanarak İkili Ağacın Düğümlerini Görüntüleyin
C'de üç geçiş yöntemi kullanarak ağaçları görüntüleyebiliriz. Bu geçiş yöntemleri şunlardır:
1: Ön Sipariş Geçişi
Bu geçiş yönteminde, düğümlerden bir yönde geçeceğiz. parent_node->left_child->right_child .
geçersiz ön sipariş ( düğüm * kök ) {eğer ( kök ) {
printf ( '%D \N ' , kök -> veri ) ;
display_pre_order ( kök -> sol ) ;
display_pre_order ( kök -> Sağ ) ;
}
}
2: Sipariş Sonrası Geçiş
Bu geçiş yönteminde, düğümlerden bir yönde geçeceğiz. left_child->right_child->parent_node-> .
geçersiz display_post_order ( düğüm * kök ) {eğer ( ikili ağaç ) {
display_post_order ( kök -> sol ) ;
display_post_order ( kök -> Sağ ) ;
printf ( '%D \N ' , kök -> veri ) ;
}
}
3: Sıralı Geçiş
Bu geçiş yönteminde, düğümlerden bir yönde geçeceğiz. left_node->root_child->right_child .
geçersiz display_in_order ( düğüm * kök ) {eğer ( ikili ağaç ) {
display_in_order ( kök -> sol ) ;
printf ( '%D \N ' , kök -> veri ) ;
display_in_order ( kök -> Sağ ) ;
}
}
Adım 5: İkili Ağaçta Silme İşlemi Gerçekleştirin
Oluşturulanları silebiliriz İkili ağaç C'deki ana düğüm işlevine sahip her iki çocuğu da aşağıdaki gibi silerek.
geçersiz sil_t ( düğüm * kök ) {eğer ( kök ) {
sil_t ( kök -> sol ) ;
sil_t ( kök -> Sağ ) ;
özgür ( kök ) ;
}
}
İkili Arama Ağacının C Programı
Aşağıdakiler, C programlamasında Binary arama ağacının tam uygulamasıdır:
#include#include
yapı düğüm {
int değer ;
yapı düğüm * sol , * Sağ ;
} ;
yapı düğüm * düğüm1 ( int veri ) {
yapı düğüm * tmp = ( yapı düğüm * ) alışveriş merkezi ( boyutu ( yapı düğüm ) ) ;
tmp -> değer = veri ;
tmp -> sol = tmp -> Sağ = HÜKÜMSÜZ ;
geri dönmek tmp ;
}
geçersiz Yazdır ( yapı düğüm * root_node ) // düğümler gösteriliyor!
{
eğer ( root_node != HÜKÜMSÜZ ) {
Yazdır ( root_node -> sol ) ;
printf ( '%D \N ' , root_node -> değer ) ;
Yazdır ( root_node -> Sağ ) ;
}
}
yapı düğüm * insert_node ( yapı düğüm * düğüm , int veri ) // düğümler ekleniyor!
{
eğer ( düğüm == HÜKÜMSÜZ ) geri dönmek düğüm1 ( veri ) ;
eğer ( veri < düğüm -> değer ) {
düğüm -> sol = insert_node ( düğüm -> sol , veri ) ;
} başka eğer ( veri > düğüm -> değer ) {
düğüm -> Sağ = insert_node ( düğüm -> Sağ , veri ) ;
}
geri dönmek düğüm ;
}
int ana ( ) {
printf ( 'İkili Arama Ağacının C uygulaması! \N \N ' ) ;
yapı düğüm * ebeveyn = HÜKÜMSÜZ ;
ebeveyn = insert_node ( ebeveyn , 10 ) ;
insert_node ( ebeveyn , 4 ) ;
insert_node ( ebeveyn , 66 ) ;
insert_node ( ebeveyn , Dört beş ) ;
insert_node ( ebeveyn , 9 ) ;
insert_node ( ebeveyn , 7 ) ;
Yazdır ( ebeveyn ) ;
geri dönmek 0 ;
}
Yukarıdaki kodda, önce bir düğüm kullanarak yapı . Ardından yeni bir düğümü ' olarak başlatıyoruz. düğüm1 ” ve kullanarak belleği dinamik olarak ayırın malloc() C'de veriler ve iki işaretçi ile belirtilen düğümü kullanan çocukları yazın. Bundan sonra, düğümü şu şekilde görüntüleriz: printf() işlev ve onu çağırın ana() işlev. Sonra ekleme düğümü() işlev oluşturulur, burada düğüm verileri NULL ise o zaman düğüm1 kaldırılır, aksi takdirde veriler düğüm (ebeveyn) sol ve sağ çocuğun. Program yürütmeyi şu adresten başlatır: ana() çocuk olarak birkaç örnek düğüm kullanarak bir düğüm oluşturan ve ardından düğüm içeriğini yazdırmak için Sıralı geçiş yöntemlerini kullanan işlev.
Çıktı
Çözüm
Ağaçlar, verileri doğrusal olmayan bir biçimde tutmak için sıklıkla kullanılır. ikili ağaçlar her düğümün (ebeveyn) sol çocuk ve sağ çocuk olmak üzere iki yavruya sahip olduğu ağaç türleridir. A ikili ağaç veri aktarmanın ve depolamanın çok yönlü bir yöntemidir. C'deki Linked-List'e kıyasla daha verimlidir. Yukarıdaki makalede, bir kavramını gördük. İkili ağaç adım adım uygulanması ile İkili Arama Ağacı C'de