4-Introduction to Tree, Binary Tree and Expression Tree-Kelvin Ricadson-2101691101

TREE

Merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubungan satu sama lainnya (disebut subtree). Untuk jelasnya, di bawah akan diuraikan istilah-istilah umum dalam tree :

1. Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.
2. Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.
3. Parent : predecssor satu level di atas suatu node.
4. Child : successor satu level di bawah suatu node.
5. Sibling : node-node yang memiliki parent yang sama dengan suatu node.
6. Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
7. Height : banyaknya tingkatan/level dalam suatu tree.
8. Degree : banyaknya child yang dimiliki suatu node

BINARY TREE

Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.

                                                       

PERFECT binary tree adalah pohon biner dimana setiap tingkat berada pada kedalaman yang sama.

                                               

COMPLETE binary tree adalah pohon biner dimana setiap tingkat,kecuali yang terakhir, terisi penuh,    dan semua simpul sejauh mungkin tertinggal.

                                       

SKEWED binary tree adalah pohon biner dimana masing – masing node memiliki paling banyak satu anak.

                                         

BALANCE binary tree adalah pohon biner dimana tidak ada daun yang jauh dari akar daripada daun. 

                                             

Property of Binary Tree

Untuk menghitung tinggi maximum (maksimal) dari tree dengan menggunakan rumus sebagai berikut  : 2^h+1 - 1. 

                                     

Representation of Binary Tree

Index on array represents node number

Index 0 is Root node

Index Left Child is 2p + 1, where p is parent index

Index Right Child is 2p + 2

Index Parent is (p-1)/2

                            

Prefix Traversal

Melakukan awalan atau postfix traversal di pohon ekspresi sederhana.

kekosongan awalan (struct tnode * curr) {
printf ("% c", curr-> chr);
if (curr-> left! = 0) awalan (curr-> left);
jika (curr-> right! = 0) awalan (curr-> right) ;?}
Dalam awalan, Anda harus mencetak / memproses sebelum anaknya diproses.

Postfix Traversal

void postfix(struct tnode *curr) {

               if ( curr->left  != 0 ) postfix(curr->left);

               if ( curr->right != 0 ) postfix(curr->right);
               printf( “%c“, curr->chr );

}

Dalam postfix, Anda harus mencetak/memproses setelah anaknya diproses.

Infix Traversal

void infix(struct tnode *curr) {

               if ( curr->left  != 0 ) infix(curr->left);

               printf( “%c“, curr->chr );

               if ( curr->right != 0 ) infix(curr->right);
}

Tampaknya benar, tetapi infix mungkin memiliki ambiguitas didahului operator tanpa tanda kurung.

Misalnya * + a b c dalam awalan akan dikodekan dalam infiks sebagai + b * c dengan kode sebelumnya, sedangkan infiks yang benar adalah (a + b) * c.
a + b * c: b dikalikan dengan c dan kemudian ditambahkan oleh a
(a + b) * c: a ditambahkan oleh b dan kemudian dikalikan dengan c

Prefix                    : *+abc

Postfix                  : ab+c*

Wrong infix         : a+b*c

Correct infix        : (a+b)*c