Pengertian serta Implementasi Binary Tree pada C#.pdf PDF

Preview

Summary

“Pengertian serta Implementasi Binary Tree pada C#” Yosua Tanga Wila 1706080071 Yandris William R. Octavianus 1706080072 Elfrida Veranda Beka Dede 1706080076 Andrew Simanjuntak 1706080088 ILMU KOMPUTER FAKULTAS SAINS DAN TEKNIK UNIVERSITAS NUSA CENDANA 2018 1 TREE STRUCTURE (Struktur Pohon) A. Penge...

Description

Accelerat ing t he world's research.

Pengertian serta Implementasi Binary Tree pada C#.pdf Vera Dede

Related papers Buku St rukt ur dat a - Copy muhamad azam azam Modul 4 St rukt ur Pohon rio arden MAKALAH T IK ST RUKT UR DATA ALYA RAISA NADYA barabai

Download a PDF Pack of t he best relat ed papers 

“Pengertian n sert serta Implementasi Binary y Tree T pada C#”

Yosua Tanga Wila la

1706080071

Yandris William R. Octavianus

1706080072

Elfrida Verandaa Be Beka Dede

1706080076

Andrew Simanjuntak ntak

1706080088

IL ILMU KOMPUTER FAKUL ULTAS SAINS DAN TEKNIK UNIVE ERSITAS NUSA CENDANA 2018 1

TREE STRUCTURE (Struktur Pohon)

A.

Pengertian Tree Tree/pohon merupakan struktur data yang tidak linear/non linear yang digunakan

terutama untuk merepresentasikan hubungan data yang bersifat hierarkis antara elemenelemennya. Definisi tree : “Kumpulan elemen yang salah satu elemennya disebut dengan root (akar) dan sisa elemen yang lain disebut sebagai simpul (node/vertex) yang terpecah menjadi sejumlah himpunan yang tidak saling berhubungan satu sama lain, yang disebut subtree/cabang”.

Contoh sebuah Tree :

2

Istilah - istilah objek tree : •

Simpul adalah elemen tree yang berisi informasi / data dan penunjuk pencabangan.

•

Tingkat/level suatu simpul ditentukan dari akar (root), sebagai level 1. Apabila simpul dinyatakan sebagai tingkat N, maka simpul-simpul yang merupakan anaknya berada pada tingkat N+1.

•

Derajat/degree menyatakan banyaknya anak/turunan di simpul tersebut. Contoh : Simpul A memiliki derajat 2 (B dan C), simpul yang memiliki derajat 0 (nol) disebut leaf (daun) seperti : I, J, K, L, N, dan O.

•

Tinggi (height) atau kedalaman (depth) suatu tree adalah tingkat maksimum dari tingkat dalam tree tersebut dikurangi 1.

•

Contoh dalam tree di atas, mempunyai depth 4.

•

Ancestor suatu simpul adalah semua simpul yang terletak dalam satu jalur dengan simpul tersebut, dari akar sampai simul yang ditinjaunya. Contoh Ancestor L adalah A, C dan G.

•

Predecessor adalah simpul yang berada di atas simpul yang ditinjau. Contoh : Predecessor D adalah B.

•

Successor adalah simpul yang berada di bawah simpul yang ditinjau. Contoh : Successor D adalah I.

•

Descendant adalah seluruh simpul yang terletak sesudah simpul tertentu dan terletak pada jalur yang sama. Contoh : Descendant E adalah J dan K.

•

Sibling adalah simpul-simpul yang memiliki parent yang sama dengan simpul yang ditinjau. Contoh : Sibling J adalah K

•

Parent adalah simpul yang berada satu level di atas simpul yang ditinjau. Contoh : Parent J adalah E

3

B.

Binary Tree (Pohon Biner) Dalam mata kuliah struktur data, secara khusus akan dipelajari mengenai pohon

biner. Pohon biner adalah sebuah tree yang pada masing-masing simpulnya hanya dapat memiliki maksimum 2 (dua) simpul anak. Tidak boleh lebih. Pada pohon biner, umumnya kedua node anak disebut dengan posisinya, yaitu kiri dan kanan. Beberapa istilah pada pohon biner: • Size (ukuran): jumlah total node yang terdapat pada pohon biner tersebut. • Depth (kedalaman): panjang jalur yang menghubungkan sebuah node sampai ke node anaknya yang paling ujung (leaf). Depth biasa juga disebut height.

Full Binary Tree (Pohon Biner Penuh) adalah pohon biner yang setiap nodenya pasti memiliki 0 atau 2 node anak.

Perfect Binary Tree (Pohon Biner Sempurna) adalah pohon biner yang semua node leafnya berada pada kedalaman yang sama dari node root. Juga disebut sebagai Complete Binary Tree (Pohon Biner Lengkap)

Almost Complete Binary Tree (Pohon Biner Hampir Lengkap) adalah pohon biner yang setiap nodenya dapat memiliki 0 node anak, atau memiliki kiri, atau jika memiliki kanan harus memiliki kiri. Tidak boleh memiliki kanan saja.

Ilustrasi Binary Tree:

4

C.

Implementasi Binary Tree

1. Menambahkan Node Pada Tree Karena pohon yang kita buat merupakan sebuah pohon biner, maka untuk menambahkan sebuah node, secara otomatis penambahan tersebut mengikuti aturan penambahan node pada pohon biner:

1. Jika pohon kosong, maka node baru ditempatkan sebagai akar pohon. 2. Jika pohon tidak kosong, maka dimulai dari node akar, dilakukan proses pengecekan berikut:

a.

Jika nilai node baru lebih kecil dari nilai node yang sedang dicek, maka lihat ke kiri

node tersebut. Jika kiri node tersebut kosong (belum memiliki kiri), maka node baru menjadi kiri node yang sedang dicek. Seandainya kiri node sudah terisi, lakukan kembali pengecekan a dan b terhadap node kiri tersebut. Pengecekan ini dilakukan seterusnya hingga node baru dapat ditempatkan.

b. Jika nilai node baru lebih besar dari nilai node yang sedang dicek, maka lihat ke kanan node tersebut. Jika kanan node tersebut kosong (belum memiliki kanan), maka node baru menjadi kanan node yang sedang dicek. Seandainya kanan node sudah terisi, lakukan kembali pengecekan a dan b terhadap node kanan tersebut. Pengecekan ini dilakukan seterusnya hingga node baru dapat ditempatkan. 5

4. Membaca dan Menampilkan Node Pada Tree Untuk membaca dan menampilkan seluruh node yang terdapat pada pohon biner, terdapat 3 macam cara, atau yang biasa disebut kunjungan (visit). Semua kunjungan diawali dengan mengunjungi akar pohon. Karena proses kunjungan ini memerlukan perulangan proses yang sama namun untuk depth (kedalaman) yang berbeda, maka ketiganya diimplementasikan dengan fungsi rekursif.

a)

Kunjungan Pre-Order Kunjungan pre-order dilakukan mulai dari akar pohon, dengan urutan:

1. Cetak isi (data) node yang sedang dikunjungi 2. Kunjungi kiri node tersebut, •

Jika kiri bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kiri tersebut.

•

Jika kiri kosong (NULL), lanjut ke langkah ketiga.

3. Kunjungi kanan node tersebut, •

Jika kanan bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kanan tersebut.

•

Jika kanan kosong (NULL), proses untuk node ini selesai, tuntaskan proses yang sama untuk node yang dikunjungi sebelumnya.

Gambar a. Preorder

b) 6

Kunjungan In-Order

1. Kunjungi kiri node tersebut, •

Jika kiri bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kiri tersebut.

•

Jika kiri kosong (NULL), lanjut ke langkah kedua.

2. Cetak isi (data) node yang sedang dikunjungi 3. Kunjungi kanan node tersebut, •

Jika kanan bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kanan tersebut.

•

Jika kanan kosong (NULL), proses untuk node ini selesai, tuntaskan proses yang sama untuk node yang dikunjungi sebelumnya.

Gambar b. Inorder

c)

Kunjungan Post-Order

1. Kunjungi kiri node tersebut, •

Jika kiri bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kiri tersebut.

•

Jika kiri kosong (NULL), lanjut ke langkah kedua.

2. Kunjungi kanan node tersebut, •

Jika kanan bukan kosong (tidak NULL) mulai lagi dari langkah pertama, terapkan untuk kanan tersebut.

•

Jika kanan kosong (NULL), lanjut ke langkah ketiga.

3.

Cetak isi (data) node yang sedang dikunjungi. Proses untuk node ini selesai, tuntaskan proses yang sama untuk node yang dikunjungi sebelumnya.

7

Gambar c. Postorder

5. Kode Program Lengkap Kode ditulis dengan C#. using using using using using

System; System.Collections.Generic; System.Linq; System.Text; System.Threading.Tasks;

class Node { public int data; public Node kiri; public Node kanan; } class Tree { public Node ReturnRoot(Node root) { return root; } public void add(ref Node root, int databaru) { if (root == null || root.data == 0) { Node Baru = new Node(); Baru.data = databaru; Baru.kiri = null; Baru.kanan = null; root = Baru; root.kiri = null; root.kanan = null; } else if (databaru < root.data) add(ref root.kiri, databaru); else if (databaru > root.data) add(ref root.kanan, databaru); else if (databaru == root.data) Console.WriteLine("Data Sudah Ada!"); } public void Preorder(Node Root)

8

{ if (Root != null) { Console.Write(Root.data + " "); Preorder(Root.kiri); Preorder(Root.kanan); } } public void Inorder(Node Root) { if (Root != null) { Inorder(Root.kiri); Console.Write(Root.data + " "); Inorder(Root.kanan); } } public void Postorder(Node Root) { if (Root != null) { Postorder(Root.kiri); Postorder(Root.kanan); Console.Write(Root.data + " "); } } } class Program { static void Main(string[] args) { int jumlah; Console.Write("Masukkan Jumlah Data"); Console.WriteLine(); Console.Write("Jumlah Data = "); jumlah = int.Parse(Console.ReadLine()); int[] elemen = new int[jumlah]; Node X = new Node(); Console.WriteLine(); Tree Array = new Tree(); for (int i = 0; i < jumlah; i++) { Console.Write("Elemen {0} = ", i + 1); elemen[i] = int.Parse(Console.ReadLine()); Array.add(ref X, elemen[i]); } Console.WriteLine(); Console.Write("Data Awal : "); for (int i = 0; i < jumlah; i++) { Console.Write("{0} ", elemen[i]); } Console.WriteLine(" "); Console.WriteLine(); Console.Write("Pre Order : "); Array.Preorder(Array.ReturnRoot(X)); Console.WriteLine(" ");

9

Console.Write("In Order : "); Array.Inorder(Array.ReturnRoot(X)); Console.WriteLine(" "); Console.Write("Post Order : "); Array.Postorder(Array.ReturnRoot(X)); Console.WriteLine(" "); Console.ReadLine(); } }

1 0...