PENGERTIAN TREE, BINARY TREE BESERTA JENIS DAN CONTOHNYA PADA C++

Pengertian Tree

Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hierarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan elemen khusus yang disebut Root. Node lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubungan satu sama lain (disebut Subtree). Untuk lebih jelasnya, di bawah akan diuraikan istilahistilah umum dalam tree.

Predecessor
Node yang berada di atas 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 sebelum 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 dengan suatu node
Subtree
Bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
Size
Banyaknya node dalam suatu tree
Height
Banyaknya tingkatan / level dalam suatu tree
Root
Satu-satunya node khusus dalam tree yang tak punyak predecessor
Leaf
Node-node dalam tree yang tak memiliki successor
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. Sesuai dengan definisi tersebut tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.

Jenis- Jenis Binary Tree :
Full Binary Tree

Jenis binary tree ini tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree
harus mempunyai panjang path yang sama.

Complete Binary Tree

Jenis ini mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda dan setiap node kecuali leaf hanya boleh memiliki 2 child.

Skewed Binary Tree

Skewed Binary Tree adalah Binary Tree yang semua nodenya (kecuali leaf) hanya
memiliki satu child.

Implementasi Binary Tree

Binary tree dapat diimplementasikan dalam C++ dengan menggunakan double
linkedlist.

Operasi-operasi pada Binary Tree

Create
Membentuk binary tree baru yang masih kosong
Clear
Mengosongkan binary tree yang sudah ada
Empty
Function untuk memeriksa apakah binary tree 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
Find
Mencari root, parent, left child, atau right child dari suatu node. (tree tidak boleh kosong).
Update
Mengubah isi dari node yang ditunjuk oleh pointer curret
(Tree tidak boleh kosong)
Retrieve
Mengetahui isi dari node yang ditunjuk oleh pointer current
(Tree tidak boleh kosong)
DeleteSub
Menghapus sebuah subtree (node beserta seluruh descendantnya)
yang ditunjuk current. Tree tidak boleh kosong. Setelah
itu, pointer current dakan berpindah ke parent dari node yang dihapus.
Characteristic
Mengetahui karakteristik dari suatu tree, yakni: size, height, serta average length. Tree tidak boleh kosong.
Traverse
Mengunjungi seluruh node-node pada tree, masing-masing sekali. Hasilnya adalah urutan informasi secara linear yang
tersimpan dalam tree. Ada tiga cara traverse,yaitu PreOrder, InOrder, dan PostOrder.

Langkah-langkah Tranverse :

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.

Binary Search Tree

Binary Tree ini memiliki sifat dimana semua left child harus lebih kecil dari pada right child dan parentnya. Semua right child juga harus lebih besar dari left child serta parentnya. Binary search tree dibuat untuk mengatasi kelemahan pada binary tree biasa, yaitu kesulitan dalam searching / pendarian node tertentu dalam binary tree.
Pada dasarnya operasi dalam Binary Search Tree sama dengan Binary Tree biasa, kecuali pada operasi insert, update, dan delete.

Insert
Pada Binary Search Tree insert dilakukan setelah lokasi yang tepat ditemukan (lokasi
tidak ditentukan oleh user sendiri ).
Update
Update ini seperti yang ada pada Binary Tree biasa, namun di sini update akan
berpengaruh pada posisi node tersebut selanjutnya. Bila update mengakibatkan tree tersebut bukan Binary Search Tree lagi, harus dilakukan perubahan pada tree dengan melakukan rotasi supaya tetap menjadi Binary Search Tree.
Delete
Seperti halnya update, delete dalam Binary Search Tree juga turut mempengaruhi
struktur dari tree tersebut.

Skenario

1. Implementasi Binary Search Tree

Kita akan mengimplementasikan Binary Search Tree dengan menggunakan pemrograman C++. Bukalah IDE C++ yang ada dikomputer anda atau notepad. Kemudian salinlah kode berikut ini.

#include <iostream>
using namespace std;

class BinarySearchTree{
private:
struct tree_node{
tree_node* left;
tree_node* right;
int data;
};

tree_node* root;

public: BinarySearchTree(){
root = NULL;
}

bool isEmpty() const { return root==NULL; }

void print_preorder();

void preorder(tree_node*);

void insert(int);

};

// Smaller elements go left

// larger elements go right

void BinarySearchTree::insert(int d){
tree_node* t = new tree_node;
tree_node* parent;
t->data = d;
t->left = NULL;
t->right = NULL;
parent = NULL;

// is this a new tree?
if(isEmpty())
root = t;
else{
//Note: ALL insertions are as leaf nodes tree_node* curr;
curr = root;
// Find the Node's parent while(curr){
parent = curr;
if(t->data > curr->data)
curr = curr->right;
else
curr = curr->left;
}

if(t->data < parent->data)
parent->left = t;
else
parent->right = t;
}
}

void BinarySearchTree::print_preorder(){
preorder(root);
}

void BinarySearchTree::preorder(tree_node* p){
if(p != NULL){
cout<<" "<<p->data<<" ";
if(p->left) preorder(p->left);
if(p->right) preorder(p->right);
}
else return;
}

int main(){
BinarySearchTree b;
int ch,tmp;
while(1){
cout<<endl<<endl;
cout<<" Binary Search Tree Operations "<<endl;
cout<<" ----------------------------- "<<endl;
cout<<" 1. Insertion/Creation "<<endl;
cout<<" 2. Pre-Order Traversal "<<endl;
cout<<" 3. Exit "<<endl;
cout<<" Enter your choice : ";
cin>>ch;

switch(ch){
case 1 : cout<<" Enter Number to be inserted : ";
cin>>tmp;
b.insert(tmp);
break;
case 2 : cout<<endl;
cout<<" Pre-Order Traversal "<<endl; cout<<" -------------------"<<endl; b.print_preorder();
break;
case 3 :
return 0;
}
}
}

Selanjutnya compile dan jalankan kode diatas dan amati hasilnya!

PENGERTIAN TREE, BINARY TREE BESERTA JENIS DAN CONTOHNYA PADA C++