Dolaşmalar
Sıralı, öncelikli ve soncelikli dolaşma.
Dolaşmalar, CoddyKit'te ücretsiz bir C Academy dersidir. Bu, 4 dersinin 3. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, C Academy öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. C Academy kursu toplamda 4 dersten oluşur.
Dolaşım Nedir?
Dolaşım, bir ağaçtaki her düğümü tam olarak bir kez ziyaret etmenin sistematik bir yoludur.
Klasik üç derinlik öncelikli sıra; ara-sıralı, ön-sıralı ve son-sıralıdır. Bunlar yalnızca mevcut düğümün alt ağaçlarına göre ne zaman işlendiği bakımından farklıdır.
Ara-Sıralı Dolaşım
Ara-sıralı dolaşımda önce sol alt ağaç, ardından düğüm, sonra da sağ alt ağaç ziyaret edilir.
Bir BST için bu işlem değerleri küçükten büyüğe sıralı biçimde yazdırır; bu nedenle arama ağaçlarında en kullanışlı dolaşımdır.
void in_order(Node *root) {
if (root == NULL) return;
in_order(root->left);
printf("%d ", root->value);
in_order(root->right);
}Ön-Sıralı Dolaşım
Ön-sıralı dolaşımda önce düğüm, ardından sol alt ağaç, sonra da sağ alt ağaç ziyaret edilir.
Kök, çocuklarından önce üretildiği için ağacı kopyalamak veya ön ek gösterimli bir ifade oluşturmak için kullanışlıdır.
void pre_order(Node *root) {
if (root == NULL) return;
printf("%d ", root->value);
pre_order(root->left);
pre_order(root->right);
}Son-Sıralı Dolaşım
Son-sıralı dolaşımda önce her iki alt ağaç, en son da düğüm ziyaret edilir.
Çocuklar üst düğümlerinden önce işlendiği için ağaç belleğini serbest bırakırken tam olarak ihtiyaç duyduğunuz sıra budur; böylece çocukları ortadan kalktıktan sonra bir düğüm hiçbir zaman kullanılmaz.
void post_order(Node *root) {
if (root == NULL) return;
post_order(root->left);
post_order(root->right);
printf("%d ", root->value);
}Ortak Örüntü
Üç derinlik öncelikli dolaşım da aynı iskeleti paylaşır: bir NULL temel durumu, sol çocuğa yapılan bir özyinelemeli çağrı, sağ çocuğa yapılan bir özyinelemeli çağrı ve bir ziyaret adımı.
Sıranın adını değiştiren tek şey, ziyaret adımının konumudur.
/* visit position decides the order:
* pre : VISIT, left, right
* in : left, VISIT, right
* post : left, right, VISIT
*/Ara-Sıralı Dolaşım Sıralı Çıktı Verir
Bu program küçük bir BST oluşturur ve ara-sıralı dolaşım çalıştırarak sıralı çıktı özelliğini gösterir.
Değerler, ekleme sırasından bağımsız olarak küçükten büyüğe çıkar.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
if(!r) return cn(v);
if(v<r->value) r->left=insert(r->left,v);
else if(v>r->value) r->right=insert(r->right,v);
return r;
}
void in_order(Node *r){ if(!r) return; in_order(r->left); printf("%d ", r->value); in_order(r->right); }
int main(void){
Node *root=NULL;
int d[]={10,5,15,3,7,12};
for(int i=0;i<6;i++) root=insert(root,d[i]);
in_order(root);
printf("\n");
return 0;
}Üç Sıranın Karşılaştırılması
Kökü 10, solu 5 ve sağı 15 olan ağaç için çıktılar farklıdır:
Ön-sıralı çıktı 10 5 15 olur. Ara-sıralı çıktı 5 10 15 olur. Son-sıralı çıktı 5 15 10 olur. Düğüm değerleri aynıdır; yalnızca ziyaret zamanı değişir.
/* 10
* / \
* 5 15
* pre : 10 5 15
* in : 5 10 15
* post: 5 15 10
*/Seviye-Sıralı Dolaşım
Genişlik öncelikli veya seviye-sıralı dolaşımda düğümler yukarıdan aşağıya, seviye seviye ziyaret edilir. Bu işlem doğal olarak özyinelemeli değildir; bir kuyruk kullanır.
Kökü kuyruğa ekler, ardından sırayla bir düğümü kuyruktan çıkarıp yazdırır ve çocuklarını kuyruğa ekleriz.
void level_order(Node *root) {
if (!root) return;
Node *queue[100];
int head = 0, tail = 0;
queue[tail++] = root;
while (head < tail) {
Node *n = queue[head++];
printf("%d ", n->value);
if (n->left) queue[tail++] = n->left;
if (n->right) queue[tail++] = n->right;
}
}Dolaşım Gerçek İşleri Yürütür
Dolaşımlar yalnızca yazdırmak için değil, her düğüme dokunması gereken her işlem için şablon görevi görür.
Ziyaret adımını değerleri toplamaya, en büyük değeri bulmaya veya düğümleri kopyalamaya uyarladığınızda aynı yapı işi gerçekleştirir.
int sum_tree(Node *root) {
if (root == NULL) return 0;
return root->value
+ sum_tree(root->left)
+ sum_tree(root->right);
}Dolaşımın Maliyeti
Her dolaşım her düğümü bir kez ziyaret eder; bu nedenle çalışma süresi düğüm sayısı olan n ile orantılıdır.
Özyineleme, ağacın yüksekliğiyle orantılı yığın alanı kullanır; ağaç dengeliyse bu log(n), en kötü durumda ise n olur.
Üçü Birden
Bu program aynı ağaç için ön-sıralı, ara-sıralı ve son-sıralı çıktıları yazdırır; böylece bunları yan yana karşılaştırabilirsiniz.
Sonuçta oluşan diziyi yalnızca yazdırma çağrısının konumunun nasıl değiştirdiğine dikkat ediniz.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
void pre(Node *r){ if(!r) return; printf("%d ", r->value); pre(r->left); pre(r->right); }
void ino(Node *r){ if(!r) return; ino(r->left); printf("%d ", r->value); ino(r->right); }
void post(Node *r){ if(!r) return; post(r->left); post(r->right); printf("%d ", r->value); }
int main(void){
Node *root = cn(10);
root->left = cn(5); root->right = cn(15);
pre(root); printf("\n");
ino(root); printf("\n");
post(root); printf("\n");
return 0;
}Kısa Kontrol
İş için doğru dolaşımı seçiniz.
Özet
Derinlik öncelikli dolaşımlar tek bir özyinelemeli iskeleti paylaşır; ziyaret adımının konumu onları ön-sıralı, ara-sıralı veya son-sıralı yapar. BST üzerinde ara-sıralı dolaşım sıralı çıktı üretir, son-sıralı dolaşım ise belleği serbest bırakmak için güvenli sıradır.
Seviye-sıralı dolaşım genişlik önceliklidir ve kuyruk kullanır. Üçü de her düğümü bir kez, O(n) zamanda ziyaret eder.
Sıkça Sorulan Sorular
“Dolaşmalar” dersi ücretsiz mi?
Evet — “Dolaşmalar” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve C Academy kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. C Academy kursu toplamda 4 dersten oluşur.
“Dolaşmalar” dersinde ne öğreneceğim?
Sıralı, öncelikli ve soncelikli dolaşma. C Academy ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
C Academy öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te C Academy, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 3. dersidir.
“Dolaşmalar” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu C Academy dersinde kod yazıp çalıştırabilir miyim?
Evet. Her C Academy dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.