complete tree

Apa yang dimaksud dengan

a. complete tree

b. binary tree
c. full binary tree
d. complete binary tree
e. perfect binary tree

Berikan contohnya masing-masing !

 Jawab:

a)Complete tree adalah tree dimana semua node leafnya berada pada depth n atau n-1 dan semua leaf yang berada pada depth n berada di sisi kiri.

Gambar : Complete Tree

b) Binary tree adalah tree dengan syarat bahwa tiap node harusnya boleh        memilki maksimal dua subtree ( left dan right subtree ) dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.

Binary tree adalah sebuah strukutur data yang berguna saat kita harus membuat keputusan 2 arah pada setiap titik pada suatu proses. Sebagai contoh, apabila kita ingin mencari angka yang sama dalam sebuah daftar yang berisi angka. Salah satu caranya adalah dengan menbandingkan setiap angka dengan seluruh angka yang ada dalam daftar.  Akan tetapi, cara ini melibatkan proses perbandingan dalam jumlah besar.

Jumlah perbandingan dapat direduksi dengan menggunakan binary tree. Bilangan pertama pada daftar dijadikan sebuah node sebagai root dari  binary tree dengan left dan right subtree yang kosong. Setiap angka dalam list kemudian dibandingkan dengan angka pada root.

a.       Jika sama, maka kita mendapatkan angka yang sama (duplikatnya).

b.      Jika lebih kecil, kita tempatkan sebagai left subtree

c.       Jika lebih besar, kita tempatkan sebagai right subtree

Kalau subtree masih kosong, dan angka yang sedang dicek belum ada di tree, maka angka tersebut kita tempatkan dalam sebuah node pada subtree tersebut. Kalau subtree tidak kosong, , kita bandingkan lagi dengan nilai root pada subtree, lalu proses diulang kembali dari awal.

Gambar : Binary Tree

Contoh penggunaannya:

/*baca bilangan pertama pada list, kemudian tempatkan pada node tunggal binary tree*/

scanf(“%d”, &number);

tree=maketree(number);

while(there are numbers left in the input)

{

                        i.   scanf(“%d”, &number);

                      ii.   p=q=tree;

                    iii.   while(number!=info(p)&&q!=NULL)

                      iv.   {

1.  p=q;

a.  if(number<info(p))

2.  q=left(p);

a.  else

3.  q=right(p);

                        v.   }/*end while*/

                      vi.   if (number==info(p)) printf(“%d %s), number, “is a duplicate”);

                    vii.   /*insert number to the left or the right of  p*/                                    

else if(number<info(p))

setleft(p, number);

else

setright(p, number);

} //end while

c)  Full binary tree adalah binary tree yang setiap nodenya ( kecuali leaf ) memilki      dua child dan tiap subtree harus mempunyai panjang path yang sama.

Contoh :

d)  Complete binary tree adalah stricly binary tree yang semua leafnya berada pada  level depth.

Contoh :

e)      Perfect binary tree adalah tree yang tiap levelnya memiliki jumlah node yang maksimum (biasanya simetris).

Contoh :

Gambar : Perfect Binary Tree

3.  Apa yang dimaksud dengan
a. tree traversal
b. in-order traversal
c. post-order traversal
d. level-order traversal
Berikan contohnya masing-masing!

Jawab :

a.  Tree traversal adalah proses mengunjungi seluruh node-node pada tree, masing-masing sekali. Hasilnya adalah urutan informasi secara linear yang tersimpan dalam tree.

Contoh :

Gambar : Tree Transversal

b.  In-order traversal

inorder (symmetric order) :

·         Traverse subtree kiri secara inorder

·         Kunjungi root

·         Traverse subtree kanan secara inorder

Contoh :

c.   Post-order traversal

postorder :

·         Traverse subtree kiri secara postorder

·         Traverse subtree kanan secara postorder

·         Kunjungi root

Contoh :

d.  Level-order traversal

preorder (depth-first order) ditunjukkan oleh tiga operasi berikut:

·         Kunjungi root

·         Traverse subtree kiri secara preorder

·         Traverse subtree kanan secara preorder

Contoh :