TREE PYTHON

A. Pengertian Tree
Tree merupakan salah satu bentukyang bersifat hirarkis (hubungan one to many) antara elemen- elemen. Tree bisa didentifikasi sebagai kumpulan simpul/ node dengan satu elemen khusus yang disebut root dan node lainnya terbagi menjadi himpunan

B. Inilah istilah- istilah umum yang terdapat pada codingan tree : 
      —  Parent : predecssor satu level di atas suatu node.

—  Child : successor satu level di bawah suatu node.

—  Sibling : node-node yang memiliki parent yang sama dengan suatu node.

—  Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.

—  Size : banyaknya node dalam suatu tree.

—  Height : banyaknya tingkatan/level dalam suatu tree.

—  Root : satu-satunya node khusus dalam tree yang tak punya predecssor.

—  Leaf : node-node dalam tree yang tak memiliki seccessor.

—  Degree : banyaknya child yang dimiliki suatu node.

 C. Contoh code Tree 

 

 

Hasil Run :

 

Ciri-ciri leaf adalah kedua pointernya bernilai nil , karena tidak menunjuk ke node manapun.

(1)    DeklarasiTree

                  Tree tersusun atas node-node, sehingga perlu kita deklarasikan adalah komponen node itu sendiri. Dalam contoh dibawah, akan kita namaiNode.

Berikut ini adalah contoh deklarasi obyek dalam binaryTree (dalam Pascal):

Type tipedata = integer;

Tree = ^node;

Node = record;

                data : tipedata;

                kiri, kanan : Tree;

                                                                                End;

                 Variabel data digunakan untuk menyimpan nilai angka node tersebut, sedangkan kiri dan kanan, bertipe pointer, masing-masing mewakili vektor yang akan menunjuk ke node anak kiri dan kanan.

(2)    InisialisasiTree

                   Untuk pertama kali, saat kita akan membuat sebuah pohon biner, asumsi awal adalah pohon itu belum bertumbuh, belum memilikinode sama sekali, sehingga masih kosong.

Pohon := Nil;

                Kita mendeklarasikan sebuah pointer yang akan menunjuk ke akar pohon yang kita buat, dengan nama Pohon. Pointer ini ditujukan untuk menunjuk struktur bertipe Node, yang telah dibuat pada bagian 1. Karena pohon tersebut sama sekali belum memiliki node, maka pointer Pohon ditunjukkan ke Nil.

(3)    Menambahkan Node PadaTree

                  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:

Ø  Jika pohon kosong, maka node baru ditempatkan sebagai akar pohon.

Ø  Jika pohon tidak kosong, maka dimulai darinode akar, dilakukan proses pengecekan berikut:

·         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.

·         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. Proses penambahan ini diimplementasikan secara rekursif pada fungsi berikut:

Procedure sisip_node(d : typedata; var  pohon : Tree);

                          Begin

                                                If pohon = nil then

                                                Begin

                                                                New(pohon);

Pohon^.data := d;

                                                                                                             Pohon^.kiri := nil;

Pohon^.kanan := nil;

                                                End

                                         else if pohon^.isi < d then sisip_node(d,Pohon^.kanan)

                               else if pohon^.isi > d then sisip_node(d,Pohon^.kiri);

                       end;

(4)    Membaca dan Menampilkan Node PadaTree

 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 NIL) mulai lagi dari langkah pertama, terapkan untuk kiri tersebut.

Ø  Jika kiri kosong (NIL), lanjut ke langkah ketiga.

3. Kunjungi kanan node tersebut,

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

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

b. Kunjungan In-Order.

1. Kunjungi kiri node tersebut,

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

Ø  Jika kiri kosong (NIL), lanjut ke langkah kedua.

2. Cetak isi (data) node yang sedang dikunjungi

3. Kunjungi kanan node tersebut,

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

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

c. Kunjungan Post-Order.

1. Kunjungi kiri node tersebut,

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

Ø  Jika kiri kosong (NIL), lanjut ke langkah kedua.

2. Kunjungi kanan node tersebut,

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

Ø  Jika kanan kosong (NIL), lanjut ke langkah ketiga.

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