Berikut algoritma yang saya buat dengan tema mata kuliah struktur data, ini membahas binary tree saya menggunakan bahasa c dalam pemrogramannya. Langsung saja berikut ini saya akan memberikan source code binary tree.
Linked List, Stack, Queue merupakan struktur data yang bersifat linier
•Tree adalah struktur data tak linier yang memiliki sifat khusus.
•Tree merupakan salah satu bentuk implementasi banyak linked list yang biasanya digunakan untuk
menggambarkan hubungan yang bersifat hirarkis antara elemen-elemen yang ada.
•Contoh penggunaan struktur tree :
- Silsilah keluarga
- Hasil pertandingan yang berbentuk turnamen
- Struktur organisasi dari sebuah perusahaan
Binary tree adalah sebuah pengorganisasian secara hirarki dari beberapa buah node; masing-masing node tidak mempunyai child lebih dari 2.
Langkah-langkah Pembentukan Binary Tree.
Siapkan node baru
-
alokasikan memory-nya
-
masukkan info-nya
-
set pointer kiri & kanan = NULL
2. Sisipkan pada posisi yang tepat
-
penelusuran à utk menentukan posisi yang tepat; info yang nilainya lebih besar dari parent akan ditelusuri di sebelah kanan, yang lebih kecil dari parent akan ditelusuri di sebelah kiri
-
penempatan à info yang nilainya lebih dari parent akan ditempatkan di sebelah kanan, yang lebih kecil di sebelah kiri
Algoritma Pembentukan Binary Tree.
. Buat node baru (new)
2. Cek apakah root
= NULL,
jika ya, maka root
= new, melompat ke langkah 9
jika tidak, maka lakukan langkah-langkah berikut
3. Mencari posisi yang tepat untuk new, tentukan P
=root, Q = root
4. Kerjakan langkah 5 dan 6 selama Q
<> NULL dan new->info <> P->info
5. Tentukan P = Q
6. Cek apakah new->info
< P->info
jika ya, (teruskan ke cabang kiri), tentukan Q
= P->kiri
jika tidak, (teruskan ke cabang kanan), tentukan Q
= P->kanan
7. Cek apakah new->info
= P->info
jika ya, (tidak perlu disisipkan), tampilkan pesan duplikasi, lompat ke langkah 9
jika tidak, (sisipkan), kerjakan langkah 8
8. Cek apakah new->info
< P->info
jika ya, (sebagai cabang kiri) P->kiri
= new
jika tidak, (sebagai cabang kanan) P->kanan
= new
9. Selesai
berikut script code program saya menggunakan c.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef char typeinfo;
typedef struct node tree;
struct node {
int info;
tree *kanan;//cabang kiri
tree *kiri;//cabang kanan
};
tree *p,*q,*baru, *root,*baca;
int x,n=0;
float total=0.0f,jum=0.0f;
float rata=0.0f;
void alokasi(){
printf("masukan DATA: ");
fflush(stdin);
scanf("%i",&x);
baru=(tree *)malloc(sizeof(tree));
if(baru==NULL){
puts("Alokasi memori gagal");
}
else{
baru->info=x;
baru->kanan=NULL;
baru->kiri=NULL;
}
}
void bentuk(){
alokasi();
n++;//banyak data
if(root==NULL){
root=baru;
}
else{
p=root;
q=root;
while((q!=NULL)&&(baru->info!=p->info)){
p=q;
if(baru->info<p->info){
q=p->kiri;
}
else{
q=p->kanan;
}
}
if(baru->info==p->info){
puts("data duplikasi");
}
else{
if(baru->info<p->info){
p->kiri=baru;
}
else{
p->kanan=baru;
}
}
}
}
void preorder(tree *root){
if(root!=NULL){
jum=root->info;
printf("%d ",root->info);
total=total+jum;
preorder(root->kiri);
preorder(root->kanan);
}
//return;
}
void inorder(tree *root){
if(root!=NULL){
inorder(root->kiri);
printf("%d ",root->info);
inorder(root->kanan);
}
//return;
}
void postorder(tree *root){
if(root!=NULL){
postorder(root->kiri);
postorder(root->kanan);
printf("%d ",root->info);
}
//return;
}
main(){
char jawab;
do{
bentuk();
printf("ada data lagi: ");
fflush(stdin);
jawab=getchar();
}while(jawab=='y'||jawab=='Y');
printf("hasil pre order : ");
preorder(root);
printf("\nhasil in order : ");
inorder(root);
printf("\n hasil post order : ");
postorder(root);
printf("\ntotal data=%d",total);
printf("\nbanyak data=%d ",n);
printf("\n\nrata-rata= %g\n",rata=total/n);
}
#include<stdlib.h>
#include<string.h>
typedef char typeinfo;
typedef struct node tree;
struct node {
int info;
tree *kanan;//cabang kiri
tree *kiri;//cabang kanan
};
tree *p,*q,*baru, *root,*baca;
int x,n=0;
float total=0.0f,jum=0.0f;
float rata=0.0f;
void alokasi(){
printf("masukan DATA: ");
fflush(stdin);
scanf("%i",&x);
baru=(tree *)malloc(sizeof(tree));
if(baru==NULL){
puts("Alokasi memori gagal");
}
else{
baru->info=x;
baru->kanan=NULL;
baru->kiri=NULL;
}
}
void bentuk(){
alokasi();
n++;//banyak data
if(root==NULL){
root=baru;
}
else{
p=root;
q=root;
while((q!=NULL)&&(baru->info!=p->info)){
p=q;
if(baru->info<p->info){
q=p->kiri;
}
else{
q=p->kanan;
}
}
if(baru->info==p->info){
puts("data duplikasi");
}
else{
if(baru->info<p->info){
p->kiri=baru;
}
else{
p->kanan=baru;
}
}
}
}
void preorder(tree *root){
if(root!=NULL){
jum=root->info;
printf("%d ",root->info);
total=total+jum;
preorder(root->kiri);
preorder(root->kanan);
}
//return;
}
void inorder(tree *root){
if(root!=NULL){
inorder(root->kiri);
printf("%d ",root->info);
inorder(root->kanan);
}
//return;
}
void postorder(tree *root){
if(root!=NULL){
postorder(root->kiri);
postorder(root->kanan);
printf("%d ",root->info);
}
//return;
}
main(){
char jawab;
do{
bentuk();
printf("ada data lagi: ");
fflush(stdin);
jawab=getchar();
}while(jawab=='y'||jawab=='Y');
printf("hasil pre order : ");
preorder(root);
printf("\nhasil in order : ");
inorder(root);
printf("\n hasil post order : ");
postorder(root);
printf("\ntotal data=%d",total);
printf("\nbanyak data=%d ",n);
printf("\n\nrata-rata= %g\n",rata=total/n);
}
