Struktur data Non Linear

Pohon  atau tree adalah salah satu bentuk konsep struktur data yang terdiri dari akar dan simpul-simpul yang berada dibawah akar.

 

Gambar : Tingkat Pohon Tree

• Selain istilah tingkat juga ada yang disebut dengan derajat ( degree ).
• Derajat merupakan banyak tingkat simpul turunan dari satu simpul tertentu, misalkan simpul tertentu, misalkan simpul “ Ketua Umum” memiliki derajat 3, simpul “ wakil Ketua I “ memiliki derajat 2 dan seterusnya.
• Simpul yang memiliki derajat 0 disebut dengan daun (  leaf ), pada struktur data pohon dikenal istilah yang disebut  kedalaman  ( depth ).
• Sedangkan sebuah simpul yang ada diatas sebuah simpul lain disebut sebagai ancestor.
• Kumpulan pohon disebut dengan hutan ( forest ).

Ada beberapa cara untuk menggambarkan sebuah pohon yaitu :

Operasi pada pohon biner :
Operasi yang dapat dilakukan pada pohon biner antara lain kunjungan terhadap simpul - simpulnya.

Jenis-jenis kunjungan pada pohon biner antara lain :

• Preorder
• Inorder
• Postorder
• Level order

Pre Order : ==> Kunjungan preorder merupakan kunjungan pada pohon biner yang dimulai dari akar

                          kemudian ke subpohon kiri, setelah subpohon  kiri  dikunjungi  baru  subpohon  kanan

                          dikunjungi.

gambar

Maka dengan kunjungan preorder  akan  menghasilkan  urutan  simpul  yang dikunjungi
A – B – D – E – C – F – G – H

In Order : ==> Kunjungan inorder merupakan kunjungan pada pohon biner yang dimulai dari simpul-simpul
                        turunan subpohon kiri, akar, baru kemudian simpul-simpul turunan pada subpohon kanan.

gambar

Maka  kunjungan  inoeder  akan  menghasilkan urutan simpul : 

D – B – E – A – F – C – H – G

Post Order : ==> Kunjungan post order merupakan kunjungan pada pohon biner yang dimulai dari simpul-

                           simpul turunan subpohon kiri, baru kemudian simpul-simpul turunan pada subpohon kanan, 

                           kemudian akar, misalkan terdapat sebuah pohon biner seperti pada gambar .

 gambar

Post Order akan menghasilkan urutan simpul yang dikunjungi :

D – E – B – F – H – G – C – A

Level  Order : ==> Kunjungan level order merupakan kunjungan pada pohon biner yang dimulai dari simpul 

                              pada tingkat  1  kemudian  simpul-simpul pada tingkat 2  dan seterusnya., dimulai dari

                              simpul  paling kiri ke kanan.

Kunjungan level order akan menghasilkan urutan simpul
A - B - C – D – E – F – G – H

 

 

 

 

Binary Tree

 

#include <iostream>

#include <cstdlib>
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_inorder();
        void inorder(tree_node*);
        void print_preorder();
        void preorder(tree_node*);
        void print_postorder();
        void postorder(tree_node*);
        void insert(int);
        void remove(int);
};

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;

  if(isEmpty()) root = t;
  else
  {

    tree_node* curr;
    curr = root;

    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::remove(int d)
{

    bool found = false;
    if(isEmpty())
    {
        cout<<" This Tree is empty! "<<endl;
        return;
    }
    tree_node* curr;
    tree_node* parent;
    curr = root;
    while(curr != NULL)
    {
         if(curr->data == d)
         {
            found = true;
            break;
         }
         else
         {
             parent = curr;
             if(d>curr->data) curr = curr->right;
             else curr = curr->left;
         }
    }
    if(!found)
         {
        cout<<" Data not found! "<<endl;
        return;
    }


    if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL
&& curr->right == NULL))
    {
       if(curr->left == NULL && curr->right != NULL)
       {
           if(parent->left == curr)
           {
             parent->left = curr->right;
             delete curr;
           }
           else
           {
             parent->right = curr->right;
             delete curr;
           }
       }
       else
       {
          if(parent->left == curr)
           {
             parent->left = curr->left;
             delete curr;
           }
           else
           {
             parent->right = curr->left;
             delete curr;
           }
       }
     return;
    }


         if( curr->left == NULL && curr->right == NULL)
    {
        if(parent->left == curr) parent->left = NULL;
        else parent->right = NULL;
                  delete curr;
                  return;
    }


    if (curr->left != NULL && curr->right != NULL)
    {
        tree_node* chkr;
        chkr = curr->right;
        if((chkr->left == NULL) && (chkr->right == NULL))
        {
            curr = chkr;
            delete chkr;
            curr->right = NULL;
        }
        else
        {

            if((curr->right)->left != NULL)
            {
                tree_node* lcurr;
                tree_node* lcurrp;
                lcurrp = curr->right;
                lcurr = (curr->right)->left;
                while(lcurr->left != NULL)
                {
                   lcurrp = lcurr;
                   lcurr = lcurr->left;
                }
                                    curr->data = lcurr->data;
                delete lcurr;
                lcurrp->left = NULL;
           }
           else
           {
               tree_node* tmp;
               tmp = curr->right;
               curr->data = tmp->data;
                              curr->right = tmp->right;
               delete tmp;
           }

        }
         return;
    }

}

void BinarySearchTree::print_inorder()
{
  inorder(root);
}

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

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

void BinarySearchTree::print_postorder()
{
  postorder(root);
}

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

int main()
{
    BinarySearchTree b;
    int n,ch,tmp,tmp1;
    cout<<"\tOperasi Pohon Biner Lukman Reza \n\n";
    cout<<"Masukkan banyak data: ";
           cin>>n;
                    for (int i=0; i<=n; i++){
                    cout<<"Angka :";cin>>i;
                    b.insert(i);}
                 
                    cout<<"\n\nIn-Order Traversal "<<endl;
                    cout<<"-------------------"<<endl;
                    b.print_inorder();
                 
                    cout<<"\n\nPre-Order Traversal "<<endl;
                    cout<<"-------------------"<<endl;
                    b.print_preorder();
               
                    cout<<"\n\nPost-Order Traversal "<<endl;
                    cout<<"--------------------"<<endl;
                    b.print_postorder();
                    cout<<endl;
                 
           system("pause");
                    return 0;
                 
 
}

 

 

Graph

 

Ini Merupakan Program C++, yang dibuat untuk mengetahui sebuah graph terhubung atau tidak!
Berikut Source Codenya:

#include <iostream.h>
#include <conio.h>

int main(){
bool ketemu,nolsemua;
int matrix[10] [10];
int i,j,jumlah_simpul,jumlah_sisi,asal,tujuan;
//isnisialisasi matrix
cout<<"jumlah simpul:";
cin>>jumlah_simpul;
cout<<"jumlah_sisi:";
cin>>jumlah_sisi;
for (i=1;i<=jumlah_simpul;i++)
for (j=1;j<=jumlah_simpul;j++)
matrix[i][j]=0;
//isi matrix sesuai input graf
for (i=1;i<=jumlah_sisi;i++){
cout<<"simpul asal:";
cin>>asal;
cout<<"simpul tujuan:";
cin>>tujuan;
matrix[asal][tujuan]=1;
matrix[tujuan][asal]=1;
}
//telusuri graf
i=1;nolsemua=false;
while (i<=jumlah_simpul && !nolsemua){
j=1;ketemu=false;
while (j<=jumlah_simpul && !ketemu){
if (matrix[i][j]==1)
ketemu=true;
else
j++;
}
if (!ketemu)
nolsemua=true;
else
i++;
}

if(nolsemua)
cout<<"graf tidak terhubung";
else
cout<<"graf terhubung";
getch();

}