STRUKTUR DATA (1) - lecturer.ukdw.ac.id

STRUKTUR DATA (1) - lecturer.ukdw.ac.id

STRUKTUR DATA (10) tree manipulation Oleh Antonius Rachmat C, S.Kom Tree Kumpulan node yang saling terhubung satu sama lain dalam suatu kesatuan yang membentuk layakya struktur sebuah pohon.

Struktur pohon adalah suatu cara merepresentasikan suatu struktur hirarki (one-tomany) secara grafis yang mirip sebuah pohon, walaupun pohon tersebut hanya tampak sebagai kumpulan node-node dari atas ke bawah. Suatu struktur data yang tidak linier yang menggambarkan hubungan yang hirarkis (one-tomany) dan tidak linier antara elemen-elemennya. Tree (2) Tree Statik : isi node-nodenya tetap karena bentuk pohonnya sudah

ditentukan. Tree Dinamik : isi nodenya berubahubah karena proses penambahan (insert) dan penghapusan (delete) Node Root Node root dalam sebuah tree adalah suatu node yang memiliki hiarki tertinggi dan dapat juga memiliki node-node anak. Semua node dapat ditelusuri dari node root tersebut.

Node root adalah node khusus yang tercipta pertama kalinya. Node-node lain di bawah node root saling terhubung satu sama lain dan disebut subtree Implementasi Tree Contoh penggunaan struktur pohon : Silsilah keluarga Parse Tree (pada compiler)

Struktur File Pertandingan Tree Example Tree Example Tree Example Representasi Tree

Representasi Tree Notasi Tingkat Notasi Kurung (A(B(D,E(I,J)),C(F,G,H))) Latihan Buat diagram venn dan notasi kurung XX

YY Q Q PP RR TT M

M UU NN SS W W ZZ

Terminologi Tree Sebuah Tree Jenis Tree 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. Binary Tree (2) Binary Tree Binary Tree

Binary Tree Node pada binary tree Jumlah maksimum node pada setiap tingkat adalah 2n Node pada binary tree maksimum berjumlah 2n-1 Implementasi Program Tree dapat dibuat dengan menggunakan

linked list secara rekursif. Linked list yang digunakan adalah double linked list non circular 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.

Implementasi Program Operasi-operasi Tree Create: membentuk sebuah tree baru yang kosong. pohon = NULL; Clear: menghapus semua elemen tree. pohon = NULL;

Empty: mengetahui apakah tree kosong atau tidak int isEmpty(Tree *pohon){ if(pohon == NULL) return 1; else return 0; } Operasi-operasi Tree

Insert: menambah node ke dalam Tree secara rekursif. Jika data yang akan dimasukkan lebih besar daripada elemen root, maka akan diletakkan di node sebelah kanan, sebaliknya jika lebih kecil maka akan diletakkan di node sebelah kiri. Untuk data pertama akan menjadi elemen root. Find: mencari node di dalam Tree secara rekursif sampai node tersebut ditemukan dengan menggunakan variable bantuan ketemu. Syaratnya adalah tree tidak boleh kosong. Traverse: yaitu operasi kunjungan terhadap node-node dalam pohon dimana masing-masing node akan dikunjungi sekali.

Count: menghitung jumlah node dalam Tree Height : mengetahui kedalaman sebuah Tree Find Min dan Find Max : mencari nilai terkecil dan terbesar pada Tree Child : mengetahui anak dari sebuah node (jika punya) Jenis Transverse PreOrder: cetak node yang dikunjungi, kunjungi left, kunjungi right InOrder: kunjungi left, cetak node yang

dikunjungi, kunjungi right PostOrder: kunjungi left, kunjungi right, cetak node yang dikunjungi Ilustrasi Insert Ilustrasi Insert 4. insert(left,3) Recursive Insert

void tambah(Tree **root,int databaru){

if((*root) == NULL){ Tree *baru; baru = new Tree; baru->data = databaru; baru->left = NULL; baru->right = NULL; (*root) = baru; (*root)->left = NULL; (*root)->right = NULL; }

else if(databaru < (*root)->data) tambah(&(*root)->left,databaru); else if(databaru > (*root)->data) tambah(&(*root)->right,databaru); else if(databaru == (*root)->data) printf("Data sudah ada!"); } Ilustrasi Kunjungan

Ilustrasi Kunjungan Ilustrasi Kunjungan Ilustrasi Kunjungan Kunjungan LevelOrder Hasil kunjungan: ABCDEFGHI Algoritma:

Siapkan antrian yang kosong Inisialisasi: masukkan root ke dalam antrian Iterasi: selama Antrian tidak kosong, lakukan: Kunjungi elemen pada antrian

Masukkan node->kiri dan node->kanan ke dalam antrian asal node tersebut tidak NULL. Keluarkan elemen pertama pada antrian Level Order 1 2 4

3 5 6 7 -Masukkan root ke antrian

Antrian : 1 -Kunjungi root (1), masukkan node kiri dan kanan Antrian : 1, 2, 3 -Keluarkan antrian terdepan (node 1) Antrian : 2, 3 -Kunjungi node 2, masukkan 4 dan 5 Antrian : 2, 3, 4, 5 -Keluarkan node terdepan (node 2) Antrian : 3, 4, 5 -Kunjungi node 3, masukkan 6 dan 7

Antrian : 3, 4, 5, 6, 7 -Keluarkan antrian terdepan (node 3) Antrian : 4, 5, 6, 7 -Kunjungi node 4, tidak ada anak, keluarkan (4) -Kunjungi node 5, tidak ada anak, keluarkan (5) -Kunjungi node 6, tidak ada anak, keluarkan (6) -Kunjungi node 7, tidak ada anak, keluarkan (7) Level Order pseudocode

void LevelOrder(Tree *root) { Queue queue; Enqueue(queue,root); while(isEmpty(queue) != 1) { Tree n = GetQueue(); //visit print(n->data);

if(n->left!=NULL) Enqueue(n->left); //Enqueue if exists if(n->right!=NULL) Enqueue(n->right); //Enqueue if exists Dequeue(queue); //out } } Contoh implementasi Misalkan suatu ekspresi berikut: 3 +

2*54 Searching in Tree

Tree *cari(Tree *root,int data){ if(root==NULL) return NULL; else if(data < root->data) return (cari(root->left,data)); else if(data > root->data) return (cari(root->right,data)); else if(data == root->data) return root; } Pencarian dilakukan secara rekursif, dimulai dari node root, jika data yang dicari lebih kecil daripada data node root, maka pencarian dilakukan di sub node sebelah kiri,

sedangkan jika data yang dicari lebih besar daripada data node root, maka pencarian dilakukan di sub node sebelah kanan, jika data yang dicari sama dengan data suatu node berarti kembalikan node tersebut dan berarti data ditemukan. Ilustrasi Searching Keterangan Searching

Root = 6 dan 8 > 6, maka akan dicari di sub node bagian kanan root. Root = 10 dan 8 < 10, maka akan dicari di sub node bagian kiri root. Root = 7 dan 8 > 7, maka akan dicari di sub node bagian kanan root.

Root = 8, berarti 8 = 8, maka akan dikembalikan node tersebut dan dianggap ketemu! Jumlah Node Tree int count(Tree *root) { if (root == NULL) return 0;

return count(root->left) + count(root->right) + 1; } Penghitungan jumlah node dalam tree dilakukan dengan cara mengunjungi setiap node, dimulai dari root ke subtree kiri, kemudian ke subtree kanan dan masing-masing node dicatat jumlahnya, dan terakhir jumlah node yang ada di subtree kiri dijumlahkan dengan jumlah node yang ada di subtree kanan ditambah 1 yaitu node root.

Kedalaman (height) Node Tree int height(Tree *root) { if (root == NULL) return -1; int u = height(root->left), v = height(root>right);

if (u > v) return u+1; else return v+1; } Penghitungan kedalaman dihitung dari setelah root, yang dimulai dari subtree bagian kiri kemudian ke subtree bagian kanan. Untuk masing-masing kedalaman kiri dan kanan akan dibandingkan, jika ternyata subtree kiri lebih dalam, maka yang dipakai adalah jumlah kedalaman subtree kiri, demikian sebaliknya. Hal ini didasarkan pada prinsip binary tree, dimana

tree-nya selalu memiliki maksimal 2 node anak. Find Min Node Tree *FindMin(Tree *root) { if(root == NULL) return NULL;

else if(root->left == NULL) return root; else return FindMin(root->left); }

Penggunaan: Tree *t = FindMin(pohon); Mencari Leaf (daun) void leaf(Tree *root){ if(root == NULL) printf("kosong!"); if(root->left!=NULL) leaf(root->left);

if(root->right!=NULL) leaf(root->right); if(root->right == NULL && root->left == NULL) printf("%d ",root->data); } Konversi Tree Biasa ke Binary Tree Anak pertama menjadi anak kiri, anak ke-2 menjadi cucu kanan, ke-3

jadi cicit kanan dst Pembentukan Tree dari Preorder Baca hasil Preorder dari paling kanan ke kiri untuk mencari node yang derajatnya lebih dari 0, kemudian ambil node sebanyak derajatnya ke kanan. Hilangkan node yang terambil tersebut dari hasil Preorder Lanjutkan langkah 1, dan seterusnya

sampai semua hasil traversal habis Contoh Preorder: U V W X Y Derajat: 2 2 0 0 0 Derajat bukan nol yang ditemukan pertama dari kanan adalah V, ambil 2 node kekanan, W dan X, hilangkan. Lanjutkan, ketemu U berderajat 2, berarti U punya anak V dan Y

Soal-soal Buatlah fungsi untuk menghapus suatu node pada Tree! Buatlah program lengkap untuk memanipulasi dan mensimulasikan tree dengan berbasis menu!

Recently Viewed Presentations

  • Conservation in the 2002 Farm Bill - University of Missouri

    Conservation in the 2002 Farm Bill - University of Missouri

    Missouri 2004 EQIP Policies have not been finalized Scoring Worksheets, Practices, and Cost Share/Incentives are anticipated to have only minor changes Competitive regions will probably change Check with your local NRCS office Irrigation Practices Available Surface Irrigation Irrigation Land Leveling-Regrade...
  • WTS Master EN

    WTS Master EN

    PRE-REFORM REGULATORY LANDSCAPE. Application for GBL 1 or GBL 2 Licence under Section 71(1) of FSA: ... Conducting business without holding a GBL (or an Authorisation) constitute an offence, with a fine not exceeding Rs 1 million. 4/3/2019. Footer.
  • Getting Your International Students to Berkeley

    Getting Your International Students to Berkeley

    Students must notify BIO prior to taking action. BIO will explain F-1/J-1 process of having their record ended and steps to request new visa documents after readmission. *NEW* BIO Withdrawal form for students to indicate they have officially notified BIO...
  • Intellectual Properties Next Generation Utilities for Modern EmpFiness

    Intellectual Properties Next Generation Utilities for Modern EmpFiness

    NPRE. NotesPoint Reverse Engineering Tool. NPWCM. NotesPoint Web Content Migrator. NPCM. NotesPoint Content Migrator. File-O-Cloud. A complete suite to go Cloud with all your files. Pre-Migration. Migration. Post-Migration. Supporting Elements. Discovery
  • Sections 5.3 &amp; 5.4 - cbafaculty.org

    Sections 5.3 & 5.4 - cbafaculty.org

    A body is subjected to a system of forces that lie in the x-y plane. When in equilibrium, the net force and net moment acting on the body are zero (as discussed earlier in Section 5.1). This 2-D condition can...
  • Classe découverte

    Classe découverte

    Classe découverte. Mme BALLAND-Mme BREMBOR. Classe « Découverte de l'Angleterre » Notre séjour en Angleterre s'inscrit dans un projet pédagogique construit en amont avec les élèves.
  • San Rafael/CMSA Methane Interview v.2

    San Rafael/CMSA Methane Interview v.2

    What are the best ways to capture Volatile Solids energy potential - 10,000 Btu/lb VS (23 000 kJ/kg VS)? ... Larger molecule carbonaceous solids are converted, by oxidization-reduction reactions, to smaller molecule combustible gas products ... San Rafael/CMSA Methane Interview...
  • GLOBALIZATION - York University

    GLOBALIZATION - York University

    GLOBALIZATION By: Aneisha Towheed Chelsea Takalo Diana Lall ... thus reinforcing the observation that poverty is political Global Monoculturalism The cultural dimension of globalization is no less ambiguous in impact and implications -Only now, the ideological principles are being applied...