搞死人的資料結構作業七: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)
}

Previous in This Category: 資料結構作業六(補充) Next in This Category: 資料結構作業八之一:QUICK SORT

