Pertemuan 4-Introduction of Binary Tree-2101648785- Christian N

Tree merupakan kumpulan satu node atau lebih

Degree of tree:5
Degree of E: 3
Height: 5
Parent of G: C
Children of E: J &K
Anchestor of D: B, A
Descendant of M: N&O

- Pohon biner merupakan struktur data pohon berakar di mana setiap node memiliki paling banyak dua anak

- Dua anak biasanya membedakan anak paling kiri dan kanan

 Contoh binary tree diatas memiliki 8 node
 Root pada node mempunyai angka 60
 Leaves adalah 15, 44, 66


Tipe pohon biner

  Perfect Binary Tree

  Complete Binary Tree


 

  











  Implementasi linked list

  struct node{
       int data;
        struct node *left;
        struct node *right;
       struct node *parent;
  }*root;


  

    Prefix: *+ab/-cde
 
    Infix: (a+b)*((c-d)/e)


    Postfix: ab+cd-e/*

Pertemuan 3- Linked List - 2101648785 - Christian Nugroho

Elemen data yang dihubungkan dengan link pada Linked List disebut Node. Biasanya didalam suatu linked list, terdapat istilah head dan tail. 

- Head adalah elemen yang berada pada posisi pertama dalam suatu linked list
- Tail adalah elemen yang berada pada posisi terakhir dalam suatu linked list

Ada beberapa macam Linked List, yaitu :

1. Single Linked List
2. Double Linked List

Single Linked List

Single Linked List merupakan suatu linked list yang hanya memiliki satu variabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya. Biasanya field pada tail menunjuk ke NULL.

 

 

 

 

contoh codingannya :

struct Mahasiswa{
      char nama[25];
      int usia;
      struct Mahasiswa *next;
}*head,*tail;

 

 

 Single Linked list: inserted

 

 

   struct Mahasiswa *node = 

  (struct Mahasiswa*) malloc(sizeof(struct Mahasiswa));

   node->value = x;

  node->next  = head;

  head = node;

 

 

Operator -> has the same meaning as:

(*node).value = x;

(*node).next  = head;

 

 
Single Linked list: deleted

 

struct tnode *curr = head;

•

// if x is in head node

if ( head->value == x ) {

  head = head->next;

  free(curr);
}

// if x is in tail node

else if(tail->value == x){

  while(curr->next!=tail) curr = curr->next;

  free(tail); tail = curr;

  tail->next = NULL;

}

// if x is not in head node, find the location

else {

  while ( curr->next->value != x ) curr = curr->next;

  struct tnode *del = curr->next;

  curr->next = del->next;

  free(del);

}

 

 

 

 

 

Double Linked List

Double Linked List merupakan suatu linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke NULL.

 

 contoh codingannya :

  struct Mahasiwa{
     char nama[25];
     int usia;
     struct Mahasiswa *next,*prev; }*head,*tail;

 

 

 Double linked list: inserted

struct tnode *node =

  (struct tnode*) malloc(sizeof(struct tnode));

node->value = x;

node->next  = NULL;

node->prev  = tail;

tail->next  = node;

tail = node;

 

 

 

 Single Linked list: deleted

 

Jika node dihapus pada head

•  head = head->next;
•  free(head->prev);
•  head->prev = NULL;

 

Jika node dihapus pada tail

 

•tail = tail->prev;

•  free(tail->next);

•  tail->next = NULL;

 

 

 

Memory Allocation

Dalam C/C++, alokasi memory dapat dilakukan dengan menggunakan malloc , sedangkan untuk dealokasi dapat menggunakan free. Fungsi free hanya membebaskan memory tetapi tidak menghapus isi dari memory tersebut. 

contoh penggunaan malloc:

int *px = (int *) malloc(sizeof(int));
char *pc = (char *) malloc(sizeof(char));
struct Facebook *curr = (struct Facebook*) malloc(sizeof(struct Facebook));


contoh penggunaan free:

free(curr);

Alokasi suatu memory biasanya dibutuhkan didalam linked list saat akan menambah node/data baru.

 

 

 

Pertemuan 5- Binary Tree -2101648785- Christian N

- Tree merupakan salah satu bentuk struktur data yang tidak linear yang menggambarkan   
   hubungan bersifat hirarkis
- Prodecessor : node yang berada diatas node tertentu.
- Successor : node yang berada di bawah node tertentu.
- Root merupakan salah satu node paling atas
- Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang
                    sama.

- Descendant: seluruh node yang terletak sesudah node tertentu dan terletak pada jalur
                          yang sama
- Parent: prodecessor satu level diatas node
- Child : successor satu level di bawah suatu node.
- Sibling : node-node yang memiliki parent yang sama dengan suatu node.
- Height : banyaknya tingkatan/level dalam suatu tree.
- Leaf : node-node dalam tree yang tak memiliki seccessor.
- 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

  Berbagai macam operasi binary tree, diantaranya:

  - Create: membentuk binary tree baru yang masih kosong.
  - Insert: Memasukkan sebuah node ke dalam tree. Ada tiga pilihan insert: sebagai root,
                left child, atau right child. Khusus insert sebagai root, tree harus dalam keadaan
                 kosong.
  - Clear: Mengosongkan binary tree yang sudah ada.
  - Find: Mencari root, parent, left child, atau right child dari suatu node. (Tree tak boleh
               kosong)
  - DeleteSub: menghapus sebuah substree


 Langkah-Langkahnya Traverse :

• PreOrder : Cetak isi node yang dikunjungi, kunjungi Left Child, kunjungi Right Child.
• InOrder : Kunjungi Left Child, Cetak isi node yang dikunjungi, kunjungi Right Child.
• PostOrder : Kunjungi Left Child, Kunjungi Right Child, cetak isi node yang dikunjungi
  
  
  Berikut skema pohon biner
  Contoh : diketahui sekumpulan elemen sebagai berikut :
  
  60, 75, 25, 50, 15, 66, 33, 44
  
  Hasil akhir:
  
   
  Khusus binary tree
  
  Maksimum angka pada node binary tree adalah 2h+1-1
  
  
  
  
  Maksimum height pada node binary tree adalah 3
  1 + 2 + 4 + 8 = 15
  
  
  
  Macam-macam pohon biner: 
• PERFECT binary tree adalah pohon biner di mana setiap level berada pada kedalaman yang sama.
• COMPLETE binary tree adalah pohon biner di mana setiap tingkat, kecuali mungkin yang terakhir, benar-benar terisi, dan semua node berada paling kiri mungkin.
   
• SKEWED binary tree merupakan pohon biner di mana setiap simpul memiliki paling banyak satu anak.
  
  
  
  

Pertemuan 2 - Introduction to linked list - 2101648785 - ChristianN

Linked List

     Linked list disebut dengan sebutan senarai berantai adalah struktur data yang terdiri 

  dari urutan record dimana setiap record memiliki field yang menyimpan alamat dari record

  selanjutnya.

  Bedanya linked list dengan array:

   Linked list:  - memiliki kumpulan node linear

                      - tidak menyimpan node dilokasi memori berturut-turut

                      

   Array :  - memiliki kumpulan elemen data linear

               - dapat random mengakses data

               - pengaksesan searching dan sorting cepat



  Macam-macam sub topik linked list

  1. Structure Declaration

       Mendeklarasi dengan struktur menggunakan keyword struct diikuti dengan nama   
          struktur atau sering disebut tag. Variabel-variabel dideklarasikan dalam kurung
          kurawal { }.

   2. Structure Assignment

      Contoh:

          struct data{

               int i;

               char a[length_data];

          }a,b;

          Use the operator:

          a.i = 42;

          strcpy(a.s,"Christian");

          b.i = 100;

          b=a;

   3. Nested structure

       Nested structure merupakan suatu struktur digunakan didalam structure lainnya

          Contoh:

        struct profile{

                char nama[100];

                int age;

            };

            struct student{

                 struct profile s;

                 int score;

           char grade;

            };

        student x;

            x.score = 82;

        x.grade = 'B';

            strcpy(x.s.nama,"christ");

            x.s.age = 22;

            END

  4. Alokasi memori: dinamik

       Fungsi-fungsi alokasi memori:

           - sizeof(): mendapat ukuran, tipe data, struktur

           - malloc(): memesan memori saat runtime

           Contoh:

          int *px = 205;

               char *pc = 'A';

                

               printf("%d %c\n",*px,*pc);

           

                

               return 0;

Pertemuan 1 - Pointer, Array and introducion to Data structure-2101648785-ChristianN

Data Structure

   Struct adalah tipe data yang digunakan untuk penyimpanan beberapa data saling terkait,

   juga terdiri dari beberapa anggota, anggota dari struct, dan variabel biasa.

   Materi ini mempelajari tentang konsep dasar data struktur yang biasanya digunakan
   dalam software engineering dan praktek pemrograman, array, structure, stack, 

   graph,tree.

     Array

       Array merupakan suatu kumpulan data-data dimana data tersebut memiliki tipe data

      yang sama. Setiap elemen array ini memiliki kesamaan tipe data yang homogen.

      Index array biasanya dimulai dari angka nol.

      Ada beberapa jenis array digunakan pada program:

      1. Array satu dimensi

           merupakan array yang berisi satu dimensi saja. Tempat penyimpanan sekumpulan
          data memiliki tipe data sama dan hanya satu index saja.

          Contoh:

      

        int data[6];

        Banyak variabel mengakses sebanyak 6 elemen

            data[0] = 15;

            data[1] = 40;

            data[2] = 32;

            data[3] = 27;

            data[4] = 77;

            data[5] = 61;

        Syntax:

         type_name[size];

     2. Array dua dimensi

             merupakan array yang berisi dua dimensi. array tersebut tersusun dalam 

             bentuk baris dan kolom.

             Contoh:

         int data[4][9];

         Banyak variabel mengakses sebanyak 4 elemen

              data[0][4] = 7;

              data[1][3] = 14;

              data[2][8] = 9;

              data[3][6] = 10;

         Syntax:

              type_name[size1][size2];

      Contoh melakukan storing nilai array

      int array[6]= {97,76,82,65,83};

int i;

for(i=0;i<5;i++)

{

printf("%d ",array[i]);

}

     Pointer

    Pointer merupakan tipe data yang nilai mengacu dimana memori komputer 

      menggunakan alamat yang ada.

      Tipe dua operator paling penting menggunakan pointer:

       - & adalah address operator

       - * adalah pointer operator

    Contoh:

     int a = 10;

        int *p = &a;

           

        printf("%d\n",*p);

       a = 17;

       *p = 20;

       printf("%d\n",a);

    Type of Data Structure

     Contoh data struktur utama terdiri dari:

       1. Arrays

            elemen-elemen data memiliki tipe data sama

  

       2. Linked lists

               Struktur data dinamis yang sekumpulan elemen yang dapat ditambahkan 

               atau di-delete.