May 21, 2009

搞死人的資料結構作業七:BST(Add / Del)

終於可以好好睡覺了......

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

#define BSTSIZE 100
#define add 0
#define del 1
#define largest 2
#define smallest 3
#define gLimit (BSTSIZE -1)

typedef struct BSTNode
{
 int Data, LSize;
 struct BSTNode *LChild, *RChild;
}BSTNode;

typedef  BSTNode *BSTPointer;

BSTPointer RootEntry;
BSTPointer BSTArray[BSTSIZE];

int gSP = 0;
BSTPointer Stack[BSTSIZE];

BSTPointer FP;
BSTPointer P;

int Result;
int idx = 0;

int AddDelLSize(BSTPointer Temp, int cmd);
void IncDec(BSTPointer Temp, int cmd);
void PUSH(BSTPointer node);
BSTPointer POP(void);

int PrintByPreOrder(void);
void AddKVintoBSTArray(int KV);
int DelKV(int KV);
void SearchKV(BSTPointer Header, int KV);
void SearchTheLargestOfLeftandTheSmallestofRight(BSTPointer Pointer, int cmd);

void main(void)
{
 int count = 0;
 int NodeData;
 int Keyin;
 char iFunc;

 RootEntry = (BSTPointer)malloc(sizeof(BSTNode));
 RootEntry->Data = 0;
 RootEntry->LSize = 0;
 RootEntry->LChild = NULL;
 RootEntry->RChild = NULL;
  
 for(int i=0; i < BSTSIZE ; i++)
 {
  BSTArray[i] = (BSTPointer)malloc(sizeof(BSTNode));
  BSTArray[i]->Data = 0;
  BSTArray[i]->LSize = 0;
  BSTArray[i]->LChild = NULL;
  BSTArray[i]->RChild = NULL;
 }
 
 RootEntry->LChild = BSTArray[0];

 cout << "Binary Search Tree and Print By Preorder Method.\n";
 cout << "================================================\n";
 
 do
 {
  cout << "(a)dd data into BST    (d)elete data from BST    (e)xit : ";
  cin >> iFunc;

  if(iFunc == 'a')
  {
   cout << "Input a new data into BST:";
   cin >> Keyin;
   AddKVintoBSTArray(Keyin);
  }

  if(iFunc == 'd')
  {
   cout << "Input a data you want to delete:";
   cin >> Keyin;
   DelKV(Keyin);
  }

  cout << "<BST> = ";
  PrintByPreOrder();
  cout << endl;
 }while(iFunc != 'e');

}

 

void PUSH(BSTPointer node)
{
 Result = 0;
 Stack[gSP] = node;
 gSP++;

 if(gSP > gLimit)
 {
  Result = -1;
 }
}

BSTPointer POP(void)
{

 BSTPointer node;
 gSP--;

 if(gSP < 0)
 {
  Result = -1;
  return NULL;
 }

 node = Stack[gSP];
 return node;
}

void AddKVintoBSTArray(int KV)
{
 BSTPointer Father;
 BSTPointer Header;
 Header = RootEntry->LChild;
 idx++;
 BSTArray[idx]->Data = KV;

 if(Header->LChild == NULL && Header->RChild == NULL && Header->LSize == 0)
 {
  BSTArray[idx]->LSize = 1;
  Header->LChild = BSTArray[idx];
 } else {

  Father = Header->LChild;

  while(1)
  {
   if(KV > Father->Data)
   {
    BSTArray[idx]->LSize = Father->LSize+1;

    if(Father->RChild == NULL)
    {
     Father->RChild = BSTArray[idx];
     break;
    } else {
     Father = Father->RChild;
    } // End of if(Father->RChild == NULL)
   } else {
    BSTArray[idx]->LSize = Father->LSize;
    Father->LSize = Father->LSize + 1;

    if(Father->RChild != NULL)
     AddDelLSize(Father->RChild, add);
    
    if(Father->LChild == NULL)
    {
     Father->LChild = BSTArray[idx];
     break;
    } else {
     Father = Father->LChild;
    } // End of if(Father->LChild == NULL)
   } // End of if(KV > Father->Data)
  } // End of while(1)
 } // End of if(Header->LChild == NULL && Header->RChild == NULL && Header->LSize == 0)
}

int AddDelLSize(BSTPointer Temp, int cmd)
{
 while(1)
 {
  if(Temp->LChild == NULL)
  {
   if(Temp->RChild == NULL)
   {
    IncDec(Temp, cmd);
    
    do
    {
     if(gSP == 0)
      return 0;

     Temp = POP();
     if(Temp == NULL)
     {
      cout << "Stack is empty!!!\n";
      return 0;
     }
     IncDec(Temp, cmd);

     Temp = Temp->RChild;
    }while(Temp == NULL);

   } else {
    IncDec(Temp, cmd);
    Temp = Temp->RChild;
   } // End of if(Temp->RChild == NULL)
  } else {
   PUSH(Temp);
   if(Result == -1)
   {
    cout << "Stack is full!!!\n";
    return 0;
   } else {
    Temp = Temp->LChild;
   } // End of if(Result == -1)
  } // End of if(Temp->RChild == NULL)
 } // End of while(1)
}

void IncDec(BSTPointer Temp, int cmd)
{
 if(cmd == add)
  Temp->LSize = Temp->LSize +1;
 if(cmd == del)
  Temp->LSize = Temp->LSize -1;
}

void SearchKV(int KV)
{
 FP = RootEntry->LChild;
 P = FP->LChild;
 Result = -1;

 if(FP->LChild == NULL && FP->RChild && FP->LSize ==0)
 {
  FP = NULL;
  P = NULL;
 } else {

  while(1)
  {
   if(P->Data > KV)
   {
    FP = P;
    P = P->LChild;
   } else {
    if(P->Data < KV)
    {
     FP = P;
     P = P->RChild;
    } else {
     Result = 0;
     break;
    } // End of if(P->Data < KV)
   } // End of if(P->Data > KV)
   if(P == NULL)
    break;
  } // End of while(1)
 } // End of if(FP->LChild == NULL && FP->RChild && FP->LSize ==0)
}

void SearchTheLargestOfLeftandTheSmallestofRight(BSTPointer Pointer, int cmd)
{
 FP = Pointer;

 if(cmd == largest)
 {
  P = FP->LChild;
  while(P->RChild != NULL)
  {
   FP = P;
   P = P->RChild;
  } // End of while(P->RChild != NULL)
 } // End of if(cmd == largest)

 if(cmd == smallest)
 {
  P = FP->RChild;
  while(P->LChild != NULL)
  {
   FP = P;
   P = P->LChild;
  } // End of while(P->LChild != NULL)
 } // End of if(cmd == smallest)
}

 


int DelKV(int KV)
{
 BSTPointer GF;
 BSTPointer F;

 GF = RootEntry->LChild;
 F = GF->LChild;
 if(F == NULL)
 {
  cout << "Nothing to delete!!!\n";
  return -1;
 }

 SearchKV(KV);

 if(Result == -1)
 {
  cout << "No KV!!!\n";
  return -1;
 } else {

  while(KV !=F->Data)
  {
    if(KV > F->Data)
    {
     GF = F;
     F = F->RChild;
    } else {
     F->LSize = F->LSize - 1;
     
     if(F->RChild != NULL)
      AddDelLSize(F->RChild, del);
     
     GF = F;
     F = F->LChild;
    }  // End of if(KV > F->Data)
  }  // End of while(KV !=F->Data)

  if(F->LChild == NULL && F->RChild == NULL)
  {
   if(GF->LChild == F)
    GF->LChild = NULL;
   else
    GF->RChild = NULL;
  } else {
   if(F->LChild == NULL)
   {
    SearchTheLargestOfLeftandTheSmallestofRight(F, smallest);
    F->LSize = F->LSize - 1;

    if(F->RChild != NULL)
     AddDelLSize(F->RChild, del);

    F->Data = P->Data;
    F->LSize = P->LSize;

    if(F == FP)
    {
     if(P->RChild != NULL && P->LChild == NULL)
      F->RChild = P->RChild;
     else
      F->RChild = NULL;
    } else {
     FP->LChild = NULL;
    }  // End of if(F = FP)
   } else {
    SearchTheLargestOfLeftandTheSmallestofRight(F, largest);
    F->LSize = F->LSize - 1;

    if(F->RChild != NULL)
     AddDelLSize(F->RChild, del);

    F->Data = P->Data;
    F->LSize = P->LSize;

    if(F == FP)
    {
     if(P->LChild != NULL && P->RChild == NULL)
      F->LChild = P->LChild;
     else
      F->LChild = NULL;
    } else {
     FP->RChild = NULL;
    }  // End of if(F = FP)
   } // End of if(F->LChild == NULL)
  }  // if(F->LChild == NULL && F->RChild == NULL)
 } // End of if(Result == -1)
 return 0;
}

int PrintByPreOrder(void)
{
 BSTPointer Temp;
 Temp = RootEntry->LChild->LChild;

  if(Temp == NULL)
 {
  cout << "This is a empty BST!!!\n";
  return 0;
 } else {

  while(1) // while#1
  {
   if(Temp->LChild == NULL)
   {
    if(Temp->RChild == NULL)
    {
     cout << "[" << Temp->Data << "/" << Temp->LSize << "] ";
     while(1) // while#2
     {
      if(gSP == 0)
       return 0;
      else {
       Temp = POP();

       if(Temp == NULL)
       {
        cout << "Stack is empty!!!\n";
        return 0;
       } else {
        Temp = Temp->RChild;

        if(Temp != NULL)
         break;
       } // End of if(Temp == NULL)
      } // End of if(gSP == 0)
     } // End of while#2
    } else {
     cout << "[" << Temp->Data << "/" << Temp->LSize << "] ";
     Temp = Temp->RChild;
    } // End of if(Temp->RChild == NULL)
   } else {

    PUSH(Temp);
    if(Result == -1)
    {
     cout << "Stack is full!!!\n";
     return 0;
    } else {
     cout << "[" << Temp->Data << "/" << Temp->LSize << "] ";
     Temp = Temp->LChild;
    } // End of if(Result == -1)
   }  // End of if(Temp->LChild != NULL)
  } // End of while#1
 } // End of if(Temp == NULL)
}



Today's Visitors: 0 Total Visitors: 63
Personal Category: 台北科技大學 Topic: learning / education / advanced edu.
Previous in This Category: 資料結構作業六(補充)   Next in This Category: 資料結構作業八之一:QUICK SORT
[Trackback URL]

Post A Comment









Yes No



Please input the magic number:

( Prevent the annoy garbage messages )
( What if you cannot see the numbers? )
Please input the magic number

誰來收藏
Loading ...
unlog_NVPO 0