Code:
#include "conio.h"
#include "stdio.h"
#include "iostream.h"
#include "graphics.h"
#include "process.h"
#include "dos.h"
#define DX 20
#define DH 30
char s[50]="0000";
int CellH ,CellW;
typedef struct Diem {
int x;
int y;
};
typedef struct TagNode {
Diem data;
TagNode *Left;
TagNode *Right;
};
typedef TagNode *Node;
typedef struct BSTree{
Node Root;
}BSTree;
void init(int &H, int &W)
{
H=textheight(s)+8;
W=textwidth(s)+6;
}
void drawTree(Node &T, int x, int y, int width)
{
if(!T) return;
rectangle(x-CellW/2,y-CellH/2,x+CellW/2,y+CellH/2);
sprintf(s,"%d,%d",T->data.x,T->data.y);
outtextxy(x,y,s);
if(T->Left)
{
line(x,y+CellH/2,x-width,y+CellH/2+DH);
drawTree(T->Left,x-width,y+CellH+DH,width-DX);
}
if(T->Right)
{
line(x,y+CellH/2,x+width,y+CellH/2+DH);
drawTree(T->Right,x+width,y+CellH+DH,width-DX);
}
}
void drawTree(BSTree T)
{
int graphdriver = DETECT,graphmode,errorcode;
initgraph(&graphdriver,&graphmode,"C:\\TC\\BGI");
errorcode=graphresult();
if(errorcode!=grOk)
{
printf("graphics error : %s\n ",grapherrormsg(errorcode));
printf("press any key to halt");
getch();
exit(1);
}
init(CellH,CellW);
settextjustify(CENTER_TEXT,CENTER_TEXT);
drawTree(T.Root,getmaxx()/2,10,60);
getch();
closegraph();
}
/////////////////////////////////////////////////////////////////////
int insertNode(Node &T,Diem A){
if(T){
if(T->data.x==A.x)
{
if(T->data.y==A.y) return(0);
if(T->data.y>A.y) return insertNode(T->Left,A);
else return insertNode(T->Right,A);
}
else if(T->data.x>A.x)return insertNode(T->Left,A);
else return insertNode(T->Right,A);
}
T = new TagNode;
if(!T)return -1;
T->data = A;
T->Left=T->Right=NULL;
return 1;
}
/////////////////////////////////////////////////////////////////////
void deleteTree(Node &T){
if(T){
deleteTree(T->Left);
deleteTree(T->Right);
delete T;
}
}
void init(BSTree &T){
T.Root=NULL;
}
////////////////////////////////////////////////
//tim phan tu nho nhat tren cay con phai
void searchStandFor(Node &p,Node &q)
{
if(q->Left) searchStandFor(p,q->Left);
else
{
p->data.x=q->data.x;
p->data.y=q->data.y;
p=q;
q=q->Right;
}
}
int delNode(Node &B,Diem A)
{
if(!B) return(0);
if(B->data.x>A.x)
return delNode(B->Left,A);
if(B->data.x<A.x)
return delNode(B->Right,A);
if(B->data.x==A.x && B->data.y<A.y)
return delNode(B->Right,A);
if(B->data.x==A.x && B->data.y>A.y)
return delNode(B->Left,A);
else{
Node p=B;
if(!B->Left)B=B->Right;
else if(!B->Right)B=B->Left;
else searchStandFor(p,B->Right);
delete p;
return(1);
}
}
int searchNode(BSTree &T,Diem A)
{
Node p=T.Root; //tim kiem Node khong xai de quy
while(p!=NULL)
{
if(A.x<p->data.x) p=p->Left;
else if(A.x>p->data.x) p=p->Right;
else if(A.x==p->data.x)
{
if(A.y<p->data.y) p=p->Left;
else if(A.y>p->data.y) p=p->Right;
else return(1);
}
}
return(0);
}
void inputPoint(Diem &A)
{
printf("nhap x : ");
fflush(stdin); //xoa bo dem ban phim
scanf("%d",&A.x);
printf("nhap y : ");
fflush(stdin);
scanf("%d",&A.y);
}
///////////////////////////////////////////////
int getFromFile(char *a,BSTree &T)
{
FILE *f;
char c;
f = fopen(a,"rt");
if(f==NULL)return 0;
Diem A; //diem co dang (x,y)
while(!feof(f))
{
fscanf(f,"%c%d%c%d%c",&c,&A.x,&c,&A.y,&c);
insertNode(T.Root,A);
}
c=NULL;
fclose(f);
return 1;
}
//////////////////////////////////////////////////////////////////
void PrintTr(Node B,FILE *f)
{
if(B)
{
PrintTr(B->Left,f);
fprintf(f,"(%d,%d)\n",B->data.x,B->data.y);
PrintTr(B->Right,f);
}
}
//////////////////////////////////////////////////////////////////
int write2File(char *a,BSTree T)
{
FILE *f;
int n;
f = fopen(a,"wt");
if(!f)return 0;
PrintTr(T.Root,f);
fclose(f);
return 1;
}
/////////////////////////////////////////////////////////////////////
void main()
{
clrscr();
BSTree T;
init(T);
Diem A;
char s[30];
char m;
//file input.txt co dang cap diem (x,y), moi dong la 1 cap diem
printf("nhap duong dan file du lieu : ");
gets(s);
getFromFile(s,T);
if(T.Root==NULL)
{
printf("\nkhong tim thay file hoac du lieu cua file bi loi\n");
getch();
exit(0);
}
drawTree(T);
Menu:
clrscr();
printf("\n\tCHUONG TRINH QUAN LY CAC DIEM TREN 2D BANG CAY NHI PHAN TIM KIEM");
printf("\n\n\t\t\t ====>MENU CHINH<====\n\n");
printf("\t 1>/Kiem tra su ton tai cua diem tren cay.\n"); //49
printf("\t 2>/Them diem vao cay.\n"); //50
printf("\t 3>/Xoa diem bat ki tren cay.\n"); //51
printf("\t 4>/Huy toan bo cay.\n"); //52
printf("\t 5>/Luu du lieu xuong file.\n"); //53
printf("\t 6>/Ve cay.\n"); //54
printf("\t-------------------------------------------\n");
printf("\t 7>/Thoat luon.\n\n\n"); //55
printf("Ban chon : ");
do
m=getch();
while(m!=49&& m!=50&& m!=51&& m!=52&& m!=53&& m!=54&& m!=55);
if(m==49) goto Check;
else if(m==50) goto Addpoint;
else if(m==51) goto Deletepoint;
else if(m==52)
{
deleteTree(T.Root);
init(T);
clrscr();
gotoxy(17,10);
printf("Cay da duoc huy thanh cong, khong con diem nao ca.");
getch();
goto Menu;
}
else if(m==53) goto Writefile;
else if(m==54)
{
if(!T.Root)
{
clrscr();
gotoxy(17,10);
printf("Cay khong con diem nao ca -->Khong co gi de ve.");
getch();
}
else drawTree(T);
goto Menu;
}
else if(m==55) goto End;
/////////////////////////////////////////////////////////////////////////
Writefile:
clrscr();
if(T.Root==NULL)
{
printf("\nBSTree khong con du lieu thi luu xuong file lam gi");
getch();
}
else
{
printf("\nnhap duong dan file can xuat du lieu : ");
fflush(stdin);
gets(s);
if(write2File(s,T))
{
write2File(s,T);
printf("\n\t\tDu lieu da luu xuong file thanh cong.");
delay(600);
}
else
{
printf("\nO cung ko du cho trong hoac duong dan sai. ");
getch();
}
}
goto Menu;
//////////////////////////////////////////////////////////////////////////
Check:
clrscr();
printf("\n\tNhap toa do can kiem tra\n");
inputPoint(A);
if(searchNode(T,A))
{
printf("======>Diem ban vua nhap da co trong BSTree");
getch();
}
else
{
printf("======>Diem ban vua nhap khong co trong BSTree");
getch();
}
goto Menu;
///////////////////////////////////////////////////////////////////////////
Addpoint:
clrscr();
printf("\n\tNhap diem can them : \n");
inputPoint(A);
if(!searchNode(T,A))
{
insertNode(T.Root,A);
printf("\t\tDa them thanh cong");
delay(600);
drawTree(T);
}
else
{
printf("\n\t======>Da co diem nay trong BSTree\n");
getch();
}
goto Menu;
///////////////////////////////////////////////////////////////////////////
Deletepoint:
clrscr();
if(!T.Root)
{
printf("Cay khong con diem nao de xoa ca.");
getch();
goto Menu;
}
printf("\n\tNhap diem can xoa : \n");
inputPoint(A);
if(searchNode(T,A))
{
delNode(T.Root,A);
printf("\t\tDa xoa thanh cong");
delay(600);
}
else
{
printf("Khong co diem nay trong BSTree");
getch();
}
if(!T.Root)
{
clrscr();
printf("\n\t\tBSTree khong con diem nao ca");
getch();
goto Menu;
}
else drawTree(T);
goto Menu;
///////////////////////////////////////////////////////////////////////////
End:
deleteTree(T.Root);
}