materi 10 - binary tree
TRANSCRIPT
Mata Kuliah Struktur Data - 2008
Binary Tree
Euis Marlina, S.Kom
Email : [email protected]://euismarlina.edublogs.org
HP : 08179424319
Pengantar
Mata Kuliah Struktur Data - 2008
Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hierarkis (hubungan one to many) antara elemen-elemen.
Tree bisa didefinisikan sebagai kumpulan simpul/node dengan elemen khusus yang disebut Root.
Binary Tree
Mata Kuliah Struktur Data - 2008
Binary Tree (Pohon Biner) yaitu pohon yang setiap simpul/node-nya paling banyak mempunyai dua buah subpohon.
Contoh implementasi : untuk membuat pohon silsilah keluarga, ungkapan aritmatika yang setiap operatornya dipasang sebagai simpul pencabangan dan operand-operandnya sebagai subpohon, dll.
Binary tree dapat diimplementasikan dalam C++ dengan menggunakan double linkedlist.
Kunjungan Pohon
Mata Kuliah Struktur Data - 2008
Ada 3 urutan dasar yang dapat digunakan untuk mengunjungi pohon, yaitu :
PreOrder : cetak isi node yang dikunjungi, kunjungi Left Child, kunjungi Right Child.
InOrder : kunjungi Left Child, cetak isi node yang dikunjungi, kunjungi Right Child.
PostOrder : kunjungi Left Child, kunjungi Right Child cetak isi node yang dikunjungi.
Penempatan Simpul
Simpul yang berisi informasi yang nilainya lebih besar dari simpul atas (root) akan ditempatkan sebagai cabang kanan, jika lebih kecil dari simpul atas akan ditempatkan sebagai cabang kiri.
Mata Kuliah Struktur Data - 2008
Contoh Pohon Biner
Mata Kuliah Struktur Data - 2008
*
-+
a /
cb
d *
e f
Ungkapan Aritmatika
Hasil :1.PreOrder : *+a/bc-d*ef2.InOrder : a+b/c*d-e*f3.PostOrder : abc/+def*-*
Mata Kuliah Struktur Data - 2008
Dari hasil di atas dapat disimpulkan bahwa :Kunjungan secara PreOrder akan
menghasilkan notasi PrefixKunjungan secara InOrder akan
menghasilkan notasi InfixKunjungan secara PostOrder akan
menghasilkan notasi Postfix
Contoh Program
Mata Kuliah Struktur Data - 2008
#include<iostream.h>#include<conio.h>#include<malloc.h>
#define nil NULL
struct nod{struct nod *left;char data;struct nod *right;
};
typedef struct nod NOD;typedef NOD POKOK;
Mata Kuliah Struktur Data - 2008
NOD *NodBaru(char item){
NOD *n;n=(NOD *)malloc(sizeof(NOD));
if(n != NULL){
n->data=item;n->left=NULL;n->right=NULL;
}return n;
}void BinaPokok(POKOK **T){
*T=NULL;}
Mata Kuliah Struktur Data - 2008
bool PokokKosong(POKOK *T){
return ((bool)(T==NULL));}void TambahNod(NOD **p, char item){
NOD *n;n=NodBaru(item);*p=n;
}void preOrder(POKOK *T){
if(!PokokKosong(T)){
cout<<" "<<T->data;preOrder(T->left);preOrder(T->right);
}}
Mata Kuliah Struktur Data - 2008
void inOrder(POKOK *T){
if(!PokokKosong(T)){
inOrder(T->left);cout<<" "<<T->data;inOrder(T->right);
}}void postOrder(POKOK *T){
if(!PokokKosong(T)){
postOrder(T->left);postOrder(T->right);cout<<" "<<T->data;
}}
Mata Kuliah Struktur Data - 2008
//Program utama int main(){
POKOK *kelapa;char buah;
BinaPokok(&kelapa);TambahNod(&kelapa, buah='M');TambahNod(&kelapa->left, buah='E');TambahNod(&kelapa->left->right, buah='I');TambahNod(&kelapa->right, buah='L');TambahNod(&kelapa->right->right, buah='O');TambahNod(&kelapa->right->right->left, buah='D');
cout<<"Tampilan secara PreOrder : ";preOrder(kelapa);
Mata Kuliah Struktur Data - 2008
cout<<endl;cout<<"Tampilan secara InOrder : ";inOrder(kelapa);
cout<<endl;cout<<"Tampilan secara PostOrder : ";postOrder(kelapa);
cout<<endl;cout<<endl;
getch();return 0;
}
Tampilan Program
Mata Kuliah Struktur Data - 2008
M
LE
IO
D