Binary Tree : Mencari kedalaman suatu binary tree

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;
                }
        }
}