Tree merupakan kumpulan dari 1 atau lebih node.
Dalam Tree,
- node paling atas disebut Root
- garis yang menghubungkan parent (orang tua) ke child (anak) disebut Edge
- node yang tidak memiliki children (anak) disebut Leaf
- node yang memiliki parent yang sama disebut Sibling
- degree dari node adalah total subtree dari node tersebut
- ketinggian / kedalaman suatu tree merupakan degree maksimum dari node dalam tree
- jika ada edge yang menghubungkan P ke Q maka P disebut Ancestor dari Q, sedangkan Q disebut Descendant dari P
Contoh Tree beserta keterangannya:
.jpg)
Keterangan :
- Degree dari Tree tersebut adalah 3
- Degree dari B adalah 2
- Height (ketinggian) = 3
- Parent (orang tua) dari C = A
- Children (anak) dari A = B, C, D
- Siblings (saudara) dari E = F
- Ancestor (leluhur) dari F = A, B
- Descendant (keturunan) dari B = E, F
- Root = A
- Leaf = E, F, G
Binary Tree
Binary Tree adalah rooted tree data structure dimana setiap node paling banyak memiliki 2 child.
2 child ini biasanya dibedakan menjadi left child dan right child.
Perbedaan Binary Tree dengan Binary Search Tree :
Binary Tree boleh tidak urut, jadi antara left child, parent dan right child nilainya bebas tidak harus urut.
Tetapi pada Binary Search Tree harus urut, left child harus lebih kecil dari parent dan right child harus lebih besar dari parentnya.
Tetapi pada Binary Search Tree harus urut, left child harus lebih kecil dari parent dan right child harus lebih besar dari parentnya.
Selain Binary, terdapat juga Unary dan Ternary.
Jenis - jenis Binary Tree:
- Perfect Biinary Tree : Binary Tree dimana setiap level punya node yang sama
- Complete Binary Tree : Binary Tree yang disalah satu levelnya boleh ada yang belum terisi, Perfect Binary Tree merupakan Complete Binary Tree
- Skewed Binary Tree : Binary Tree dimana setiap node memiliki paling banyak 1 child
Binary Tree dalam array:
Keterangan:
- Index pada array menunjukkan nomor node
- Index 0 adalah node Root
- Index left child adalah 2p + 1 dimana p adalah index parent
- Index right child adalah 2p + 2
- Index parent adalah (p - 1) / 2
Binary Tree dalam Linked List:
struct
node {
int data;
struct node *left;
struct node *right;
struct node *parent;
};
struct
node *root = NULL;
Prefix, Postfix, Infix
Prefix :
*+ab/-cde
Postfix : ab+cd-e/*
Infix :
(a+b)*((c-d)/e)
Cara mengubah Infix, Prefix dan Postfix.
Infix -> LVR
Prefix -> LRV
Postfix -> VLR
ingat KaBaTaKu (Kali Bagi Tambah Kurang)
contoh:
2 + a + (b / 2) * 3
maka:
prefix : + 2 + a * / b 2 3
postfix : 2 a b 2 / 3 * + *
tugas : c / a * 2 + 3 / 12 + 21
prefix : + / + / c * a 2 3 12 21
postfix : c a 2 * / 3 + 12 / 21 +
Implementasi Prefix dalam Linked List:
void
prefix(struct tnode *curr) {
printf(
“%c “, curr->chr );
if ( curr->left != 0 ) prefix(curr->left);
if ( curr->right != 0 )
prefix(curr->right);
}
}
Postfix :
void postfix(struct tnode *curr) {
if
( curr->left != 0 )
postfix(curr->left);
if
( curr->right != 0 ) postfix(curr->right);
printf( “%c“, curr->chr );
printf( “%c“, curr->chr );
}
Infix:
void infix(struct tnode *curr) {
if
( curr->left != 0 )
infix(curr->left);
printf( “%c“, curr->chr );
if
( curr->right != 0 ) infix(curr->right);
}
}
No comments:
Post a Comment