4-Introduction to Tree, Binary Tree, and Expression Tree

1. Konsep Tree
  • Node yang ada di paling atas pada Tree disebutroot
  • Garis yang menghubungkan Parent ke Child pada tree disebutEdge
  • Node yang tidak memiliki anak disebut Leaf
  • Dua node yang memiliki Parent yang sama disebut Sibling
  • Degree dari node adalah jumlah cabang dari satu node
  • Height/ Depth adalah cabang maksimum dari satu node pada Tree
  • Ancestor adalah semua node parent yang ada di atas node tersebut
  • Descendant adalah semua node child yang ada di bawah node tersebut


Binary Tree adalah data structure bercabang yang masing-masing nodenya memiliki dua anak, yaitu anak kiri dan anak kanan

2. Jenis jenis Binary Tree
  • Perfect binary tree adalah binary tree yang semua tingkatnya memiliki kesamaan kedalaman, bisa juga disebut complete binary tree atau balanced binary tree
  • Complete binary tree adalah binary tree yang semua tingkat memiliki anggota kecuali tingkat paling akhir
  • Skewed binary tree adalah binary tree yang setiap node memiliki satu anak
  • Balanced binary tee adalah binary tree yang jumlah node child kiri sama dengan jumlah node child kanan
Perfect Binary Tree

Complete Binary Tree

Skewed Binary Tree

Balanced Binary Tree

3. Binary Tree dalam Array

4. Binary Tree dalam Linked List
struct Data{
   int number;
   Data*parent, *left, *right;
}Data*root = NULL;


5. Konsep Expression Tree

Prefix = *+ab/cde
Postfix = ab+cd-e/*
Infix = (a+b)*((c-d)/e)

code dari binary tree:

struct Data{
   char a;
   Data *left, *right;
};

6. Infix, Prefix, Postfix dalam Binary Tree

kita dapat membuat expression tree dari prefix atau postfix menggunakan rekursif

pada prefix, data harus dicetak sebelum node child dari data tersebut dicetak

pada postfix, data harus dicetak sesudah node child dari data tersebut dicetak

Comments

Post a Comment

Popular posts from this blog

1-Array & Linked List

1. Array Array adalah sekumpulan data yang tipe datanya sama, yang disimpan dalam bentuk indeks, dimulai dari angka nol dan indeks terakhir adalah null. contoh: int array[4]; array[0] = 2; array[1] = 0; array[2] = 1; array[3] = 8; jadi arraynya seperti berikut: [0] [1] [2] [3] [4]  2  0  1  8 /0 2. Dimensi Array Array berdimensi dua menggunakan dua array, biasanya digunakan untuk array of char (kalimat atau kata yang lebih dari satu karakter/ huruf). contoh: char array[9][9]; array [0] = "Allan"; array [1] = "Bill"; array [2] = "Chuck"; array [3] = "Dean"; array [4] = "Ellie"; array [5] = "Frans"; array [6] = "Godin"; array [7] = "Hill"; array [8] = "Irvin"; Jadi arraynya seperti berikut: [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] Allan Bill Chuck Dean Ellie Frans Godin Hill Irvin \0 Untuk array [0], dimensi keduanya adalah sebagai berikut: [0][0] [0][...
Read more

2-Linked List Implementation

Image
1. Jenis - Jenis Linked List     -Single Linked List       Linked List yang setiap nodenya hanya memiliki satu pointer, yaitu *next.     -Polynomial Representation      Setiap istilah individual di dalam polinomial terdiri dari dua bagian, yaitu koefisien dan pangkat, setiap istilah dapat diwakili sebagai node dari Linked List     -Circular Single Linked List       Linked List yang tidak memiliki ujung atau seperti sirkuit, yang berarti tail akan kembali menunjuk  head.     -Double Linked List       Linked List yang setiap nodenya memiliki dua pointer, yaitu*prev dan *next.     -Circular Double Linked List       Sama halnya dengan "Circular Single Linked List", yang membedakannya adalah setiap node memiliki dua pointer sehingga tail dapat menunjuk head dan begitu juga sebaliknya.     -Header Linked List      Linked List ya...
Read more

5-Binary Search Tree

Image
1. Binary Tree dan Binary Search Tree Binary tree adalah tree yang memiliki maksimal child, sebanyak dua untuk setiap nodenya, sedangkan binary search tree adalah binary tree yang child kirinya selalu lebih kecil daripada node tersebut, dan child kanan selalu lebih besar daripada node tersebut. Note: Binary search tree memiliki bentuk yang sama seperti binary tree biasa 2. Kegunaan Binary Search Tree Kegunaan binary search tree adalah untuk mempermudah proses pencarian data 3. Operasi dalam Binary Search Tree Proses pencarian data dalam binary search tree adalah sebagai berikut: misalnya kita ingin mencari nilai X, 1. pencarian dimulai dari root 2. jika root berisi X, berarti pencarian selesai 3. jika X lebih kecil dari pada nilai root, cari ke subtree kiri secara rekursif, sebaliknya jika X lebih besar dari pada nilai root, cari ke subtree kanan secara rekursif 4. Code Pencarian pada Binary Search Tree 5. Penambahan Data Pada Binary Search Tree Penambahan data pa...
Read more