Penelusuran Pohon Biner Algoritma DFS(Stack) dan Algoritma BFS(Queue) dalam Bahasa C

Penelusuran Pohon Biner Berdasarkan Kedalaman dengan Algoritma DFS + Stack dan Secara Melebar (Level Order) dengan Algoritma BFS + Queue serta Implementasinya dalam Bahasa C.

Judulnya udah kaya judul jurnal -_-
Yaudahlah ya, nah sekarang sesuai dengan judul postingan ini kita akan membahas bagaimana cara kerja dan implementasi algoritma DFS dan BFS dalam bahasa C. Dalam postingan kali ini saya melibatkan 3 buah stuktur data yang sudah di jelaskan sebelumnya, yaitu stack, queue dan pohon biner.

Depth First Search

DFS (Depth-First-Search) adalah salah satu algoritma penelusuran struktur graf / pohon berdasarkan kedalaman. Simpul ditelusuri dari root kemudian ke salah satu simpul anaknya ( misalnya prioritas penelusuran berdasarkan anak pertama [simpul sebelah kiri] ), maka penelusuran dilakukan terus melalui simpul anak pertama dari simpul anak pertama level sebelumnya hingga mencapai level terdalam.

Setelah sampai di level terdalam, penelusuran akan kembali ke 1 level sebelumnya untuk menelusuri simpul anak kedua pada pohon biner [simpul sebelah kanan] lalu kembali ke langkah sebelumnya dengan menelusuri simpul anak pertama lagi sampai level terdalam dan seterusnya.

Jadi, jika ada pohon biner seperti gambar di bawah ini :

Maka, urutan penelusurannya adalah : A – B – D – H – E – I – C – F – G – J – K – L

Dalam implementasinya DFS dapat diselesaikan dengan cara rekursif atau dengan bantuan struktur data stack. Kita akan membahas dengan cara yang menggunakan stack. Stack yang digunakan adalah stack yang isi elemennya adalah simpul pohon / tree. Bagaimana cara kerjanya ? Berikut ini adalah urutan algoritmanya :

Masukkan simpul root ke dalam tumpukan dengan push
Ambil dan simpan isi elemen (berupa simpul pohon) dari tumpukan teratas
Hapus isi stack teratas dengan prosedur pop
Periksa apakah simpul pohon yang disimpan tadi memiliki anak simpul
Jika ya, push semua anak simpul yang dibangkitkan ke dalam stack
Jika tumpukan kosong berhenti, tapi jika tidak kembali ke langkah dua

Jadi, untuk gambar pohon biner di atas urutan langkah dan kondisi stack-nya setiap iterasi adalah :

Contoh diatas menggunakan prioritas untuk memasukkan anak simpul dari sebelah kanan terlebih dahulu ke dalam stack. Sehingga, pada iterasi 2 elemen A dihapus lalu memasukkan anak simpulnya yaitu C dulu, baru B ke dalam stack. Selain itu bisa dilihat stack teratas (yang diwarna biru) pada tiap iterasi memiliki urutan A – B – D – H – E – I – C – F – G – J – K – L. Oiya, pada iterasi ke 13 itu kondisi stack sudah kosong karena ketika simpul J dibangkitkan tidak ada anak simpul yang dimasukkan ke stack.

Jika dituliskan dalam bahasa C, prosedur pencetakan dengan DFS-nya kurang lebih bisa ditulis seperti ini :

void DFS_printPreOrder(simpul *root){
	if(root!=NULL){
		stack S;
		createEmptyStack(&S);
		push(root, &S);

		while(isStackEmpty(S) != 1){
			printf("%c ", S.top->elemen->huruf);
			simpul *node = peek(S);
			pop(&S);

			if(node->right != NULL){
				push(node->right, &S);
			}
			if(node->left != NULL){
				push(node->left, &S);
			}
		}
		printf("\n");
	}
}

Breadth First Search

BFS (Breadth First Search) juga merupakan salah satu algoritma penelusuran struktur graf / pohon seperti DFS, namun bedanya BFS melakukan pencarian secara melebar atau per level pohon. Simpul ditelusuri dari root kemudian menelusuri semua simpul pada setiap level di bawahnya ( misalnya prioritas penelusuran dari kiri ke kanan ), maka penelusuran dilakukan terus dari simpul paling kiri ke simpul anak – anak tetangganya yang selevel.

Jadi, untuk pohon biner :

Maka, urutan penelusurannya adalah : A – B – C – D – E – F – G – H – I – J – K – L

Salah satu cara implementasi BFS adalah dengan bantuan struktur data queue. Sama seperti stack pada DFS, queue yang digunakan adalah queue yang isi elemennya adalah simpul pohon / tree. Berikut ini adalah urutan algoritmanya :

Masukkan simpul root ke dalam antrian
Periksa antrian terdepan apakah memiliki anak simpul
Jika ya, masukan semua anak simpul ke dalam antrian
Hapus antrian terdepan
Jika antrian kosong berhenti, tapi jika tidak kembali ke langkah dua

Untuk gambar pohon biner di atas, urutan langkah dan kondisi queue pada setiap iterasinya adalah sebagai berikut :

Contoh diatas menggunakan prioritas untuk memasukkan anak simpul dari sebelah kiri terlebih dahulu ke dalam queue. Sehingga, pada iterasi 2 elemen A dihapus lalu memasukkan anak simpulnya yaitu B dulu, baru C ke dalam stack. Untuk penelusurannya yang dilihat adalah bagian yang berwarna biru, yaitu antrian terdepan yang setiap iterasinya memiliki urutan A – B – C – D – E – F – G – H – I – J – K – L. Sama seperti DFS lagi pada iterasi ke 13 itu kondisi antrian sudah kosong.

Berikut adalah potongan prosedurnya dalam bahasa C :

void BFS_printLevelOrder(simpul *root){
	if(root!=NULL){
		queue Q;
		createEmptyQueue(&Q);
		addQueue(root, &Q);

		while(isQueueEmpty(Q) != 1){
			printf("%c ", Q.first->elemen->huruf);

			if(Q.first->elemen->left != NULL){
				addQueue(Q.first->elemen->left, &Q);
			}
			if(Q.first->elemen->right != NULL){
				addQueue(Q.first->elemen->right, &Q);
			}
			delQueue(&Q);
		}
		printf("\n");
	}
}

Kodingan lengkapnya untuk DFS dan BFS karena menggunakan gabungan 3 struktur data dan dalam satu file, jadi cukup panjang. Bisa dilihat disini :

/*
	Saungkode - saungkode.wordpress.com
*/

/*Library*/

#include <stdio.h>
#include <string.h>
#include <malloc.h>

#define LEFT "left"
#define RIGHT "right"

/*-------Pohon Biner*/

typedef struct smp *alamatsimpul;
typedef struct smp{
	char huruf;         //Elemen pohon
	alamatsimpul right;//Ranting kanan
	alamatsimpul left;//Ranting kiri
}simpul;

typedef struct{
	simpul* root;//Root = Akar pohon paling atas
}tree;

/*-------Stack*/

typedef struct elmStack *alamatelmtStack;
typedef struct elmStack{
	simpul* elemen;//alamat simpul pohon
	alamatelmtStack next;
}containerStack;

typedef struct {
  containerStack *top;//Paling atas
}stack;

/*-------Queue*/

typedef struct elmQueue *alamatelmtQueue;
typedef struct elmQueue{
	simpul* elemen;//alamat simpul pohon
	alamatelmtQueue next;
}containerQueue;

typedef struct{
	containerQueue *first;//Pointer depan
	containerQueue *last;//Pointer belakang
}queue;

/*
	Saungkode - saungkode.wordpress.com
*/

/*Mesin*/

/*-------Pohon Biner*/

//Buat pohon baru
void makeTree(char huruf, tree *T){
	simpul *node;//Pointer baru
	node = (simpul *) malloc (sizeof (simpul));
	node->huruf = huruf;
	node->right = NULL;
	node->left = NULL;
	(*T).root = node;//Pindah akar
}

//Tambah elemen di ranting kanan
void addTree(char tempat[], char huruf, simpul **root){
	/*Jika ranting kanan masih kosong*/
	if((*root)->right == NULL){
		simpul *node;//Pointer baru
		node = (simpul *) malloc (sizeof (simpul));
		node->huruf = huruf;
		node->right = NULL;
		node->left = NULL;
		if(strcmp(tempat, RIGHT) == 0) (*root)->right = node;//Pindah ranting kanan
		else if(strcmp(tempat, LEFT) == 0) (*root)->left = node;//Pindah ranting kiri
	}
}

/*
	Saungkode - saungkode.wordpress.com
*/

/*-------Stack*/

//buat stack kosong
void createEmptyStack(stack *S){
  (*S).top = NULL;
}

//fungsi memeriksa stack kosong atau tidak
int isStackEmpty(stack S){
	int hasil = 0;
	if(S.top == NULL){ //jika kosong
		hasil = 1;
	}
	return hasil;
}

//operator peek
simpul* peek(stack S){
	if(S.top != NULL){ //jika tidak kosong
		return S.top->elemen;
	}
}

//operator push
void push(simpul *node, stack *S ){
	containerStack *tunjuk;
	tunjuk = (containerStack *) malloc (sizeof (containerStack));
	tunjuk->elemen = node;
	tunjuk->next = (*S).top;
	(*S).top = tunjuk;
	tunjuk = NULL;
}

//operator pop
void pop(stack *S){
	if((*S).top != NULL){ //jika tidak kosong
		containerStack *tunjuk = (*S).top;
		(*S).top = (*S).top->next;
		tunjuk->next = NULL;
		free(tunjuk);
	}
}

/*
	Saungkode - saungkode.wordpress.com
*/

/*-------Queue*/

//prosedur membuat queue kosong
void createEmptyQueue(queue *Q){
	(*Q).first = NULL;
	(*Q).last = NULL;
}

//prosedur memeriksa apakah queue kosong
int isQueueEmpty(queue Q){
	int hasil = 0;
	if(Q.first == NULL){
		hasil = 1;
	}
	return hasil;
}

//prosedur menambah elemen pada queue(addLast)
void addQueue(simpul *node, queue *Q ){
	containerQueue *tunjuk;
	tunjuk = (containerQueue *) malloc (sizeof (containerQueue));
	tunjuk->elemen = node;
	tunjuk->next = NULL;

	//jika queue masih kosong (addFirst)
	if((*Q).first == NULL) (*Q).first = tunjuk;
	else (*Q).last->next = tunjuk;

	(*Q).last = tunjuk;
	tunjuk = NULL;
}

//prosedur delete queue (delFirst);
void delQueue(queue *Q){

	//jika queue tidak kosong
	if((*Q).first != NULL){
		containerQueue *tunjuk = (*Q).first;
		(*Q).first = (*Q).first->next;
		tunjuk->next = NULL;
		free(tunjuk);
	}
}

/*
	Saungkode - saungkode.wordpress.com
*/

/*-------Prosedur Cetak Pohon Biner*/

// print pohon menurut keadalaman dengan algoritma DFS
void DFS_printPreOrder(simpul *root){
	if(root!=NULL){
		stack S;
		createEmptyStack(&S);
		push(root, &S);

		while(isStackEmpty(S) != 1){
			printf("%c ", S.top->elemen->huruf);
			simpul *node = peek(S);
			pop(&S);

			if(node->right != NULL){
				push(node->right, &S);
			}
			if(node->left != NULL){
				push(node->left, &S);
			}
		}
		printf("\n");
	}
}

//print pohon per level dengan algoritma BFS
void BFS_printLevelOrder(simpul *root){
	if(root!=NULL){
		queue Q;
		createEmptyQueue(&Q);
		addQueue(root, &Q);

		while(isQueueEmpty(Q) != 1){
			printf("%c ", Q.first->elemen->huruf);

			if(Q.first->elemen->left != NULL){
				addQueue(Q.first->elemen->left, &Q);
			}
			if(Q.first->elemen->right != NULL){
				addQueue(Q.first->elemen->right, &Q);
			}
			delQueue(&Q);
		}
		printf("\n");
	}
}

/*
	Saungkode - saungkode.wordpress.com
*/

int main(){

	tree T;

	makeTree('A', &T);
	addTree(LEFT , 'B', &T.root);
	addTree(RIGHT, 'C', &T.root);
	addTree(LEFT , 'D', &T.root->left);
	addTree(RIGHT, 'E', &T.root->left);
	addTree(LEFT , 'F', &T.root->right);
	addTree(RIGHT, 'G', &T.root->right);
	addTree(LEFT , 'H', &T.root->left->left);
	addTree(RIGHT, 'I', &T.root->left->right);
	addTree(LEFT , 'J', &T.root->right->right);
	addTree(RIGHT, 'K', &T.root->right->right);
	addTree(RIGHT, 'L', &T.root->right->right->right);

	DFS_printPreOrder(T.root);
	BFS_printLevelOrder(T.root);

	return 0;
}