struktur data pertemuan 15

 POHON BINER LANJUTAN

    pohon biner adalah bentuk graf yang terhubung, yang tidak memiliki sirkuit dan pada pohon biner selalu terdsapat path atau jalur yang menghubungkan dua simpul dalam pohon

1,Beberapa Terminology Pada Pohon biner:

Simpul akar (root)

   simpul pohon dengan tingkatan tertinggi

Simpul daun (leaf)

  Simpul   simpul pada pohon yang tidak lagi memiliki simpul anak (child)

Induk(parent)

   Simpul yang merupakan induk dari children-nya

Anak dari simpul x

   akar-akar (root) dari sub pohon–subpohon dari simpul x adalah anak dari x

Siblings

   Anak dari induk yang sama

2.Beberapa terminology pada pohon biner:

Moyang(anchestor)

  simpul-simpul di sepanjang jalur dari simpul keroot

Level suatu node

  Jika simpul pada level p, maka children-nya adalah berada pada level p + 1

Height atau depth

 Pohon memiliki ketinggian (height) atau kedalaman yang merupakan level tertinggi + 1.

Weight

  Pohon memiliki berat (weight) yang merupakan banyaknya Daun pada Pohon

3.Proses

a. Inisialisasi

b. Pembuatan sebuah simpul

c. Pembuatan simpul akar

d. Penambahan (insert) simpul kedalam sebuah pohon

e. Penghapusan (delete) simpul dari sebuah pohon

f. Pembacaan/penelusuran pohon biner II

4.Deklarasi simpul

struct Node{

int INFO;

 struct Node *LEFT;

struct Node *RIGHT;

};

Node *ROOT, *P, *Q, *R;

5.Contoh Program Tree dalam C++
#include
#include
#include
#include
struct Node{
int data;
Node *kiri;
Node *kanan;
};
int count;
void tambah(Node **root, int databaru)
{
if((*root) == NULL){
Node *baru;
baru = new Node;
baru->data = databaru;
baru->kiri = NULL;
baru->kanan = NULL;
(*root) = baru;
(*root)->kiri = NULL;
(*root)->kanan = NULL;
printf(“Data telah Dimasukkan”);
}
else if(databaru data)
tambah(&(*root)->kiri,databaru);
else if(databaru > (*root)->data)
tambah(&(*root)->kanan,databaru);
else if(databaru == (*root)->data)
printf(“Data sudah ada!!”);
}
void preOrder(Node *root){
if(root != NULL){
printf(“%d ” ,root->data);
preOrder(root->kiri);
preOrder(root->kanan);
}
}
void inOrder(Node *root){
if(root != NULL){
inOrder(root->kiri);
printf(“%d “,root->data);
inOrder(root->kanan);
}
}
void postOrder(Node *root){
if(root != NULL){
postOrder(root->kiri);
postOrder(root->kanan);
printf(“%d “,root->data);
}
}
void search(Node **root, int cari)
{
if((*root) == NULL){
printf(“Maaf,Data tidak ditemukan!”);
}
else if(cari data)
search(&(*root)->kiri,cari);
else if(cari > (*root)->data)
search(&(*root)->kanan,cari);
else if(cari == (*root)->data)
printf(“Data ditemukan!!!”);
}
void hapus(Node **root, int del)
{
if((*root) == NULL){
printf(“Data tidak ada!!”);
}
else if(del data)
hapus(&(*root)->kiri,del);
else if(del > (*root)->data)
hapus(&(*root)->kanan,del);
else if(del == (*root)->data)
{
(*root)=NULL;
printf(“Data telah Terhapus”);
}
}
int main(){
int pil,cari,del;
Node *pohon;
pohon = NULL;
do{
int data;
system(“cls”);
printf(” PROGRAM TREE LANJUTAN \n”);
printf(“================================\n”);
printf(” 1. Masukkan Data \n”);
printf(” 2. Transverse \n”);
printf(” 3. Cari \n”);
printf(” 4. Hapus \n”);
printf(” 5. Clear Data \n”);
printf(” 6. Keluar \n”);
printf(“================================\n”);
printf(“Masukkan Pilihan Anda : “);
scanf(“%d”,&pil);
switch(pil){
case 1:
printf(“Masukkan data baru : “);
scanf(“%d”, &data);
tambah(&pohon,data);
break;
case 2:
printf(“\nPreOrder : “);
if(pohon!=NULL) preOrder(pohon);
else printf(“Data masih kosong”);
printf(“\ninOrder : “);
if(pohon!=NULL) inOrder(pohon);
else printf(“Data masih kosong”);
printf(“\npostOrder : “);
if(pohon!=NULL) postOrder(pohon);
else printf(“Data masih kosong”);
break;
case 3:
printf(“Cari data : “);
scanf(“%d”, &cari);
search(&pohon,cari);
break;
case 4:
printf(“Hapus data : “);
scanf(“%d”, &del);
hapus(&pohon,del);
break;
case 5:
pohon = NULL;
printf(“Semua data telah terhapus”);
break;
case 6:
return 0;
default:
printf(“Maaf, pilihan Anda Salah”);
}
getch();
}while(pil!=7);
}
Tampilan program saat dijalankan :

Tampilan Transverse setelah diinput data 1,3,7 dan 5.