data structure tree -...

Data Structure ” Tree ”

Kusnawi,S.Kom, M.Eng

Data Structure – Non Linier

„ Struktur Pohon ( Tree ) „ Graph

Konsep dasar Trees „ Secara sederhana tree dapat didefinisikan sebagai kumpulan elemen

yang salah satu elemennya disebut root, dan sisa elemen yang lain (yang disebut node)

„ Terpecah menjadi sejumlah himpunan yang saling tidak berhubungan satu sama lain (disjoint), yang disebut dengan subtree.

„ Node yang tidak mempunyai cabang disebut terminal node atau leaf, sedangkan node yang mempunyai cabang disebut branch node.

„ Jumlah node pada sebuah tree merupakan bilangan terbatas (finite number).

Examples of trees: „ Directory tree „ Family tree „ Company organization chart „ Table of contents „ etc.

Bentuk Trees

Level Trees

Binary Tree - Suatu tree dengan syarat bahwa tiap node hanya boleh memiliki

maksimal dua subtree dan kedua subtree tersebut harus terpisah. - Tiap node dalam binary tree hanya boleh memiliki paling banyak dua

child.

IMPLEMENTASI PROGRAM TREE

„ Tree dapat dibuat dengan menggunakan linked list secara rekursif. „ Linked list yang digunakan adalah double linked list. „ Data yang pertama kali masuk akan menjadi node root. „ Data yang lebih kecil dari data node root akan masuk dan

menempati node kiri dari node root, sedangkan jika lebih besar dari data node root, akan masuk dan menempati node di sebelah kanan node root.

„ Catatan : isi node bisa disesuaikan dengan permasalahan(kasus)

Binary Tree dan Representasi dalam Linked List

Pendeklarasian

typedef struct Tree { int data; Tree *left; Tree *right; }

Traversal pada Binary Tree Teknik menyusuri tiap node dalam sebuah tree

secara sistematis, sehingga semua node dapat dan hanya satu kali saja dikunjungi. Dengan melakukan kunjungan secara lengkap,

maka akan didapatkan urutan informasi secara linier yang tersimpan dalam sebuah binary tree. Terdapat tiga cara untuk melakukan kunjungan itu,

yaitu: Traversal preorder (depth first order), Traversal inorder (symmetric order) dan Traversal postorder

Traversal preorder (depth first order)

„ Dilaksanakan dengan jalan mencetak isi node yang dikunjungi lalu melakukan kunjungan ke subtree kiri dan selanjutnya ke subtree kanan.

Traversal inorder (symmetric order)

„ Dilaksanakan dengan jalan melakukan kunjungan ke subtree kiri, mencetak isi node yang dikunjungi, lalu melakukan kunjungan ke subtree kanan.

Traversal postorder „ Dilaksanakan dengan jalan melakukan kunjungan ke subtree kiri, lalu

ke subtree kanan, dan selanjutnya mencetak isi node yang dikunjungi.

Contoh

PreOrder Hasil kunjungan: “ABDGCEHIF” Procedure: void preOrder(Tree *root){ if(root != NULL){ printf("%d ",root->data); preOrder(root->left); preOrder(root->right); }}

InOrder Hasil kunjungan: “DGBAHEICF” Procedure:

void inOrder(Tree *root){ if(root != NULL){ inOrder(root->left); printf("%d ",root->data); inOrder(root->right);} }

PostOrder Hasil kunjungan: “GDBHIEFCA” Procedure:

void postOrder(Tree *root){ if(root != NULL){ postOrder(root->left); postOrder(root->right); printf("%d ",root->data); } }

Contoh Traversal InOrder Urutan penulisan ekpresi Aritmatik

DEMO