Pengertian kedalaman (depth) atau ketinggian (height)
pada tree.
Tree bisa didefinisikan sebagai suatu kumpulan elemen yang salah satu elemennya disebut dengan akar (root), dan sisa elemen lainnya (yang disebut simpul)
terpecah menjadi sejumlah himpunan yang paling tidak berhubungan satu sama
lain, yang disebut dengan subpohon (subtree),
atau disebut juga cabang. Jika kita melihat pada subpohon, maka subpohon
inipun juga mempunyai akar dan sub-subpohonnya masing-masing.
Dalam
kehidupan sehari-hari, tree dapat
dilihat dari pohon silsilah keluarga. Tingkat yang tertinggi disebut juga
sebagai root. Untuk lebih jelasnya
lihat gambar di
bawah ini merupakan contoh dari sebuah tree.
Di dalam
sebuah tree dikenal istilah Tingkat atau level. Tingkat (level) suatu simpul
ditentukan dengan pertama kali menentukan akar sebagai bertingkat 0. jika suatu
simpul dinyatakan sebagai tingkat N, maka simpul-simpul yang merupakan anaknya
dikatakan berada dalam tingkat N+1. pada pohon dibawah merupakan tree dengan 4 level.
Tinggi (Height) atau Kedalaman (Depth)
dari suatu pohon adalah tingkat(level) maksimum
dari suatu pohon dikurangi dengan satu. Dengan demikian pohon diatas mempunyai
tinggi atau kedalaman sama dengan 4.
Pohon Biner
(Binary Tree)
Pohon
biner bisa didefinisikan sebagai suatu kumpulan simpul yang mungkin kosong atau
mempunyai akar dan dua subpohon yang saling terpisah yang disebut dengan
subpohon kiri dan sub pohon kanan. Subpohon disebut juga sebagai cabang.
Karakteristik dari pohon biner ialah bahwa setiap simpul paling banyak hanya
mempunyai dua buah anak. Dengan kata lain derajat tertinggi dari sebuah pohon
biner adalah dua.
Pengertian daun, root,
level, tinggi dan derajad yang berlaku pada pohon juga berlaku pada binary
tree. Penyajian binary tree pada komputer di gunakan double link list.
Deklarasi mencari
kedalaman atau ketinggian dari suatu 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;
}
Algoritma pada penghitungan kedalaman dimulai dari menghitung
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.
contoh codingnya :
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
struct tree_node //deklarasi variabel
{ //menggunakan double linked list
int data;
tree_node* left;
tree_node* right;
};
tree_node* root;
bool isEmpty()
{return root==NULL;}
void insert(int d) //untuk memasukkan data
{
tree_node* t = new tree_node;
tree_node* parent;
t->data = d; //data masukan
t->left = NULL;//cabang kiri
t->right = NULL;//cabang kanan
parent = NULL;
if(isEmpty())root = t; //jika belum ada data yg dimasukkan
else //jika sudah ada data yang masuk
{
tree_node* curr;
curr = root;
while(curr!=NULL)
{
parent = curr;
if(t->data == curr->data) { printf("DATA ALREADY EXIST !"); break; }
else if(t->data > curr->data) {curr = curr->right;}
else if(t->data < curr->data) {curr = curr->left;}
}
//meletakkan posisi anak
if(t->data < parent->data) parent->left = t;
else if(t->data > parent->data) parent->right = t;
else if(t->data == parent->data) parent->left = parent->right = NULL;
}
}
void inorder(tree_node* p) //menampilkan data dengan kunjungan secara inorder
{
if(p!=NULL)
{
if(p->left) inorder(p->left);
cout<<" "<<p->data<<" ";
if(p->right)inorder(p->right);
}
else return;
}
void print_inorder() //menampilkan inorder
{
inorder(root);
}
void print(struct tree_node* p, int x, int y, int j)
{
if(p == NULL) return;
gotoxy(x,y);
printf("%d", p->data);
print(p -> left, x-j, y+2, j/2);
print(p -> right, x+j, y+2, j/2);
getch();
}
int height(tree_node* p) //fungsi height untuk menghitung kedalaman tree
{
if(p==NULL)return -1;
else {
int l = height(p->left) ;
int r = height(p->right);
if (l > r) {return l+1;}
else {return r+1;}
}
getch();
}
void print_height() //menampilkan kedalaman dari tree
{
height(root);
}
int main()
{
root=NULL;
int a,data;
while(1)
{
clrscr();
cout<<endl;
cout<<"\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n";
cout<<"===============================================================================\n";
cout<<"\t\t\t\tPROGRAMMER BY :\n";
printf("\t\t"); textcolor(17); cprintf("1. Ulva S. Nurmayani"); textcolor(7);
printf("\t\t"); textcolor(26); cprintf("081012015"); textcolor(7);
printf("\n\t\t"); textcolor(37); cprintf("2. Etik Ulfianita"); textcolor(7);
printf("\t\t"); textcolor(27); cprintf("081012016"); textcolor(7);
printf("\n\t\t"); textcolor(13); cprintf("3. Madya Vica A."); textcolor(7);
printf("\t\t"); textcolor(14); cprintf("081012025"); textcolor(7);
printf("\n\t\t"); textcolor(495); cprintf("4. Candra Arga M."); textcolor(7);
printf("\t\t"); textcolor(396); cprintf("081012063"); textcolor(7);
printf("\n\t\t"); textcolor(395); cprintf("5. Nuri Fashichah"); textcolor(7);
printf("\t\t"); textcolor(300); cprintf("081012066"); textcolor(7);
cout<<"\n===============================================================================\n\n\n";
cout<<"\n\t\t\a1----INSERT A NODE IN A BINARY TREE.";
cout<<"\n\t\t\a2----IN-ORDER TRAVERSAL.";
cout<<"\n\t\t\a3----HEIGHT OF TREE.";
cout<<"\n\t\t\a4----EXIT.";
cout<<"\n\n\t\t\aENTER CHOICE::";
cin>>a;
print(root, 40, 2, 20);
cout<<endl;
switch(a)
{
case 1 : gotoxy(37,39);
printf("\n\tENTER THE ELEMENT : ");
scanf("%d",&data);
insert(data);
print(root, 40, 2, 20);
break;
case 2 : gotoxy(37,39);
cout<<endl;
cout<<"\n\t****IN-ORDER TRAVERSAL OF A TREE****"<<endl;
cout<<"\t------------------------------------"<<endl;
print_inorder();
getch();
break;
case 3 : gotoxy(37,39);
cout<<"\n\tHEIGHT OF A TREE"<<endl;
cout<<"\t-----------------"<<endl;
cout<<height(root);
getch();
break;
case 4 : cout<<"\n\n\n\t\t\tTHANKS";
return 0;
break;
default: gotoxy(37,39);
cout<<"INVALID INPUT"<<endl;
getch();
break;
}
}
}
