#include <stdlib.h>
#include <graphics.h>
#include <stdio.h>
#include <conio.h>
#define DATA int
#define TRUE 1
#define FASLE 0
struct node
{
DATA key;
struct node *pL, *pR;
};
typedef struct node NODE;
typedef NODE *TREE;
void init(TREE &t)
{
t=NULL;
}
int insertNode(TREE &t, DATA k)
{
if(t!=NULL)
{
if(t->key==k) return 0;
if(t->key>k)
return insertNode(t->pL,k);
else
return insertNode(t->pR,k);
}
t=new NODE;
if(t==NULL) return -1;
t->key=k;
t->pL=t->pR=NULL;
return 1;
}
void SearchStandFor(TREE &p, TREE &q)
{
if(q->pL) SearchStandFor(p,q->pL);
else
{
p->key=q->key;
p=q;
q=q->pR;
}
}
int delNode(TREE &t, DATA k)
{
if(t==NULL) return 0;
if(t->key>k) return delNode(t->pL,k);
if(t->key<k) return delNode(t->pR,k);
else
{
NODE *p=t;
if(t->pL==NULL) t=t->pR;
else
if(t->pR==NULL) t=t->pL;
else
{
NODE *q=t->pR;
SearchStandFor(p,q);
}
delete p;
return 1;
}
}
void removeTree(TREE &t)
{
if(t!=NULL)
{
removeTree(t->pL);
removeTree(t->pR);
delete t;
}
}
int empty(TREE t)
{
return (t==NULL?TRUE:FALSE);
}
void kt_dh()
{
/* request auto detection */
int gdriver = DETECT, gmode, errorcode;
/* initialize graphics and local variables */
initgraph(&gdriver, &gmode, "D:/TURBOC~1.0/BGI");
/* read result of initialization */
errorcode = graphresult();
if (errorcode != grOk) /* an error occurred */
{
printf("Graphics error: %s\n", grapherrormsg(errorcode));
printf("Press any key to halt:");
getch();
exit(1); /* terminate with an error code */
}
}
void draw_line(int x1, int y1, int x2, int y2)
{
setcolor(14);
line(x1,y1,x2,y2);
}
void draw_node(TREE t, int xm, int ym)
{
fflush(stdin);
char *str_key;
sprintf(str_key,"%d",t->key);
setcolor(14);
rectangle(xm-20,ym-10,xm+20,ym+10);
setcolor(5);
int text_xm=xm-textwidth(str_key)/2;
int text_ym=ym-textheight(str_key)/2;
outtextxy(text_xm,text_ym,str_key);
}
void draw_tree(TREE t, int x0, int xn, int xm, int ym)
{
if(t!=NULL)
{
draw_node(t,xm,ym);
if(t->pL!=NULL)
{
draw_line(xm,ym+10,(x0+xm)/2,ym+40);
draw_tree(t->pL,x0,xm,(x0+xm)/2,ym+50);
}
if(t->pR!=NULL)
{
draw_line(xm,ym+10,(xm+xn)/2,ym+40);
draw_tree(t->pR,xm,xn,(xm+xn)/2,ym+50);
}
}
}
void chon1(TREE &t)
{
int k;
clrscr();
printf("\n\n\tTao node: ");
scanf("%d",&k);
switch (insertNode(t,k))
{
case -1: printf("\n\n\tDay bo nho"); break;
case 1: printf("\n\n\tNode da duoc tao"); break;
case 0: printf("\n\n\tNode da co san"); break;
}
printf("\n\n\n\tNhan phim bat ki de tro ve menu chinh...");
getch();
}
void chon2(TREE &t)
{
int k;
clrscr();
printf("\n\n\tNhap node can xoa: ");
scanf("%d",&k);
switch (delNode(t,k))
{
case 1: printf("\n\n\tNode da duoc xoa"); break;
case 0: printf("\n\n\tKhong tim thay node can xoa"); break;
}
printf("\n\n\n\tNhan phim bat ki de tro ve menu chinh...");
getch();
}
void chon4(TREE t)
{
clrscr();
kt_dh();
draw_tree(t,0,640,320,80);
getch();
closegraph();
}
void menu()
{
TREE t;
init(t);
char lc;
do
{
clrscr();
printf("\n\n\n\t\t\t\tBinary Search Tree \n\n");
printf("\t\t\t --------------------------------\n");
printf("\t\t\t| 1. Them node |\n");
printf("\t\t\t| 2. Xoa node |\n");
printf("\t\t\t| 3. Tim node |\n");
printf("\t\t\t| 4. Duyet cay |\n");
printf("\t\t\t| 5. Xoa cay |\n");
printf("\t\t\t| 0. Thoat chuong trinh |\n");
printf("\t\t\t --------------------------------\n");
printf("\t\t\tChon muc thuc hien: ");
lc=getch();
switch (lc)
{
case '1': chon1(t); break;
case '2': chon2(t); break;
//case '3': chon3(t); break;
case '4': chon4(t); break;
//case '5': chon5(t); break;
}
}
while(lc!='0');
}
void main()
{
textmode(C80);
menu();
}