Penelusuran
In-order, pre-order, post-order.
Penelusuran adalah pelajaran C Academy gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar C Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus C Academy mencakup 4 pelajaran total.
Apa Itu Penelusuran?
Penelusuran adalah cara sistematis untuk mengunjungi setiap simpul dalam pohon tepat satu kali.
Tiga urutan depth-first klasik adalah in-order, pre-order, dan post-order. Perbedaannya hanya terletak pada kapan simpul saat ini diproses dibandingkan dengan subpohonnya.
Penelusuran In-Order
In-order mengunjungi subpohon kiri, lalu simpul, kemudian subpohon kanan.
Pada BST, cara ini mencetak nilai dalam urutan menaik, sehingga menjadi penelusuran yang paling berguna untuk pohon pencarian.
void in_order(Node *root) {
if (root == NULL) return;
in_order(root->left);
printf("%d ", root->value);
in_order(root->right);
}Penelusuran Pre-Order
Pre-order mengunjungi simpul terlebih dahulu, lalu subpohon kiri, kemudian subpohon kanan.
Urutan ini berguna untuk menyalin pohon atau menghasilkan ekspresi awalan, karena akar dikeluarkan sebelum anak-anaknya.
void pre_order(Node *root) {
if (root == NULL) return;
printf("%d ", root->value);
pre_order(root->left);
pre_order(root->right);
}Penelusuran Post-Order
Post-order mengunjungi kedua subpohon terlebih dahulu, lalu simpul pada urutan terakhir.
Karena anak-anak diproses sebelum induknya, urutan ini tepat digunakan saat membebaskan pohon, sehingga simpul tidak pernah digunakan setelah anak-anaknya dihapus.
void post_order(Node *root) {
if (root == NULL) return;
post_order(root->left);
post_order(root->right);
printf("%d ", root->value);
}Pola Umum
Ketiga penelusuran depth-first memiliki kerangka yang sama: kasus dasar NULL, rekursi ke anak kiri, rekursi ke anak kanan, dan langkah kunjungan.
Hanya posisi langkah kunjungan yang mengubah nama urutannya.
/* visit position decides the order:
* pre : VISIT, left, right
* in : left, VISIT, right
* post : left, right, VISIT
*/In-Order Mencetak Urutan Terurut
Program ini membangun BST kecil dan menjalankan penelusuran in-order untuk menunjukkan sifat keluaran yang terurut.
Nilai-nilai keluar dari yang terkecil hingga terbesar, apa pun urutan penyisipannya.
#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;
}Membandingkan Ketiga Urutan
Untuk pohon dengan akar 10, kiri 5, dan kanan 15, hasilnya berbeda:
Pre-order menghasilkan 10 5 15. In-order menghasilkan 5 10 15. Post-order menghasilkan 5 15 10. Nilai simpulnya sama; hanya waktu kunjungannya yang berubah.
/* 10
* / \
* 5 15
* pre : 10 5 15
* in : 5 10 15
* post: 5 15 10
*/Penelusuran Level-Order
Penelusuran breadth-first, atau level-order, mengunjungi simpul tingkat demi tingkat dari atas ke bawah. Cara ini tidak secara alami menggunakan rekursi; cara ini menggunakan antrean.
Kita memasukkan akar ke antrean, lalu berulang kali mengeluarkan sebuah simpul, mencetaknya, dan memasukkan anak-anaknya ke antrean.
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;
}
}Penelusuran Menggerakkan Pekerjaan Nyata
Penelusuran merupakan templat untuk operasi apa pun yang harus menyentuh setiap simpul, bukan hanya untuk mencetak.
Gantilah langkah kunjungan dengan penjumlahan nilai, pencarian nilai maksimum, atau penyalinan simpul, dan struktur yang sama akan menyelesaikan tugasnya.
int sum_tree(Node *root) {
if (root == NULL) return 0;
return root->value
+ sum_tree(root->left)
+ sum_tree(root->right);
}Biaya Penelusuran
Setiap penelusuran mengunjungi setiap simpul satu kali, sehingga berjalan dalam waktu yang sebanding dengan n, yaitu jumlah simpul.
Rekursi menggunakan ruang tumpukan yang sebanding dengan tinggi pohon, yaitu log(n) ketika seimbang dan n dalam kasus terburuk.
Ketiganya Sekaligus
Program ini mencetak pre-order, in-order, dan post-order untuk pohon yang sama agar Anda dapat membandingkannya berdampingan.
Perhatikan bahwa hanya posisi pemanggilan pencetakan yang mengubah urutan hasil.
#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;
}Pemeriksaan Singkat
Pilih penelusuran yang tepat untuk tugasnya.
Ringkasan
Penelusuran depth-first memiliki satu kerangka rekursif; posisi langkah kunjungan menjadikannya pre-order, in-order, atau post-order. In-order pada BST menghasilkan keluaran terurut, sedangkan post-order merupakan urutan yang aman untuk membebaskan pohon.
Level-order bersifat breadth-first dan menggunakan antrean. Semuanya mengunjungi setiap simpul satu kali dalam waktu O(n).
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Penelusuran” gratis?
Ya — teks lengkap “Penelusuran” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus C Academy, upgrade ke CoddyKit PRO. Kursus C Academy mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Penelusuran”?
In-order, pre-order, post-order. Kamu berlatih C Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai C Academy?
Tidak diperlukan pengalaman sebelumnya. C Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.
Berapa lama pelajaran “Penelusuran” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran C Academy ini?
Ya. Setiap pelajaran C Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.