Cây n phân

/*
   Cai dat Cay n phan
   Cac giai thuat tiem kiem BFS, DFS ....
   Writer: Nguyen Minh Lap
   MSSV: 070165T
   Ton Duc Thang University
   Date: 02/05/2010
   
   Chu y: doc file bao cao de biet cach nhap cay n phan
   Chua lam duoc: do cach duyet cay n phan khong xy ly duoc truong hop trung gia tri.

*/

#include <stdio.h>
#include <stdlib.h>
#include "iomanip.h"
#include "iostream.h"
#define M 100
typedef int elem;
#include "queue.cpp"
#include "stack.cpp"

#define TRUE 1
#define FALSE 0
#define MAX 10
struct node
{
   int data;//  gia tri node
   int dosau;
   int sonode;// so node con
   struct node *subnode[MAX];// con tro den cac node con
};
typedef struct node *Tree;

// khai bao ham
int themnut();
void duyetcay(Tree T1);
void xoacay(Tree T1);
void nhapnutgoc();
void nhapcay();
void duyetqueue();
void duyetstack();
void creategraph(Tree &T);
void incay(Tree t,int m=1);
void splitqueue(queue q, int x1); // loai bo x1 ra khoi queue
void splitstack(stack St, int x1); // loai bo x1 ra khoi stack
Tree T;
int sonode =0;

queue q;
stack St;

int empty(Tree T);
Tree search(Tree T1,int k);
void BFS(Tree t);
void DFS(Tree t);
void gandosau(Tree T1, int m=0);
void DFSchieusauhanche(Tree t) ;
int DFSchieusauhanche_p(Tree t, int chieusau, int giatri);
void DFSsaudan(Tree t);
void HCS(Tree t);
void sapxep(int mang[], int n);
void BestFS(Tree t);

//------------------- *****ham main*****  ----------------------------
void main()
{
   cout<<"--------Chuong trinh minh hoa cac giai thuat tim kiem------------\n";
   int choice =0 ;
   creategraph(T);
   cout<<"\n        ***  do thi  ***\n";
   incay(T);
   cout<<endl;
   do
   {
      cout<<"\n\n  Chuong Trinh      "
         <<"\n  1. Breadth First Search "
         <<"\n  2. Depth First Search "
         <<"\n  3. Depth First Search chieu sau han che "
         <<"\n  4. Depth First Search  sau dan"
         <<"\n  5. Hill Climbing Search"
         <<"\n  6. Best First Search"
         <<"\n  7. Xem do thi "
         <<"\n  0. Thoat "
         <<"\n  Chon : ";
      cin>>choice;
      switch(choice)
      {
      case 1 :
         BFS(T);
         break;
      case 2:
         DFS(T);
         break;
      case 3:
         DFSchieusauhanche(T);
         break;
      case 4:
         DFSsaudan(T);
         break;
      case 5:
         HCS(T);
         break;
      case 6:
         BestFS(T);
         break;
      case 7:
         cout<<"\n        ***  do thi  ***\n";
         incay(T);
         break;
      case 0:
         break;   
      }
   }while(choice !=0 );
   
}
//--------------------------------------------------------------------
int empty(Tree T)
{
  return(T == NULL ? TRUE : FALSE);
}
Tree search(Tree T1,int k)// tra ve node chua gia tri k
{
   int i;   
   Tree t1;
   if(!empty(T1))
   {
      if(T1->data == k)
      {
         return (T1);
      
      }
      else
      {
         for(i=0;i<T1->sonode;i++)
         {
            t1 = search(T1->subnode[i],k);
               if(t1)
                  return t1;         
         }
      }
   }
   return NULL;
}

void BFS(Tree t)
{
   int giatri;
   cout<<"-------- ***  Breadth First Search *** ---------";
   cout<<"\nNhap gia tri can tim : ";
   cin>>giatri;   
   int i,x;
   createqueue(q);   
   cout<<"\nVi tri hien tai ------ danh sach open";
   Tree t1 = t;
   x = t->data;
   addqueue(q,x);      
   while(!emptyqueue(q))
   {      
      removequeue(q,x);
      if(x ==  giatri)
      {
         cout<<"\n  "<<setw(6)<<x;
         cout<<"\nda tim thay muc tieu\n";          
         break;
      }
      cout<<"\n  "<<setw(6)<<x;   
      t = search(t1,x);
      // add cac con cua t vao queue   
      for(i = 0 ; i< t->sonode ; i++)
         addqueue(q,t->subnode[i]->data);   // chuyen cac con con lai vao open         
      cout<<"        |    ";
      duyetqueue();         
   }      
}

void DFS(Tree t)
{   
   createstack(St);
   cout<<"---------- ***  Depth First Search *** -----------";
   int giatri;
   cout<<"\nNhap gia tri can tim : ";
   cin>>giatri;

   int i,x;
   cout<<"\nvi tri hien tai ------ danh sach open";
   Tree t1 = t;// backup      
   x = t->data;
   push(St,x);

   while(!emptystack(St))
   {      
      pop(St,x);
      if(x ==  giatri)
      {
         cout<<"\n  "<<setw(6)<<x;
         cout<<"\nda tim thay muc tieu\n";          
         break;
      }
      cout<<"\n  "<<setw(6)<<x;
      
      t = search(t1,x);
      
      // add cac con cua t vao queue   
      for(i = 0 ; i< t->sonode ; i++)
      {      
         push(St,t->subnode[i]->data);   // chuyen cac con con lai vao open            
      }            
      
      cout<<"        |    ";
      duyetstack();         
   }   
   
}
void gandosau(Tree T1, int m)
{
   if(T1!=NULL)
   {   
      T1->dosau = m;
      for (int i =0; i< T1->sonode ; i++)
         gandosau(T1->subnode[i],m+1);
   }

}
void DFSchieusauhanche(Tree t)  /// xem lai chua chay dung
{   
   int chieusau, d=0 ;
   createstack(St);
   cout<<"---------- ***  Depth First Search chieu sau han che *** -----------";
   int giatri;
   cout<<"\nNhap gia tri can tim : ";
   cin>>giatri;   
   cout<<"\nNhap do sau : ";
   cin>>chieusau;

   int i,x;
   cout<<"\nvi tri hien tai ------ danh sach open";
   Tree t1 = t;
   gandosau(t);// gan do sau cho cay

   push(St,t->data);   
   while(!emptystack(St))
   {      
      pop(St,x);
      if(x ==  giatri)
      {
         cout<<"\n  "<<setw(6)<<x;
         cout<<"\nda tim thay muc tieu\n";          
         break;
      }
      cout<<"\n  "<<setw(6)<<x;
      t = search(t1,x);
      if(t->dosau < chieusau )
      {
         // add cac con cua t vao queue   
         for(i = 0 ; i< t->sonode ; i++)
            push(St,t->subnode[i]->data);   // chuyen cac con con lai vao open                        
      }      
      cout<<"        |    ";
      duyetstack();         
   }      
}
int DFSchieusauhanche_p(Tree t, int chieusau, int giatri)
{   
   int kq = 0 ;
   createstack(St);
   int i,x;
   cout<<"\nvi tri hien tai ------ danh sach open";
   Tree t1 = t;
   gandosau(t);// gan do sau cho cay

   push(St,t->data);   
   while(!emptystack(St))
   {      
      pop(St,x);
      if(x ==  giatri)
      {
         cout<<"\n  "<<setw(6)<<x;               
         kq=1;
      }
      cout<<"\n  "<<setw(6)<<x;
      t = search(t1,x);
      if(t->dosau < chieusau )
      {
         // add cac con cua t vao queue   
         for(i = 0 ; i< t->sonode ; i++)
         {         
            push(St,t->subnode[i]->data);   // chuyen cac con con lai vao open         
         }         
      }      
      cout<<"        |    ";
      duyetstack();         
   }
   return kq;
}

void DFSsaudan(Tree t)
{   
   int chieusau,d = 1 ;
   createstack(St);
   cout<<"---------- ***  Depth First Search sau dan *** -----------";
   int giatri;
   cout<<"\nNhap gia tri can tim : ";
   cin>>giatri;   
   for(chieusau =0; chieusau <(sonode/2); chieusau ++ )
   {
      cout<<"\nChieu sau :"<<chieusau<<endl;
      if(DFSchieusauhanche_p(t,chieusau,giatri))
      {
         cout<<"tim thay ";
         break;
      }
      
   }
}
void HCS(Tree t)
{
   createstack(St);
   cout<<"---------- ***  Hill Climbing Search *** -----------";
   int giatri;
   cout<<"\nNhap gia tri can tim : ";
   cin>>giatri;

   int i,x;
   cout<<"\nvi tri hien tai ------ danh sach open";
   Tree t1 = t;// backup      
   x = t->data;
   push(St,x);
   int max;
   while(!emptystack(St))
   {      
      pop(St,x);
      if(x ==  giatri)
      {
         cout<<"\n  "<<setw(6)<<x;
         cout<<"\nda tim thay muc tieu\n";          
         break;
      }
      cout<<"\n  "<<setw(6)<<x;
      
      t = search(t1,x);
      
      if(t->sonode >0 )
      {
         max = t->subnode[0]->data;
         for(i = 1 ; i< t->sonode ; i++)
         {      
            if(t->subnode[i]->data > max)
               max = t->subnode[i]->data;
         }
         if(max >x)
            push(St,max);   // trang thai tiep theo phai lon hon trang thai truoc
      }
      
      cout<<"        |    ";
      duyetstack();         
   }
}
void sapxep(int mang[], int n)
{
   int i,j,k;
   for(i=0;i<n;i++)
   {   
      for(j=i+1;j<n;j++)       
         if(mang[j] < mang[i])
         {
            k=mang[i];
            mang[i]=mang[j];
            mang[j]=k;
         }      
   }
}
void BestFS(Tree t)
{
   createstack(St);
   cout<<"---------- ***  Best First Search *** -----------";
   int giatri;
   cout<<"\nNhap gia tri can tim : ";
   cin>>giatri;

   int i,x;
   cout<<"\nvi tri hien tai ------ danh sach open";
   Tree t1 = t;// backup      
   x = t->data;
   push(St,x);

   while(!emptystack(St))
   {      
      pop(St,x);
      if(x ==  giatri)
      {
         cout<<"\n  "<<setw(6)<<x;
         cout<<"\nda tim thay muc tieu\n";          
         break;
      }
      cout<<"\n  "<<setw(6)<<x;
      
      t = search(t1,x);      
      
      if(t->sonode >0 )
      {
         int a[100];
         for(i = 0 ; i< t->sonode ; i++)
         {      
            a[i] = t->subnode[i]->data;
         }   
         sapxep(a,t->sonode);// sap xep
         for(i = 0 ; i< t->sonode ; i++)
         {      
            push(St, a[i]);
         }         
      }      
      cout<<"        |    ";
      duyetstack();         
   }
}
void incay(Tree t,int m)
{   
   if(t!=NULL)
   {   
      cout<<endl<<setw(5*m)<<t->data;
      for (int i =0; i< t->sonode ; i++)
         incay(t->subnode[i],m+1);
   }
}
int themnut()
{
   int a,c;
    Tree s,T2,b,d;
    T2 = T;
    b = new node;// cap phat
   d = new node;// cap phat
    cout<<"\nnhap gia tri nut can them : ";
   cin>>a;
    d = search(T2,a);
   if(!empty(d))
   {
      cout<<"\nDa ton tai, ko them dc";
      return 0;
   }
   else
   {
      cout<<"\nnhap khoa cua nut cha :";
      cin>>c;
       T2=T;
      b=search(T2,c);
      if(empty(b))
      {
         cout<<"\nkhong tim thay nut cha";
         return 0;
      }
      else
      {
         s =new node;
           s->data=a;
           s->sonode=0;
           for(int i=0 ; i<MAX ; i++)
            s->subnode[i]=NULL;
          b->sonode++;
           b->subnode[b->sonode-1] = s;  // gan node moi vao
         return 1;
      }
   }
}

void duyetcay(Tree T1)
{
   cout<<"ket qua do thi ";
   int i;
   if(T1!= NULL)
   {
      cout<<setw(3)<<T1->data;
      for(i=0 ; i<T1->sonode ; i++)
         duyetcay(T1->subnode[i]);         
   }
}
void xoacay(Tree T1)
{
   int i;
   for(i=0;i<T1->sonode;i++)
   {
       xoacay(T1->subnode[i]);
       free(T1);
   }
}

void creategraph(Tree &T)
{
     int a,b;
    cout<<"\nnhap gia tri nut goc : ";
    cin>>a;
    sonode ++;// dem so node
    if(a>0)
    {
       cout<<"nhap so node con : ";
       cin>>b;
        T = new node;
       T->data  = a;
       T->dosau =0;
       T->sonode = b;      
       for(int i=0 ; i < b ; i++)
       {
         cout<<"nhap chi tiet cho node con#";
         creategraph(T-> subnode[i]);
       }         
    }
    else
       T = NULL;
      
} 
void nhapnutgoc()
{
     int a;   
      cout<<"\nnhap gia tri nut goc : ";
    cin>>a;
     T=new node;
    T->data  = a;
    T->sonode = 0;
    for(int i=0 ; i<MAX ; i++)
      T->subnode[i] = NULL;
}

void nhapcay()
{
   nhapnutgoc();
   int n;
   cout<<"nhap so node cua do thi: ";
   cin>>n;
   for(int i=0; i<n ; i++)
      themnut();
}
void duyetqueue()
{
   queue q1;
   createqueue(q1);
   int x;
   while(!emptyqueue(q))
   {
      removequeue(q,x);
      cout<<setw(5)<<x;
      addqueue(q1,x);
   }
   while(!emptyqueue(q1))
   {
      removequeue(q1,x);
      addqueue(q,x);
   }
}
void duyetstack()
{
   stack s1;
   createstack (s1);
   int x;
   while(!emptystack(St))
   {
      pop(St,x);
      cout<<setw(5)<<x;
      push(s1,x);
   }
   while(!emptystack(s1))
   {
      pop(s1,x);
      push(St,x);
   }
}
void splitqueue(queue q, int x1)
{
   queue q1;
   createqueue(q1);
   int x;
   while(!emptyqueue(q))
   {
      removequeue(q,x);   
      addqueue(q1,x);
   }
   while(!emptyqueue(q1))
   {
      removequeue(q1,x);
      if(x != x1)
         addqueue(q,x);
   }
}
void splitstack(stack St, int x1)
{
   stack s1;
   createstack (s1);
   int x;
   while(!emptystack(St))
   {
      pop(St,x);      
      push(s1,x);
   }
   while(!emptystack(s1))
   {
      pop(s1,x);
      if(x != x1)
         push(St,x);
   }
}

//---------------------------------------queue ne------------------------------------------
#include"stdlib.h"
#include"string.h"
typedef struct {
   elem e[M];
   int front,rear;
}queue;
void createqueue(queue &q)
{
   q.front=q.rear=0;
}
int emptyqueue(queue &q)
{
   return q.front==q.rear;
}
void addqueue(queue &q,int &x)
{
   int nr=(q.rear+1)%M;
   if(nr==q.front) exit(0);
   memcpy(&q.e[q.rear],&x,sizeof(elem));
   q.rear=nr;
}
void removequeue(queue &q,int &x)
{
   if(q.front==q.rear) exit(0);
   memcpy(&x,&q.e[q.front],sizeof(elem));
   q.front=(q.front+1)%M;
}



//-----------------------stack ne------------------------
#include"string.h"
#include"stdlib.h"
typedef struct {
   elem e[M];
   int top;
}stack;
void createstack(stack &s)
{
   s.top=-1;
}
int emptystack(stack &s)
{
   return s.top==-1;
}
void push(stack &s,elem &x)
{
   if(s.top==M-1) exit (0);
   memcpy(&s.e[++s.top],&x,sizeof(elem));
}
void pop(stack &s,elem &x)
{
   if(s.top==-1) exit (0);
   memcpy(&x,&s.e[s.top--],sizeof(elem));
}