BINARY TREE

"PROGRAM SILSILAH KELUARGA MENGGUNAKAN BINARY TREE"

#define WINDOWS
//#define LINUX

/** FAMILY TREE */

#include<iostream>
#include<string.h>
#include<stdlib.h>

using namespace std;

struct node
{
    char name[50];
    short int age,x;    // x - height of node
    bool g;             // g- gender
    node* fc;           // Pointer to first child
    node* ns;           // Pointer to next sibiling

    node();
    void getData();
};

node::node()
{
    fc=ns=NULL;
    g=0;
    strcpy(name,"");
    age=x=0;
}

void node::getData()
{
    char ch;
    cout<<"\nName of the Person: ";
    cin>>name;
    cout<<"Age of "<<name<<": ";
    cin>>age;
    cout<<name<<" is (m/f): ";
    cin>>ch;
    if(ch=='m')
        g=1;
}

class familyTree
{

public:

    node* start;

    familyTree();

    node* traverseDown(node*,char[]);   // Search functions
    node* traverseRight(node*,char[]);
    node* search(char[]);

    void addSib(node*,node*);           // Functions for adding new members
    void addChild(node*,node*);
    void addNew();

    void find();                        // Function to find relations
    void show(node*);                   // Function to show details of particular person
    void display(node*);                // Function to display full tree
    void destroy(node*);                // Function to destroy full tree
    void updateX(node*,int);

};

familyTree::familyTree()
{
    start = NULL;
}

void familyTree::destroy(node* ptr)
{
    node* temp = ptr;

    if(ptr==NULL)
        return;

    while(ptr!=NULL)
    {
        destroy(ptr->fc);
        temp = ptr;
        ptr = ptr->ns;
        delete temp;
    }

    start = NULL;
}

void familyTree::show(node* ptr)
{
    char g[10];
    strcpy(g,"Female");
    if(ptr->g)
        strcpy(g,"Male");
    cout<<"\n\nName: "<< ptr->name <<endl;
    cout<<"Age: "<< ptr->age <<endl;
    cout<<"Gender: "<<g<<endl;
}

void familyTree::display(node* ptr)
{
    // Traverses the full n-array tree by recursion to display names of all people

    if(ptr==NULL)
        return;

    while(ptr!=NULL)
    {
        cout<< ptr->name <<endl;
        display(ptr->fc);
        ptr = ptr->ns;
    }
}

void familyTree::updateX(node* ptr,int x)
{
    // Traverses the full n-array tree by recursion and updates x value of all people

    if(ptr==NULL)
        return;

    while(ptr!=NULL)
    {
        updateX(ptr->fc,x++);
        if(ptr->ns!=NULL)
            ptr->ns->x = x;
        ptr = ptr->ns;
    }
}

void familyTree::find()
{

    /*
        Same hight: Sibiling if same parent, else cousin
        Difference of height = 1 - Parent if immediate, else uncule/aunt
        Difference oh height = 2 - Grand parents if same link, elss idk
    */

    char name1[50],name2[50];
    cout<<"Enter names of two persons:\n";
    cin>>name1>>name2;
    node* ptr1 = search(name1);
    node* ptr2 = search(name2);
    node* ptr;
    node* ptrk=ptr1;
    node* ptrk1=ptr2;

    switch(ptr1->x - ptr2->x)
    {

    case 0:
            char s[50];
            strcpy(s,"sister");
            if(ptr1->g)
                strcpy(s,"brother");

            ptr = ptr1;
            while(ptr!=NULL)
            {
                if(ptr==ptr2)
                {
                    cout<<endl<<name1<<" is "<<name2<<"'s "<<s<<endl;
                    return;
                }
                ptr = ptr->ns;
            }
            ptr = ptr2;
            while(ptr!=NULL)
            {
                if(ptr==ptr1)
                {
                    cout<<endl<<name1<<" is "<<name2<<"'s "<<s<<endl;
                    return;
                }
                ptr = ptr->ns;
            }
            cout<<endl<<name1<<" and "<<name2<<" are Cousins";
            break;

    case 1:
            char str3[50];
            strcpy(str3,"daughter");
            if(ptr1->g)
                strcpy(str3,"son");
            ptr2 = ptr2->fc;
            while(ptr2!=NULL)
            {
                if(ptr2==ptr1)
                {
                    cout<<endl<<name1<<" is "<<name2<<"'s "<<str3;
                    return;
                }
                ptr2=ptr2->ns;
            }
            strcpy(str3,"niece");
            if(ptr1->g)
                strcpy(str3,"nephew");
            cout<<endl<<name1<<" is "<<name2<<"'s "<<str3;
            break;
    case -1:
            char str[10];
            strcpy(str,"mother");
            if(ptrk->g)
                strcpy(str,"father");

            ptr = ptrk->fc;
            while(ptr!=NULL)
            {
                if(ptr==ptrk1)
                {
                    cout<<endl<<name1<<" is "<<name2<<"'s "<<str;
                    return;
                }
                ptr=ptr->ns;
            }
            strcpy(str,"aunt");
            if(ptrk->g)
                strcpy(str,"uncule");
            cout<<endl<<name1<<" is "<<name2<<"'s "<<str;
            break;

    case 2:
            char str1[50];
            strcpy(str1,"daughter");
            if(ptr2->g)
                strcpy(str1,"son");
            ptr2 = ptr2->fc->fc;
            while(ptr2!=NULL)
            {
                if(ptr2==ptr1)
                {
                    cout<<endl<<name1<<" is grand "<<str1<<" of "<<name2;
                    return;
                }
                ptr2 = ptr2->ns;
            }
            break;
    case -2:
            char str2[50];
            strcpy(str2,"mother");

            if(ptr1->g)
                strcpy(str2,"father");

             ptr1 = ptr1->fc->fc;

            while(ptr1!=NULL)
            {
                if(ptr1==ptr2)
                {
                    cout<<endl<<name1<<" is grand "<<str2<<" of "<<name2;
                    return;
                }
                ptr1 = ptr1->ns;
            }

            break;
    default:
            cout<<"Too far relationship";
            break;
    }
}



node* familyTree::search(char s[50])
{
    /*
        Searches for the given name from start to it's sibilings and their children
        Returns the pointer of node where the name is present
    */

    node *ptr = start;

    if(strcmp(ptr->name,s)==0)
        return ptr;
    else if(traverseRight(start,s)!=NULL)
        return traverseRight(start,s);
    else if(traverseDown(start,s)!=NULL)
        return traverseDown(start,s);
    else
    {
        return NULL;
        cout<<"***Not found***8";
    }
}

node* familyTree::traverseDown(node* ptr, char s[50])
{
    // Searches all the children

    ptr = ptr->fc;

    while(ptr!=NULL)
    {
        if(  strcmp(ptr->name,s)==0 )
            return ptr;
        else if(traverseRight(ptr,s)!=NULL)
            return traverseRight(ptr,s);
        else
            ptr = ptr->fc;
    }
    return NULL;
}

node* familyTree::traverseRight(node* ptr, char s[50])
{

    //  Searches all the sibilings

    ptr = ptr->ns;

    while(ptr!=NULL)
    {
        if(strcmp(ptr->name,s)==0)
            return ptr;
        else if (traverseDown(ptr,s)!=NULL)
            return traverseDown(ptr,s);
        else
            ptr = ptr->ns;
    }
    return NULL;
}

void familyTree::addNew()
{
    node* temp = new node;
    temp->getData();

    if(start == NULL)
    {
        start = temp;
        temp->x=0;
    }

    else
    {
        cout<<"\nEnter any relation's name: ";
        char name[50];
        cin>>name;
        cout<<"\n1. Child\n2. Sibiling\n\n"<< temp->name <<" is ____ to "<<name<<" : ";
        int opt;
        cin>>opt;
        switch(opt)
        {
            case 1:
                    addChild(search(name),temp);
                    break;
            case 2:
                    addSib(search(name),temp);
                    break;

        }
    }
    cout<<"\nPerson sucessfully added.\n";
}

void familyTree::addSib(node* a,node* b)
{
    // b is added as sibling of a

    while(a->ns!=NULL)
        a=a->ns;
    a->ns = b;

    b->x = a->x;
}

void familyTree::addChild(node* a,node* b)
{

    // b is added as child as a (or) b is added as sibiling to last child of a

    if(a->fc==NULL)
        a->fc = b;
    else
        addSib(a->fc,b);

    b->x = a->x+1;
}

void connect(familyTree *T1, familyTree *T2)
{
    char name[50];
    int opt;
    int x;
    cout<<"Name of person in 1st tree to merge: ";
    cin>>name;
    cout<<T2->start->name<<" is __ to "<<name<<"\n1. Child 2. Sibling - ";;
    cin>>opt;
    node *ptr = T1->search(name);
    switch(opt)
    {
        case 1:
            T1->addChild(ptr,T2->start);
            x = ptr->x + 1;
            break;
        case 2:
            T1->addSib(ptr,T2->start);
            x = ptr->x;
            break;
     }
     T2->updateX(T2->start,x);
     T2->destroy(T2->start);
     cout<<"\nMerged\n";
}

int main()
{
    familyTree T[100];
    int opt,n,n1,n2;
    char c,name[50];
    cout<<"\nEnter the family tree number = ";
    cin>>n;
    while(1)
    {
#ifdef WINDOWS
        system("cls");
#endif // WINDOWS
#ifdef LINUX
        system("clear");
#endif // LINUX
        cout<<"\n\n\n\tFamily tree no = "<<n<<"\n\n\t1. Add new person\n\t2. Find relationship b/w two persons\n\t3. Search\n\t4. Destroy\n\t5. Display\n\t6. Change family tree\n\t7. Connect two family trees\n\t8. Exit\n\n\tEnter your choice = ";
        cin>>opt;
        cout<<endl;

        switch(opt)
        {

        default:
                cout<<"Invalid input";
                break;

        case 1:
                T[n].addNew();
                break;

        case 2:
                T[n].find();
                break;

        case 3:
                cout<<"Enter name of person to search: ";
                cin>>name;
                T[n].show(T[n].search(name));
                break;

        case 4:
                T[n].destroy(T[n].start);
                cout<<"Tree "<<n<<" has been destroyed sucessfully";
                break;

        case 5:
                T[n].display(T[n].start);
                break;

        case 6:
                cout<<"Enter family tree number: ";
                cin>>n;
                break;

        case 7:
               cout<<"Merge __ to __ \n";
               cin>>n2>>n1;
               connect(&T[n1],&T[n2]);
               break;

        case 8:
            return 0;

        }
        cout<<"\n\nPress any key to continue.....";
        cin>>c;
    }
}


jika dijalankan kurang lebih seperti ini outputnya yaa....

referensi saya:

Modul praktikum struktur data Pendidikan teknik informatika Universitas Muhammadiyah Surakarta

antrian "QUEUE"

ANTRIAN "QUEUE"

ANTRIAN (QUEUE)

Program struktur data jenis antrian (queue) yang terdapat operasi didalamnya (enqueue,dequeue,print,clear)


#include <stdio.h>
#include <conio.h>
#include <iostream>
#define MAX 6
using namespace std;
struct Queue
{
  int data[MAX];
  int head;
  int tail;
};

Queue antrian;
void Create()
{
  antrian.head=antrian.tail=-1;
}

int IsEmpty()
{
  if(antrian.tail==-1)
    return 1;
  else
    return 0;
}
int IsFull()
{
  if(antrian.tail==MAX-1)
    return 1;
  else
    return 0;
}

void Enqueue(int data)
{
  if(IsEmpty()==1)
  {
     antrian.head=antrian.tail=0;
     antrian.data[antrian.tail]=data;
     cout<<antrian.data[antrian.tail];
  }
  else
   //kodisi lainnya jika penuh() sama dengan 0 maka antrian.ekor ditambah 1
  {
     antrian.tail++;
     antrian.data[antrian.tail]=data;
     cout<<antrian.data[antrian.tail];
  }
}

int Dequeue()
{
  int i;
  int e=antrian.data[antrian.head];
  for(i=antrian.head;i<=antrian.tail-1;i++)
  {
    antrian.data[i]=antrian.data[i+1];
  }
  antrian.tail--;
  return e;
}

void Clear()
{
  antrian.head=antrian.tail=-1;
  cout<<"Data Clear";
}

void Tampil()
{
  if (IsEmpty()==0)
    for (int i=antrian.head;i<=antrian.tail; i++)
      cout<<antrian.data[i]<<"  ";
  else
    cout<<"Data Kosong\n";
}

int main()
{
  int pil;
  int data;
  Create();
  do
  {
    cout<<endl;
    cout<<"\n============MENU PILIHAN============\n";
    cout<<"1. Enqueue\n";
    cout<<"2. Dequeue\n";
    cout<<"3. Tampil\n";
    cout<<"4. Clear\n";
    cout<<"5. Keluar\n";
    cout<<"************************************\n";
    cout<<"Masukkan Pilihan Anda =  ";
    cin>>pil;
    switch(pil)
    {
    case 1:
      cout<<"Data : ";cin>>data;
      Enqueue(data);
      break;
     case 2:
      if (IsEmpty()==0)
        cout<<"Elemen yang keluar : "<<Dequeue();
      else
      cout<<"Data kosong"<<endl;
      break;
    case 3:
      Tampil();
      break;
    case 4:
      Clear();
      break;
    case 5:
      break;
    }
    getch();
} while(pil!=5);

}


jika dijalankan kurang lebih seperti ini outputnya yaa....

referensi saya:

Modul praktikum struktur data Pendidikan teknik informatika Universitas Muhammadiyah Surakarta