Data structure materi struktur data Tree.ppt

Materi struktur data tree

1. STRUKTUR DATA
Tree (Pohon)

2. OUTLINE
1.Pengertian Tree Structure?
2.Binary Tree & implementasinya
3.Tree Traversal
4.Implementasi tree (selain binary tree)

3. APAKAH TREE STRUCTURE ITU ?
Konsep struktur data yang terdiri dari akar dan simpul-simpul yang berada di bawahnya
Struktur data yang menunjukkan hubungan bertingkat (memiliki hierarkhi)
Contoh: struktur organisasi, silsilah keluarga
Warek I Warek II Warek III
Rektor

4. APAKAH TREE STRUCTURE ITU ?
Contoh: direktori/folder pada windows
My PicturesMy Music Struktur data
Pointer & StructureLinked list
My Document
Tree

5. KOMPONEN PADA TREE
1
3
7
10
2
4 5 6
8 9
node root
leaf
leaf
leaf
node
node
leaf
leaf
leafleaf
leaf
subtree

6. HUBUNGAN ANTAR KOMPONEN
Hubungan antar elemen: parent-
child, father-son, mother-daughter
Nama node: nama(angka) yang
dipakai untuk membedakan sebuah
node dengan node yang lain. Dalam
kuliah ini adalah angka yang tertulis
dalam lingkaran.
Label: nilai yang diingat oleh sebuah
node　　　　　
Tree vs Graph
Tree: setiap node kecuali root
hanya memiliki sebuah parent
Graph: dapat memiliki lebih dari
sebuah parent
1
3
7
10
4 5 6
8 9
node
root
leaf
leaf
leafleaf
leaf
node
node
2
Contoh graph

7. HUBUNGAN ANTAR KOMPONEN
sibling：node-node yang
memiliki parent yang sama
Ancestor dari node x：
node yang ditemukan, ketika
menyusuri tree ke atas
dari node x
Descendant dari node x：
node yang ditemukan ketika
menyusuri tree ke bawah
dari node x
1
3
7
10
2
4 5 6
8 9
node
root
leaf
leaf
leafleaf
leaf
node
node

8. HUBUNGAN ANTAR KOMPONEN
sibling：node-node
yang memiliki parent
yang sama
Ancestor dari node x：
node yang ditemukan,
ketika menyusuri tree ke
atas dari node x
Descendant dari node
x： node yang
ditemukan ketika
menyusuri tree ke
bawah dari node x
1
3
7
10
2
4 5 6
8 9
node
root
leaf
leaf
leafleaf
leaf
node
node

9. HUBUNGAN ANTAR KOMPONEN
sibling：node-node yang
memiliki parent yang sama
Ancestor dari node x：
node yang ditemukan,
ketika menyusuri tree ke
atas dari node x
Descendant dari node
x： node yang
ditemukan ketika
menyusuri tree ke bawah
dari node x
1
3
7
10
2
4 5 6
8 9
node
root
leaf
leaf
leafleaf
leaf
node
node

10. LEVEL
1
3
7
10
2
4 5 6
8 9
0
1
2
3

11. DERAJAT
1
3
7
10
2
4 5 6
8 9
3
2
1
0

12. DEFINISI TREE
Sebuah tree didefinisikan sebagai struktur y ang dibentuk secara
recursive oleh kedua rule berikut:
1.Sebuah node adalah sebuah tree. Node satu-satunya pada tree ini
berfungsi sebagai root maupun leaf.
2.Dari k buah tree T
1
～T
k
, dan masing-masing memiliki root n
1
～n
k
.
3.Jika node n adalah parent dari node n
1
～n
k
, akan diperoleh sebuah
tree baru T yang memiliki root n. Dalam kondisi ini, tree T
1～
T
kmenjadi sub-tree dari tree T. Root dari sub-tree n
1～n
kadalah
child dari node n .
1
Tree
leaf
root
node

13. DEFINISI TREE
Sebuah tree didefinisikan sebagai struktur y ang dibentuk secara
recursive oleh kedua rule berikut:
1.Sebuah node adalah sebuah tree. Node satu-satunya pada tree
ini berfungsi sebagai root maupun leaf.
2.Dari k buah tree T
1～T
k , dan masing-masing memiliki root n
1～
n
k.Jika node n adalah parent dari noden
1～n
k, akan diperoleh
sebuah tree baru T yang memiliki root n. Dalam kondisi ini, tree
T
1～T
kmenjadi sub-tree dari tree T. Root dari sub-tree n
1～
n
kadalah child dari node n .
１
２ ３ ４
５ ６
T1 n1 T2
n2 1
2
3
1
T3
n3 n4
T4
2
1
3

14. DEFINISI TREE
2.Dari k buah tree T
1
～T
k
, dan masing-masing memiliki root
n
1
～n
k
.Jika node n adalah parent dari noden
1
～n
k
, akan
diperoleh sebuah tree baru T yang memiliki root n. Dalam
kondisi ini, tree T
1～T
kmenjadi sub-tree dari tree T. Root
dari sub-tree n
1
～n
k
adalah child dari node n .
2
6 7 8
12 13
T1 n1 T2
n2
5
T3
n3 n4
T4
n
T
4
11
14
9 10
3
1

15. ORDERED VS UNORDERED TREE
Ordered tree
Antar sibling terdapat urutan “usia”
Node yang paling kiri berusia paling tua (sulung), sedangkan
node yang paling kanan berusia paling muda (bungsu)
Posisi node diatur atas urutan tertentu
Unordered tree
Antar sibling tidak terdapat urutan tertentu

16. OUTLINE
1.Pengertian Tree Structure?
2.Binary Tree & implementasinya
3.Tree Traversal
4.Implementasi tree (selain binary tree)

17. DEFINISI BINARY TREE
1.Sebuah tree yang kosong juga merupakan sebuah binary tree
2.Binary tree harus memenuhi salah satu syarat berikut
Tidak memiliki anak
Memiliki subtree di sebelah kiri (left subtree)
Memiliki subtree di sebelah kanan (right subtree)
Memiliki baik left subtree maupun right subtree
a a
b
a
b
a
cb
a
b
HATI-HATI DALAM MENGGAMBAR BINARY TREE

18. IMPLEMENTASI BINARY TREE DALAM
BAHASA C
ERNA PIANTARI
10/09/25

19. leftrightlabelstruct node {
struct node *left;
struct node *right;
mydata label;
}
a
cb
a
b c
IMPLEMENTASI BINARY TREE

20. CONTOH
A
H
B
C
F
D
E
G
A
H
B
C
F
D
E
G
1418A
2638B H
C 5678D
100 E F
G
10
14 18
26 38
56 78
100
10
14
18
26 38
56 78
100

21. LATIHAN 1
Gambarkan implementasi dari binary tree berikut
DC
G
A
F
E
JI
H
B
10
20
30
40 50 60 70
80
90
100

22. OUTLINE
1.Pengertian Tree Structure?
2.Binary Tree & implementasinya
3.Tree Traversal
4.Implementasi tree (selain binary tree)

23. DEFINISI TREE TRAVERSAL
Teknik menyusuri tiap node dalam sebuah tree secara
sistematis, sehingga semua node dapat dan hanya satu
kali saja dikunjungi
Ada tiga cara traversal
preorder
inorder
postorder
Untuk tree yang kosong, traversal tidak perlu dilakukan

24. PREORDER
1.Visit the root
2.Traverse the left subtree
3.Traverse the right subtree
A
H
B
C
F
D
E
G
A
H
B
C
F
D
E
G
A→B→C→D→E→G→F→H

25. struct node {
struct node *left;
struct node *right;
char label;
}
void preorder(struct node *p)
{
if (p==NULL) return; jika empty-tree, tidak perlu lakukan apa-apa
printf(“visit %c ”, p->label); tampilkan label node yang dikunjungi
preorder(p->left); traverse the left subtree
preorder(p->right);　　　　 traverse the right subtree
}

26. INORDER
1.Traverse the left subtree
2.Visit the root
3.Traverse the right subtree
A
H
B
C
F
D
E
G
A
H
B
C
F
D
E
G

27. IMPLEMENTASI DALAM BAHASA C
struct node {
struct node *left;
struct node *right;
char label;
}
void inorder(struct node *p)
{
if (p==NULL) return; jika empty-tree, tidak perlu lakukan apa-apa
inorder(p->left); traverse the left subtree
printf(“visit %c ”, p->label); tampilkan label node yang dikunjungi
inorder(p->right);　　　　 traverse the right subtree
}

28. POSTORDER
1.Traverse the left subtree
2.Traverse the right subtree
3.Visit the root
A
H
B
C
F
D
E
G
A
H
B
C
F
D
E
G

29. IMPLEMENTASI DALAM BAHASA C
struct node {
struct node *left;
struct node *right;
char label;
}
void postorder(struct node *p)
{
if (p==NULL) return; jika empty-tree, tidak perlu lakukan apa-apa
postorder(p->left); traverse the left subtree
postorder(p->right);　　　　 traverse the right subtree
printf(“visit %c ”, p->label); tampilkan label node yang dikunjungi
}

30. 1. Visit the root
2. Traverse the left subtree
3. Traverse the right
subtree
1. Traverse the left
subtree
2. Visit the root
3. Traverse the right
subtree
1. Visit the root
2. Traverse the left subtree
3. Traverse the right
subtree

31. 10/09/25

32. LATIHAN-2
A
B
C
G
D
E
F H
LK
I
J
Tuliskan hasil preorder, inorder dan postorder traversal
untuk binary tree berikut.

33. OUTLINE
1.Apakah Tree Structure itu ?
2.Binary Tree & implementasinya
3.Tree Traversal
4.Implementasi tree (selain binary tree)

34. N-TREE
STRUKTUR DATA
10/09/25ERNA PIANTARI

35. TEKNIK IMPLEMENTASI TREE LAINNYA
Binary tree hanya memiliki dua anak: kiri dan kanan. Karena
itu implementasinya hanya memerlukan dua buah pointer
untuk masing-masing subtree.
 Untuk implementasi tree yang memiliki sebarang anak,
dapat dilakukan dengan berbagai cara

36. CONTOH
1
2 6
3 54

37. 1 23
IMPLEMENTASI 1 , LABEL || CHILD
1
2 6
3 54
2 77
3
4
5
6
5 37 35
1087 1595 25
3
5
10
15
25
35
23 37
77 87 95
labelchild
struktur yang
Merepresentasikan node
　　　　　　　　　　　　
　
struktur yang merepresentasikan
koneksi antar node　　　　　　
　　　　　　　

38. 1
2 6
3 54
labelchildsibling
11001
210031002 6
1000
1001 1002
3 1004
1003
4 1005
1004
5
1005
Implementasi 2 memakai model binary-tree, label || child || sibling

39. 1
2 6
3 54
IMPLEMENTASI MEMAKAI BINARY-TREE
11001
210031002 6
1000
1001 1002
3 1004
1003
4 1005
1004
5
1005

40. IMPLEMENTASI MEMAKAI BINARY-TREE
11001
210031002 6
1000
1001 1002
3 1004
1003
4 1005
1004
5
1005
1
2
6
3
5
4
Rotasi ke kanan 45°

41. LATIHAN
EC H
G
KJ
I
10
50
300
100 200 350 400
450 500
D150
F250
A
B
Jelaskan bagaimana proses
implementasi tree berikut!
a.Implementasi 1
b.Implementasi 2

42. SELESAI
10/09/25ERNA PIANTARI

43. 10/09/25
JENIS-JENIS KHUSUS BINARY TREE
Full Binary Tree : Binary tree yang setiap nodenya memiliki dua clid dan setiap
subtree memiliki panjang path yang sama
Complete Binary Tree : Setiap node memiliki dua clid namun setiap subtree
boleh memiliki Panjang yang berbeda
Skewed Binary Tree : Binary tree yang semua nodenya hanya memiliki 1 child,
kecuali leaf

44. OPERASI TREE
Create : untuk membuat binary tree baru yang masih kosong
Insert ; memasukan node kedalam tree, bis sebagai root, left child atau right child,
jika sebagai root maka harus kosong
Clear : mengosongkan binary tree yang sudah ada
Empty : memeriksa apakah binary treenya kosong
Find ; mencari root, parent, left child atau right child
Update : mengubah isi dari node
Retrive : mengetahui isi node yang ditunjuk pointer current
deleteSub : menghapus subree (node beserta descendantnya)
Characteristic : mengetahui karakteristik dari tree (ukuran, height average length)
Transverse : mengunjungi node pada tree (pre orderm in order dan post order)
10/09/25

45. 10/09/25
CREATE BINARY TREE
typedef struct {
struct node *left;
struct node *right;
int label;
}node;
void createTree ( node * T, int data) {
node *new;
new = (node *) malloc (sizeof (node));
new->label = data;
new->left = NULL;
new-> right = NULL;
T = new;
}

46. 10/09/25
INSERT KIRI
void tambahKiri (tree *T, int dataBaru){
node *baru;
baru = (node *) malloc (sizeof (node));
baru -> data = dataBaru
baru->left = NULL;
baru->right =NULL;
if (T->left == NULL){
T->left = baru;
}
else {
tree * subtree;
subtree = T->left;
while (subtree->left !=NULL)
subtree = subtree->left;
subtree->left = baru;
}
}

47. 10/09/25
Buat Insert Kanan!!

48. 10/09/25
DELETE TREE
void delAll (node *root){
if (root!=NULL);
dellAll(root->left);
dellAll(root->right);
free (root);
}
void delKanan (simpul * root){
if (root!=NULL){
if (root->right !=NULL){
dellAll(root->right);
}
}
}

49. ILUSTRASI BINARY TREE UNTUK
ARITMATIKA
10/09/25

50. 10/09/25

51. 10/09/25

52. 10/09/25

53. 10/09/25

54. 10/09/25

55. 10/09/25

56. 10/09/25

57. 10/09/25

58. 10/09/25

59. 10/09/25

60. 10/09/25

61. 10/09/25

62. 10/09/25

63. 10/09/25

64. 10/09/25

65. 10/09/25

66. 10/09/25

67. BINARY SEARCH TREE
10/09/25

68. PENGERTIAN
Sama dengan ordered binary Tree
Untuk memudahkan proses pencarian, binary serach tree memiliki sifat bahwa
semua left child harus lebih kecil daripada right child dan parentnya. Juga semua
right child harus lebih besar dari left child serta parentnya. 
10/09/25

69. 10/09/25
INSERT DALAM BINARY TREE

70. 10/09/25
INSERT BINARY TREE
5
5
5

71. DELETE
10/09/25

72. DELETE
10/09/25