Dalam istilah ilmu komputer, sebuah struktur data adalah cara penyimpanan, penyusunan dan pengaturan data di dalam media penyimpanan komputer sehingga data tersebut dapat digunakan secara efisien.
Dalam teknik pemrograman, struktur data berarti tata letak data yang berisi kolom-kolom data, baik itu kolom yang tampak oleh pengguna (user) atau pun kolom yang hanya digunakan untuk keperluan pemrograman yang tidak tampak oleh pengguna. Setiap baris dari kumpulan kolom-kolom tersebut dinamakan catatan (record). Lebar kolom untuk data dapat berubah dan bervariasi. Ada kolom yang lebarnya berubah secara dinamis sesuai masukan dari pengguna, dan juga ada kolom yang lebarnya tetap. Dengan sifatnya ini, sebuah struktur data dapat diterapkan untuk pengolahan database (misalnya untuk keperluan data keuangan) atau untuk pengolah kata (word processor) yang kolomnya berubah secara dinamis. Contoh struktur data dapat dilihat pada berkas-berkas lembar-sebar (spreadsheet), pangkal-data (database), pengolahan kata, citra yang dipampat (dikompres), juga pemampatan berkas dengan teknik tertentu yang memanfaatkan struktur data.
- Pengertian Data Array adalah Array merupakan tipe data terstruktur yang berguna untuk menyimpan sejumlah data yang bertipe sama. Bagian yang menyusun array disebut elemen array, yang masing-masing elemen dapat diakses tersendiri melalui indeks array.
- Pengertian Data Stach adalahSecara sederhana stack bisa diartikan dengan
• sebagai tumpukan dari benda
• sekumpulan data yang seolah-olah diletakkan di atas data yang lain
• koleksi dari objek-objek homogen
Dalam suatu stack terdapat 2 operasi utama, yaitu operasi push (memasukkan node ke dalam stack), dan pop (mengambil node dari stack), data melalui ujung yang sama (TOS, Top Of Stack), ujung ini merupakan ujung atas stack. - Pengertian Linked List adalah salah satu bentuk struktur data, berisi kumpulan data (node) yang tersusun secara sambung menyambung, dinamis dan terbatas.
Linked List sering disebut juga Senarai Berantai
Linked List saling terhubung dengan bantuan variabel pointer
Masing-masing data dalam Linked List disebut dengan node (simpul) yang menempati alokasi memori secara dinamis dan biasanya berupa struct yang terdiri dari beberapa field.
Gambar tersebut menunjukkan Linked List tunggal atau ’singly-linked list’ dimana tiap simpul hanya memiliki satu taut (link) yang merujuk ke simpul berikutnya atau nilai null pada akhir simpul. Seranai berantai ini hanya bisa diakses maju dari awal simpul ke akhir simpul.
Operasi-Operasi yang ada pada Linked List
Insert
Istilah Insert berarti menambahkan sebuah simpul baru ke dalam suatu linked list.
IsEmpty
Fungsi ini menentukan apakah linked list kosong atau tidak.
Find First
Fungsi ini mencari elemen pertama dari linked list
Find Next
Fungsi ini mencari elemen sesudah elemen yang ditunjuk now
Retrieve
Fungsi ini mengambil elemen yang ditunjuk oleh now. Elemen tersebut lalu dikembalikan oleh fungsi.
Update
Fungsi ini mengubah elemen yang ditunjuk oleh now dengan isi dari sesuatu
Delete Now
Fungsi ini menghapus elemen yang ditunjuk oleh now. Jika yang dihapus adalah elemen pertama dari linked list (head), head akan berpindah ke elemen berikut.
Delete Head
Fungsi ini menghapus elemen yang ditunjuk head. Head berpindah ke elemen sesudahnya.
Clear
Fungsi ini menghapus linked list yang sudah ada. Fungsi ini wajib dilakukan bila anda ingin mengakhiri program yang menggunakan linked list. Jika anda melakukannya, data-data yang dialokasikan ke memori pada program sebelumnya akan tetap tertinggal di dalam memori.Operasi-operasi untuk Stack dengan Linked List
IsEmpty
Fungsi memeriksa apakah stack yang adamasih kosong.
Push
Fungsi memasukkan elemen baru ke dalam stack. Push di sini mirip dengan insert dalam single linked list biasa.
Pop
Fungsi ini mengeluarkan elemen teratas dari stack.
Clear
Fungsi ini akan menghapus stack yang ada.Operasi-operasi Queue dengan Double Linked List
IsEmpty
Fungsi IsEmpty berguna untuk mengecek apakah queue masih kosong atau sudah berisi data. Hal ini dilakukan dengan mengecek apakah head masih menunjukkan pada Null atau tidak. Jika benar berarti queue masih kosong.
IsFull
Fungsi IsFull berguna untuk mengecek apakah queue sudah penuh atau masih bisa menampung data dengan cara mengecek apakah Jumlah Queue sudah sama dengan MAX_QUEUE atau belum. Jika benar maka queue sudah penuh.
EnQueue
Fungsi EnQueue berguna untuk memasukkan sebuah elemen ke dalam queue (head dan tail mula-mula meunjukkan ke NULL).
DeQueue
Procedure DeQueue berguna untuk mengambil sebuah elemen dari queue. Hal ini dilakukan dengan cara menghapus satu simpul yang terletak paling depan (head).
Single Linked List Circular
Single Linked List Circular (SLLC) adalah Single Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut terdiri dari beberapa node, maka pointer next pada node terakhir akan menunjuk ke node terdepannya.
Pengertian:
Node : rangkaian beberapa simpul
Single : artinya field pointer-nya hanya satu buah saja dan satu arah.
Linked List : artinya node-node tersebut saling terhubung satu sama lain.
Circular : artinya pointer next-nya akan menunjuk pada dirinya sendiri sehingga berputar
Ilustrasi SLLC
Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya, dan juga memiliki field yang berisi data. Pada akhir linked list, node terakhir akan menunjuk ke node terdepan sehingga linked list tersebut berputar.
Deklarasi:
Deklarasi node dibuat dari struct berikut ini:
typedef struct TNode{
int data;
TNode *next;
};Pembentukan node baru
Digunakan keyword new yang berarti mempersiapkan sebuah node baru
berserta alokasi memorinya.TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = baru;Dibutuhkan satu buah variabel pointer: head
Head akan selalu menunjuk pada node pertama
Penambahan data di depan
Penambahan node baru akan dikaitan di node paling depan, namun pada saat pertama kali (data masih kosong), maka penambahan data dilakukan pada head nya.
Pada prinsipnya adalah mengkaitkan data baru dengan head, kemudian head akan menunjuk pada data baru tersebut sehingga head akan tetap selalu menjadi data terdepan. Untuk menghubungkan node terakhir dengan node terdepan dibutuhkan pointer bantu.
HEAD Single Linked List Circular
Penambahan data di depan
Penambahan data di depan
void insertDepan(int databaru){
TNode *baru,*bantu;
baru = new TNode;
baru->data = databaru;
baru->next = baru;
if(isEmpty()==1){
head=baru;
head->next=head;
}
else {
bantu = head;
while(bantu->next!=head){
bantu=bantu->next;
}
baru->next = head;
head = baru;
bantu->next = head;
}
printf(”Data masuk\n“);
}
Penambahan data di belakang
Penambahan data dilakukan di belakang, namun pada saat pertama kali data langsung ditunjuk pada head-nya.
Penambahan di belakang lebih sulit karena kita membutuhkan pointer bantu untuk mengetahui data terbelakang, kemudian dikaitkan dengan data baru. Untuk mengetahui data terbelakang perlu digunakan perulangan.
Penambahan data di belakang
void insertBelakang (int databaru){
TNode *baru,*bantu;
baru = new TNode;
baru->data = databaru;
baru->next = baru;
if(isEmpty()==1){
head=baru;
head->next=head;
}
else {
bantu = head;
while(bantu->next != head){
bantu=bantu->next;
}
bantu->next = baru;
baru->next = head;
}
printf(”Data masuk\n“);
}Operasi Penghapusan
Penghapusan node dilakukan dengan memutus rantai node kemudian menghapus node. Jika node berada di tengah rangkaian, rangkaian yang terputus perlu disambung kembali. Untuk memudahkan penghapusan simpul dibutuhkan dua cursor sebagai simpul bantu. Selain cursor juga dibutuhkan simpul head sebagai acuan awal simpul dalam rangkaian.
Berikut langkah langkah untuk menghapus simpul dalam rangkaian: - Buat cursor bantu yang menunjuk ke awal node(simpul).
- Pindahkan cursor ke node berikutnya
- Putus sambungan awal node dengan node berikutnya.
- Hapus rangkaian
- Jika berada di akhir rangkaian, putuskan dari rangkaian sebelumnya
- Jika di tengah rangkaian, pindahkan penunjukan node berikutnya, atau di akhir, atau setelah node yang akan dihapus
Ilustrasi Hapus Depan
Ilustrasi Hapus Depan
void hapusDepan (){
TNode *hapus,*bantu;
if (isEmpty()==0){
int d;
hapus = head;
d = head->data;
if(head->next != head){
bantu = head;
while(bantu->next!=head){
bantu=bantu->next;
}
head = head->next;
delete hapus;
bantu->next = head;
}else{
head=NULL;
}
printf(“%d terhapus\n“,d);
} else printf(”Masih kosong\n“);
}
Ilustrasi Hapus Belakang
Ilustrasi Hapus Belakang
void hapusBelakang(){
TNode *hapus,*bantu;
if (isEmpty()==0){
int d;
hapus = head;
if(head->next == head){
head = NULL;
}else{
bantu = head;
while(bantu->next->next != head){
bantu = bantu->next;
}
hapus = bantu->next;
d = bantu->data;
bantu->next = head;
delete hapus;
}
printf(“%d terhapus\n“,d);
} else printf(”Masih kosong\n“);
}
Contoh Coding Stack Dengan Linked List
#include
#include
/* membuat linked list */
typedef struct myLinkedList {
char nim[10];
char nama[35];
int nilai;
myLinkedList *next;
};
myLinkedList *head;
/* keadaan awal */
void init() {
head = NULL;
}
/* fungsi untuk mengecek linked list
* apakah kosong atau tidak
* jika kosong maka bernilai 1
* jika tidak kosong maka bernilai 0
*/
int paKosong() {
if (head == NULL) return 1;
else return 0;
}
/**
* fungsi untuk menambahkan data dari depan node
*/
void tambahDepan() {
myLinkedList *baru;
baru = new myLinkedList;
cout << “Masukkan Data lengkap di bawah ini : ” <<>> baru->nim;
cout << “Nama : “; cin >> baru->nama;
cout << “Nilai : “; cin >> baru->nilai;
baru->next = NULL;
if (paKosong() == 1) {
head = baru;
head->next = NULL;
} else {
baru->next = head;
head = baru;
}
}
/**
* fungsu untuk menambahkan data dari depan node
*/
void tambahBelakang() {
myLinkedList *baru, *bantu;
baru = new myLinkedList;
cout << “Masukkan Data lengkap di bawah ini : ” <<>> baru->nim;
cout << “Nama : “; cin >> baru->nama;
cout << “Nilai : “; cin >> baru->nilai;
baru->next = NULL;
if (paKosong() == 1) {
head = baru;
head->next = NULL;
} else {
bantu = head;
while (bantu->next != NULL) {
bantu = bantu->next;
}
bantu->next = baru;
}
}
/**
* fungsi untuk menghapus dari depan node
*/
void hapusDepan() {
myLinkedList *hapus;
char *data;
if (paKosong() == 0) {
if (head->next != NULL) {
hapus = head;
data = hapus->nim;
head = head->next;
delete hapus;
} else {
data = head->nim;
head = NULL;
}
cout <<>
/**
* fungsi untuk menghapus dari belakang node
*/
void hapusBelakang() {
myLinkedList *hapus, *bantu;
char *data;
if (paKosong() == 0) {
if (head->next != NULL) {
bantu = head;
while(bantu->next->next != NULL) {
bantu = bantu->next;
}
hapus = bantu->next;
data = hapus->nim;
bantu->next = NULL;
delete hapus;
} else {
data = head->nim;
head = NULL;
}
cout <<>
cout << “Tekan Enter untuk kembali ke Menu!”; getch(); }
/**
* fungsi untuk menampilkan data linked list
*/
void tampilData() {
int no = 1;
myLinkedList *bantu;
bantu = head;
if (paKosong() == 0) {
while (bantu != NULL) {
cout << “No. : ” <<>nim <<>nama <<>nilai <<>
no++;
bantu = bantu->next;
}
cout <<>
} else {
cout << “Data masih kosong ” <<>
/**
* fungsi Menu, Untuk menentukan linked list mana
* yang dipilih
*/
int menu() {
int pilihan;
cout << “+———————-+\n”; cout << “| MENU PILIHAN |\n”; cout << “+———————-+\n”; cout << “| 1. Tambah Depan |\n”; cout << “| 2. Tambah Belakang |\n”; cout << “| 3. Hapus Depan |\n”; cout << “| 4. Hapus Belakang |\n”; cout << “| 5. Tambah Tengah |\n”; cout << “| 6. Hapus Tengah |\n”; cout << “| 7. TampilData |\n”; cout << “| 8. Keluar |\n”; cout << “+———————-+\n”; cout << “| PILIHAN ANDA ? [ ] |\n”; cout << “+———————-+\n”;
cin >> pilihan;
return pilihan;
}
/**
* fungsi operasi data
*/
void operasiData() {
int pilih;
do {
pilih = menu();
switch (pilih) {
case 1 :
tambahDepan();
break;
case 2 :
tambahBelakang();
break;
case 3 :
hapusDepan();
break;
case 4 :
hapusBelakang();
break;
case 5 :
tampilData();
break;
case 6:
cout << “Terima kasih coy!!!”; break; } } while (pilih != 6); }
/**
* PROGRAM UTAMA
*/
void main() {
init();
operasiData();
}
Setelah diCompile, maka akan menghasilkan tampilan:
3. Pengertian Tree adalah
kesatuan yang membentuk layakya struktur sebuah pohon.
Struktur pohon adalah suatu cara merepresentasikan suatu struktur hirarki
(one-to-many) secara grafis yang mirip sebuah pohon, walaupun pohon
tersebut hanya tampak sebagai kumpulan node-node dari atas ke bawah.
Suatu struktur data yang tidak linier yang menggambarkan hubungan
yang hirarkis (one-to-many) dan tidak linier antara elemen-elemennya.
NODE ROOT
- Node root dalam sebuah tree adalah suatu node yang memiliki hiarki
tertinggi dan dapat juga memiliki node-node anak. Semua node dapat
ditelusuri dari node root tersebut.
- Node root adalah node khusus yang tercipta pertama kalinya.
- Node-node lain di bawah node root saling terhubung satu sama lain dan
disebut subtree
IMPLEMENTASI
Contoh penggunaan struktur pohon :
- Silsilah keluarga
- Hasil pertandingan yang berbentuk turnamen
- Struktur organisasi dari sebuah perusahaan
HANDOUT STRUKTUR DATA
PRODI TEKNIK INFORMATIKA UKDW by Antonius Rachmat C, S.Kom
ISTILAH DALAM TREE
Predecesor Node yang berada diatas node tertentu.
Successor Node yang berada dibawah node tertentu.
Ancestor Seluruh node yang terletak sebelum node tertentu dan
terletak pada jalur yang sama
Descendant Seluruh node yang terletak setelah node tertentu dan
terletak pada jalur yang sama
Parent Predecessor satu level di atas suatu node.
Child Successor satu level di bawah suatu node.
Sibling Node-node yang memiliki parent yang sama
Subtree Suatu node beserta descendantnya.
Size Banyaknya node dalam suatu tree
Height Banyaknya tingkatan dalam suatu tree
Root Node khusus yang tidak memiliki predecessor.
Leaf Node-node dalam tree yang tidak memiliki successor.
Degree Banyaknya child dalam suatu node
GAMBAR TREE
Ancestor (F) = C,A
Descendant (C) = F,G
Parent (D) = B
Child (A) = B,C
Sibling (F) = G
Size = 7
A
B C
D E F G
HANDOUT STRUKTUR DATA
PRODI TEKNIK INFORMATIKA UKDW by Antonius Rachmat C, S.Kom
Height = 3
Root = A
Leaf = D,E,F,G
Degree (C) = 2
JENIS-JENIS TREE
Binary Tree
- Suatu tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal
dua subtree dan kedua subtree tersebut harus terpisah.
- Tiap node dalam binary tree hanya boleh memiliki paling banyak dua
child.
Jenis Binary Tree:
- Full Binary Tree: semua node (kecuali leaf) pasti memiliki 2 anak dan tiap
subtree memiliki panjang path yang sama.
A
B C
D E F G
A
B C
D E F G
H I J
HANDOUT STRUKTUR DATA
PRODI TEKNIK INFORMATIKA UKDW by Antonius Rachmat C, S.Kom
- Complete Binary Tree: mirip dengan full binary tree, tapi tiap subtree boleh
memiliki panjang path yang berbeda dan tiap node (kecuali leaf) memiliki
2 anak.
- Skewed Binary Tree: binary tree yang semua nodenya (kecuali leaf)
hanya memiliki satu anak.
IMPLEMENTASI PROGRAM TREE
- Tree dapat dibuat dengan menggunakan linked list secara rekursif.
- Linked list yang digunakan adalah double linked list.
- Data yang pertama kali masuk akan menjadi node root.
- Data yang lebih kecil dari data node root akan masuk dan menempati
node kiri dari node root, sedangkan jika lebih besar dari data node root,
akan masuk dan menempati node di sebelah kanan node root.
A
B
D
C
E
F
A
B C
D E
HANDOUT STRUKTUR DATA
PRODI TEKNIK INFORMATIKA UKDW by Antonius Rachmat C, S.Kom
Deklarasi struct
typedef struct Tree{
int data;
Tree *left;
Tree *right;
}
Ilustrasi:
Deklarasi variabel:
Tree *pohon;
Operasi-operasi pada Tree:
- Create: membentuk sebuah tree baru yang kosong.
pohon = NULL;
- Clear: menghapus semua elemen tree.
pohon = NULL;
- Empty: mengetahui apakah tree kosong atau tidak
int isEmpty(Tree *pohon){
if(pohon == NULL) return 1; else return 0;
}
- Insert: menambah node ke dalam Tree secara rekursif. Jika data yang
akan dimasukkan lebih besar daripada elemen root, maka akan diletakkan
di node sebelah kanan, sebaliknya jika lebih kecil maka akan diletakkan di
node sebelah kiri. Untuk data pertama akan menjadi elemen root.
Root
Left Right
LeftLeft RightLeft
LeftRight
RightRight
HANDOUT STRUKTUR DATA
PRODI TEKNIK INFORMATIKA UKDW by Antonius Rachmat C, S.Kom
- Find: mencari node di dalam Tree secara rekursif sampai node tersebut
ditemukan dengan menggunakan variable bantuan ketemu. Syaratnya
adalah tree tidak boleh kosong.
- Traverse: yaitu operasi kunjungan terhadap node-node dalam pohon
dimana masing-masing node akan dikunjungi sekali.
Ada tiga cara traverse:
o PreOrder: cetak node yang dikunjungi, kunjungi left, kunjungi right
o InOrder: kunjungi left, cetak node yang dikunjungi, kunjungi right
o PostOrder: kunjungi left, kunjungi right, cetak node yang dikunjungi
Ilustrasi operasi Insert:
1. Insert(root, 65)
2. Insert(left, 5)
3. Insert(right, 70)
4. Insert(left, 3)
65
5 70
65
5
65
HANDOUT STRUKTUR DATA
PRODI TEKNIK INFORMATIKA UKDW by Antonius Rachmat C, S.Kom
5. Insert(right, 10)
Tambah Secara Rekursif
void tambah(Tree **root,int databaru){
if((*root) == NULL){
Tree *baru;
baru = new Tree;
baru->data = databaru;
baru->left = NULL;
baru->right = NULL;
(*root) = baru;
(*root)->left = NULL;
(*root)->right = NULL;
}
else if(databaru < (*root)->data)
tambah(&(*root)->left,databaru);
else if(databaru > (*root)->data)
tambah(&(*root)->right,databaru);
else if(databaru == (*root)->data)
printf("Data sudah ada!");
}
65
5 70
3 10
65
5 70
3
HANDOUT STRUKTUR DATA
PRODI TEKNIK INFORMATIKA UKDW by Antonius Rachmat C, S.Kom
Misal terdapat Tree sebagai berikut:
Ilustrasi Kunjungan
1. Kunjungan PreOrder (notasi prefiks)
Hasil kunjungan: “ABDGCEHIF”
void preOrder(Tree *root){
if(root != NULL){
printf("%d ",root->data);
preOrder(root->left);
preOrder(root->right);
}
}
2. Kunjungan InOrder (notasi infiks)
Hasil kunjungan: “DGBAHEICF”
void inOrder(Tree *root){
if(root != NULL){
inOrder(root->left);
printf("%d ",root->data);
inOrder(root->right);
}
}
3. Kunjungan PostOrder (notasi postfiks)
Hasil kunjungan: “GDBAHIEFCA”
void postOrder(Tree *root){
if(root != NULL){
postOrder(root->left);
postOrder(root->right);
printf("%d ",root->data);
A
B C
D E F
G H I
HANDOUT STRUKTUR DATA
PRODI TEKNIK INFORMATIKA UKDW by Antonius Rachmat C, S.Kom
}
}
4. Kunjungan LevelOrder
Hasil kunjungan: “ABCDEFGHI”
Algoritma:
o Inisialisasi: masukkan root ke dalam Antrian
o Iterasi: selama Antrian tidak kosong, lakukan:
Keluarkan antrian node terdepan, dan kunjungi node tersebut
Masukkan node->right dan node->left ke dalam antrian asal
node tersebut tidak NULL.
Ilustrasi Level Order
- Masukkan A ke Antrian.
- Delelte dari Antrian, yaitu A
- Masukkan B dan C ke Antrian.
- Hapus dari Antrian, yaitu B
- Masukkan D ke Antrian
- Hapus dari Antrian, yaitu C
- Masukkan E ke Antrian.
- Hapus dari Antrian, yaitu D
- Hapus dari Antrian, yaitu E
Notasi Matematika
Misalkan suatu ekspresi berikut: 3 + 2 * 5 – 4
HANDOUT STRUKTUR DATA
PRODI TEKNIK INFORMATIKA UKDW by Antonius Rachmat C, S.Kom
Bagaimana dengan adanya kurung, misalnya: (3 + 2) * 5 – 4?
Pencarian Data di Tree
Tree *cari(Tree *root,int data){
if(root==NULL) return NULL;
else if(data <>data) return (cari(root->left,data));
else if(data > root->data) return (cari(root->right,data));
else if(data == root->data) return root;
}
Pencarian dilakukan secara rekursif, dimulai dari node root, jika data yang dicari
lebih kecil daripada data node root, maka pencarian dilakukan di sub node
sebelah kiri, sedangkan jika data yang dicari lebih besar daripada data node
-
* 4
+ 5
-
+ 4
3 *
2 5
3 2
Prefiks: - * + 3 2 5 4
Infiks: (3 + 2) * 5 – 4
Postfiks: 3 2 + 5 * 4 -
Prefiks: - + 3 * 2 5 4
Infiks: 3 + 2 * 5 - 4
Postfiks: 3 2 5 * + 4 -
HANDOUT STRUKTUR DATA
PRODI TEKNIK INFORMATIKA UKDW by Antonius Rachmat C, S.Kom
root, maka pencarian dilakukan di sub node sebelah kanan, jika data yang dicari
sama dengan data suatu node berarti kembalikan node tersebut dan berarti
data ditemukan.
Ilustrasi:
Misal dicari data 8
1. Root = 6 dan 8 > 6, maka akan dicari di sub node bagian kanan root.
2. Root = 10 dan 8 < root =" 7"> 7, maka akan dicari di sub node bagian kanan root.
4. Root = 8, berarti 8 = 8, maka akan dikembalikan node tersebut dan
dianggap ketemu!
Penghitungan jumlah node dalam tree
int count(Tree *root)
{
if (root == NULL) return 0;
return count(root->left) + count(root->right) + 1;
}
Penghitungan jumlah node dalam tree dilakukan dengan cara mengunjungi
setiap node, dimulai dari root ke subtree kiri, kemudian ke subtree kanan dan
masing-masing node dicatat jumlahnya, dan terakhir jumlah node yang ada di
root
root
root
root 6
3 10
1 5
7
8
9
HANDOUT STRUKTUR DATA
PRODI TEKNIK INFORMATIKA UKDW by Antonius Rachmat C, S.Kom
subtree kiri dijumlahkan dengan jumlah node yang ada di subtree kanan
ditambah 1 yaitu node root.
Penghitungan kedalaman tree
int height(Tree *root)
{
if (root == NULL) return -1;
int u = height(root->left), v = height(root->right);
if (u > v) return u+1;
else return v+1;
}
Penghitungan kedalaman dihitung dari setelah root, yang dimulai dari subtree
bagian kiri kemudian ke subtree bagian kanan. Untuk masing-masing
kedalaman kiri dan kanan akan dibandingkan, jika ternyata subtree kiri lebih
dalam, maka yang dipakai adalah jumlah kedalaman subtree kiri, demikian
sebaliknya. Hal ini didasarkan pada prinsip binary tree, dimana tree-nya selalu
memiliki maksimal 2 node anak.
Fungsi-fungsi lainnya
Tree *FindMin(Tree *root)
{
if(root == NULL)
return NULL;
else
if(root->left == NULL)
return root;
else
return FindMin(root->left);
}
Tree *FindMax(Tree *root)
{
if(root == NULL)
return NULL;
else
if(root->right == NULL)
return root;
else
return FindMax(root->right);
}
HANDOUT STRUKTUR DATA
PRODI TEKNIK INFORMATIKA UKDW by Antonius Rachmat C, S.Kom
Tree *Delete(int d,Tree **root){
Tree *tmp;
if(*root == NULL )
printf("kosong!");
else
if(d < (*root)->data )
/* Go left */
(*root)->left = Delete(d,&(*root)->left);
else
if(d > (*root)->data ) /* Go right */
(*root)->right = Delete(d,&(*root)->right );
else /* Found element to be deleted */
if((*root)->left && (*root)->right ) /* Two children */
{
/* Replace with smallest in right subtree */
tmp = FindMin((*root)->right);
(*root)->data = tmp->data;
(*root)->right = Delete((*root)->data, &(*root)-
>right);
}
else /* One or zero children */
{
tmp = (*root);
if( (*root)->left == NULL ) /* Also handles 0 children
*/
(*root) = (*root)->right;
else if( (*root)->right == NULL ){
(*root) = (*root)->left;
delete tmp;
}
}
return tmp;
}
void leaf(Tree *root){
if(root == NULL) printf("kosong!");
if(root->left!=NULL) leaf(root->left);
if(root->right!=NULL) leaf(root->right);
if(root->right == NULL && root->left == NULL) printf("%d ",root-
>data);
}
void child(Tree *root,int data){
Tree *t = cari(root,data);
if(root->left != NULL) printf("%d ",root->left->data);
if(root->right != NULL) printf("%d ",root->right->data);
}
4. Pengertian Pointer adalah
Pointer (variabel penunjuk) adalah suatu variabel yang berisi alamat memori dari suatu
variabel lain. Alamat ini merupakan lokasi dari obyek lain (biasanya variabel lain) di dalam
memori. Contoh, jika sebuah variabel berisi alamat dari variabel lain, variabel pertama
dikatakan menunjuk ke variabel kedua
�� Operator Pointer ada dua, yaitu :
♦ Operator &
�� Operator & bersifat unary (hanya memerlukan satu operand saja).
�� Operator & menghasilkan alamat dari operandnya.
♦ Operator *
�� Operator * bersifat unary (hanya memerlukan satu operand saja).
�� Operator * menghasilkan nilai yang berada pada sebuah alamat.
2 DEKLARASI POINTER
Seperti halnya variabel yang lain, variabel pointer juga harus dideklarasikan terlebih dahulu
sebelum digunakan. Bentuk Umum :
Tipe_data *nama_pointer;
Tipe data pointer mendefinisikan tipe dari obyek yang ditunjuk oleh pointer. Secara teknis, tipe
apapun dari pointer dapat menunjukkan lokasi (dimanapun) dalam memori. Bahkan operasi
pointer dapat dilaksanakan relatif terhadap tipe dasar apapun yang ditunjuk. Contoh, ketika kita
mendeklarasikan pointer dengan tipe int*, kompiler akan menganggap alamat yang ditunjuk
menyimpan nilai integer - walaupun sebenarnya bukan (sebuah pointer int* selalu menganggap
bahwa ia menunjuk ke sebuah obyek bertipe integer, tidak peduli isi sebenarnya). Karenanya,
sebelum mendeklarasikan sebuah pointer, pastikan tipenya sesuai dengan tipe obyek yang akan
ditunjuk.
