TREE ALGORITMA & STRUKTUR DATA
Materi ASD Fakultas Teknik Elektro & Komputer UKSW (www.uksw.edu) Download Dari : http://ambonmemanggil.blogspot.com
1
TREE • ISTILAH-ISTILAH DASAR: – tree : kumpulan elemen yang disebut simpul (nodes). – tree dapat juga kosong – Tree terdiri dari elemen yang disebut akar (root) dan tanpa atau lebih subtree t1,t2,…,tk yang masing masing dihubungkan dengan garis dari akar
2
BAGIAN-BAGIAN TREE Nodes/simpul
3
BAGIAN-BAGIAN TREE parent node
4
BAGIAN-BAGIAN TREE child nodes
parent node sibling
Sibling: node dengan orang tua yang sama 5
BAGIAN-BAGIAN TREE child nodes
parent node Ancestor Descendant
6
BAGIAN-BAGIAN TREE root node
leaf nodes
7
BAGIAN-BAGIAN TREE sub-tree
8
BAGIAN-BAGIAN TREE sub-tree
9
LEVEL level 0 level 1 level 2 level 3 Depth: level maksimum node daun 10
BAGIAN-BAGIAN TREE
11
HUBUNGAN HIRARKIS DIREKTORY FILE
12
HUBUNGAN HIRARKIS KAMPUS
KELUARGA
13
IMPLEMENTASI TREE typedef struct TreeNode * PtrToNode; struct TreeNode { ElementType element; PtrToNode FirstChild; PtrToNode NextSibling; }; 14
FirstChild pointer: panah yang menunjuk ke bawah NextSibling pointer: panah dari kiri ke kanan
15
TREE TRAVERSAL • 3 METODE TRAVERSAL – POST ORDER – PREORDER – INORDER
16
PREORDER TRAVERSAL
17
POST ORDER TRAVERSAL
18
POST ORDER TRAVERSAL
19
POST ORDER TRAVERSAL
20
Preorder: +/+AB*CD*EFGH Inorder : A+B/C*DE*FG+H Postorder: AB+CD*/EFG*H+
+
H
/
*
+ A
* B
C
E D
F
G 21
BINARY TREE • binary tree adalah tree dengan node
maksimal memiliki 2 anak. • binary tree disebut strictly binary tree jika setiap node yang bukan node daun memiliki substree kiri dan kanan. – setiap node selain node daun memiliki 2 anak.
• complete binary tree dengan kedalaman d adalah strictly binary tree dengan semua node daun memiliki level d.
22
IMPLEMENTASI BINARY TREE typedef struct TreeNode *PtrToNode; typedef struct TreeNode *Tree; struct TreeNode { ElementType Element; Tree Left; Tree Right; }; 23
EKSPRESI TREE Expression tree for (a+b*c) +((d*e+f)*g)
24
EKSPRESI TREE Algoritma konversi ekspresi postfix ke tree masukan: ab+cde+**
25
EKSPRESI TREE
? 26
Binary Search Trees
• Untuk setiap node, X, dalam tree,
semua nilai kunci yang berada disubstree kiri lebih kecil dibanding nilai kunci X dan semua nilai kunci di substree kanan lebih besar dibanding nilai kunci X.
√
X 27
IMPLEMENTASI BST struct TreeNode; typedef struct TreeNode *Position; typedef struct TreeNode *SearchTree; SearchTree MakeEmpty( SearchTree T ); Position Find( ElementType X, SearchTree T ); Position FindMin( SearchTree T ); Position FindMax( SearchTree T ); SearchTree Insert( ElementType X, SearchTree T ); SearchTree Delete( ElementType X, SearchTree T ); ElementType Retrieve( Position P ); 28
IMPLEMENTASI BST struct TreeNode { ElementType Element; SearchTree Left; SearchTree Right; };
29
Make Empty SearchTree MakeEmpty( SearchTree T ) { if( T != NULL ) { MakeEmpty( T→Left ); MakeEmpty( T→ Right ); free( T ); } return NULL; } 30
Find Position Find( ElementType X, SearchTree T ) { if( T == NULL ) return NULL; if ( X < T → Element ) return Find( X, T → Left ); else if ( X > T → Element ) return Find( X, T → Right ); else return T; } 31
FindMin Position FindMin( SearchTree T ) { if ( T == NULL ) return NULL; else if( T → Left == NULL ) return T; else return FindMin( T → Left ); }
32
FindMax Position FindMax( SearchTree T ) { if ( T != NULL ) while ( T → Right != NULL ) T = T → Right; return T; }
33
Insert
34
Insert SearchTree Insert( ElementType X, SearchTree T ) { if ( T == NULL ) { T = malloc( sizeof( struct TreeNode ) ); if ( T == NULL ) FatalError( "Out of space!!!" ); else { T → Element = X; T → Left = T → Right = NULL; } }
35
Insert else if ( X < T → Element ) T → Left = Insert( X, T → Left ); else if( X > T → Element ) T → Right = Insert( X, T → Right ); /* Else X is in the tree already; we'll do nothing */ return T; /* Do not forget this line!! */ } 36
Delete Hapus angka '4'
37
Delete SearchTree Delete( ElementType X, SearchTree T ) { Position TmpCell; if ( T == NULL ) Error( "Element not found" ); else if ( X < T → Element ) /* Go left */ T → Left = Delete( X, T → Left ); else if ( X > T → Element ) /* Go right */ T → Right = Delete( X, T → Right ); else /* Found element to be deleted */
38
Delete if ( T {
→ Left && T → Right ) /* Two children */ TmpCell = FindMin( T → Right ); T → Element = TmpCell → Element; T → Right = Delete( T → Element, T → Right );
} else /* One or zero children */ { TmpCell = T; if ( T → Left == NULL ) /* Also handles 0 children */ T = T → Right; else if ( T → Right == NULL ) T = T → Left; free( TmpCell );
} return T; }
39
