trees.h

该包是数据结构的实验软件,来源于合肥工业大学人工智能与数据挖掘实验室,用来实现数据结构.

//	dir_keyset=[up,down,left,right,bigleft,bigright];
	Menu("set tree range left, up conner");
	x=70;
	y=70;
	dxl=30;
	dyl=30;
	dxr=70;
	dyr=70;
    mvcurtree(x,y,dxl,dyl,dxr,dyr,ndcur);
    comput_tree_card(t);
    change_trecard_to(t,x,y);
}

void move_tree(string s,tree &t)
{
	int curx,cury;
	curx=t->x-rdx / 4*3;
	cury=t->y-rdy / 4*3;
	mmmtre(curx,cury,t);
	move_tree_dxy(s,t,curx-t->x,cury-t->y);
}

void move1_tree(string s,tree &t)
{
	int curx,cury,x1,y1,x2,y2;
	tree_range(t,x1,y1,x2,y2);
	curx=t->x-rdx / 4*3;
	cury=t->y-rdy / 4*3;
	mmmtre(curx,cury,t);
	Clear_range(x1,y1,x2,y2);
	move_tree_dxy(s,t,curx-t->x,cury-t->y);
}

void write_attnode_angle(tree t,int an,string ss)
{
	int x1,y1,l;
	float angle;
	l=an / 360;
	angle=an*2*PI/360;
	x1=t->x+rdx+Round((2+rdx)*(2+l)*cos(angle));
	y1=t->y+rdy-Round((2+rdy)*(2+l)*sin(angle));
	outtextxy(x1,y1,ss);
}

void writestr_attnode_angle(tree t,int an,string ss)
{
	write_attnode_angle(t,an,ss);
}

void writeint_attnode_angle(tree t,int an,int ii)
{
	char ss[255];
	Convs(ii,ss);
	write_attnode_angle(t,an,ss);
}

void dispstr_attnode_angle(string ss,tree t,int an)
{
	write_attnode_angle(t,an,ss);
}

void dispint_attnode_angle(int ii,tree t,int an)
{
	char ss[255];
	Convs(ii,ss);
	write_attnode_angle(t,an,ss);
}
/*
   function llx(p:tree):integer;
     var q:grtlink;j,x1:integer;
     function lmxd(p:tree;i:integer):integer;
      function lmxr(p:tree;i:integer):integer;
        var x1,x2:integer;
        { if ( p==NULL ) lmxr=0
              else { if ( i==0 ) x1=p^.x
                                else x1=lmxd(p^.firstson,i-1);
                         x2=lmxr(p^.nextbrother,i);
                         lmxr=max(x1,x2);
                   }
        };
      { if ( p==NULL ) lmxd=0
                else if ( i==0 ) lmxd=p^.x
                  else lmxd=lmxr(p^.firstson,i-1)
       };
     {   q=p;j=0;x1=0;
        repeat
            while ( (x1==0) && (q^.lbro!=NULL) ) 
            { q=q^.lbro;x1=lmxd(q,j) };
            if ( (x1==0) && (q^.father!=NULL)
	      ) { j=j+1;q=q^.father };
        until (x1!=0) || (q==NULL)
     };
*/
void dismenutree(int ll)
{
	char ss[255],s[255],s1[255],space[255],mss[255],ms1[255],stemp[255];
	setfillstyle(1,0);
	rectangle(1,1,getmaxx(),startrow-2);
	bar(2,2,getmaxx()-2,startrow-3);
	strcpy(s,"ctrl w : return , ");
	switch(ll){
		case d:{
			strcpy(s1,"<--:lbrother, -->:rbrother,up:parent,down:lson, ^i or space:input");
			strcpy(ss,"  data field ");
			strcpy(ms1,"<--:到左兄弟, -->:到右兄弟, up:到父结点, down:到第一个孩子, ^i 空格:输入数据");
			strcpy(mss," ");
			break;
		}
		case m:{
			strcpy(s1,"<-- , ctrl <--  : move left,  -->,ctrl --> : move right,esc:abort");
			strcpy(ss," locate node ");
			strcpy(ms1,"<-- , ctrl <--: 左移,  -->,ctrl--> : 右移, esc:取消");
			strcpy(mss," 选择结点位置: ");
            break;
        }
        case 3:{
         	strcpy(s1," data ,end by return ");
         	strcpy(ss," input data");
         	strcpy(s," ");
            strcpy(ms1,"以回车结束 ");
            strcpy(mss," 输入数据: ");
            break;
        }  
	}
	strcat(ss,s);
	strcpy(space,"                                                         ");
	outtextxy(getmaxx() / 2,6,space);
	outtextxy(getmaxx() / 2,17,space);
	outtextxy(getmaxx() / 2,6,ss);
	outtextxy(getmaxx() / 2,17,s1);
	strcpy(stemp,mss);
	strcat(stemp,ms1);
	Menu(stemp);
}

void locttnod(tree &t,int fx,int fy,int lx,ffield ff)
{
	int key;
	tree fa;
	int step;
    dismenutree(m);
	putimage(t->x,t->y,ff,1);
	do{
		Getkey(key,funckey);
		if ((key!=10)&&(key!=13)&&(key!=esc)){
			if ( funckey && ((key==left)||(key==right)||(key==bigleft)||(key==bigright))){
				if ((key==left)||(key==right))  step=keystept; 
				else step=bigstep;
				putimage(t->x,t->y,ff,1);
				switch(key){
					case left:
					case bigleft:t->x=t->x-step;break;
					case right:
					case bigright:t->x=t->x+step;break;
                }//switch
                putimage(t->x,t->y,ff,1);
            }else printf("\007");
        }
        if ( (key==esc) && (t->father==NULL) && (t->lbro==NULL)) {printf("\007");key=49;}
	}while  ((key!=10)&&(key!=13)&&(key!=esc));
	if (key==esc){
		putimage(t->x,t->y,ff,1);
		free(t);
		t=NULL;
	}else
		if (fx+fy!=0)  Arrowdot(fx,fy,t->x+rdx,t->y) ;
}

void crttre1(tree &root)
{
	tree t,p,fa;
	string ss;
	char keych;
	int fx,fy,tag,lx;
	int key;
//  assigncrt(input);reset(input); 
	root=(tree)malloc(sizeof(struct grtnode));
	root->x=getmaxx() / 4;
	root->y=startrow+5;
	fx=0;
	fy=0;
    root->nextbrother=NULL;
    root->father=NULL;
    root->lbro=NULL;
    root->firstson=NULL;
    locttnod(root,fx,fy,0,ff);
    window(50,1,60,2);
    t=root;
    fifild(t,1);
    do{
    	dismenutree(d);
    	Getkey(key,funckey);
    	if ( key!=ctrlw){
    		while ((key==ctrli) || (key==' ')){
    			dismenutree(3);
    			clrscr();
    			scanf("%c",&(t->data));
    			t->hvdt=true;
    			disnodedat(t);
    			fifild(t,1);
    			dismenutree(d);
    			Getkey(key,funckey);
    		}
            if ( key!=ctrlw )
              if (!(funckey && (key==up||key==down||key==left||key==right))) printf("\007");
              else{
				tag=0;
              	switch (key){
              		case left:
              			if (t->lbro==NULL) printf("\007");
              			else{
              				p=t->lbro;
							tag=1;
              			}
              			break;
              		case up:
              			if ( t->father==NULL) printf("\007");
              			else{
              				p=t->father;
							tag=1;
              			}
              			break;
              		case right:
              			if (t->nextbrother!=NULL){
              				p=t->nextbrother;
							tag=1;
              			}else{
              				p=(tree)malloc(sizeof(struct grtnode));
              				p->lbro=t;
              				p->father=t->father;
              				p->nextbrother=NULL;
              				p->firstson=NULL;
              				lx=t->x+stepcol;
              				p->x=lx;
              				p->y=t->y;
              				if (p->father==NULL){
              					fx=0;
              					fy=0;
              				}else{
              					fx=p->father->x+rdx;
              					fy=p->father->y+2*rdy;
              				}
                            p->hvdt=false;
                            locttnod(p,fx,fy,lx,ff);
                            if (p!=NULL){
								tag=1;
                        		t->nextbrother=p;
                        	}
                        }
                        break;
                    case down:
                    	if ((t->firstson!=NULL)){
                    		p=t->firstson;
							tag=1;
                    	}else{
                    		p=(tree)malloc(sizeof(struct grtnode));
                    		p->lbro=NULL;
                    		p->father=t;
                    		p->nextbrother=NULL;
                    		p->firstson=NULL;
                    		lx=Max(0,t->x-4*stepcol);
                    		p->x=t->x;
                    		p->y=t->y+steprowt;
                    		fx=t->x+rdx;
                    		fy=t->y+2*rdy;
                    		p->hvdt=false;
                    		locttnod(p,fx,fy,lx,ff);
                    	    if (p!=NULL){
								tag=1;
                    	    	t->firstson=p;
                    	    }
                        }
                        break;
                }
              }
			if (tag==1){
            	fifild(t,1);
            	fifild(p,1);
            	t=p;
            }
        }
	}while (key!=ctrlw);// getkey(key,funckey);
	window(1,1,80,25);
}

void create_tree(tree &tre)
{
	int w,lsz,may,key,i;
	boolean funckey;
	tree grbt;
	bitre bt;
	string ss;
	initial_tree(); 
	crttre1(grbt);
	copy_grtree_tree(grbt,tre);
	display_tree("grtree",tre);
}
 
void save(tree t,FILE *ff)
{
	boolean k1,k2;
	if (t!=NULL){
		fprintf(ff,"%c%6d%6d",t->data,t->x,t->y);
		if (t->firstson!=NULL) k1=true;
		else k1=false;
		if (t->nextbrother!=NULL) k2=true;
		else k2=false;
		if (k1)  fprintf(ff,"  0");
		else fprintf(ff,"  1");
		if (k2)  fprintf(ff,"  0\n");
		else fprintf(ff,"  1\n");
		if (k1) save(t->firstson,ff);
		if (k2) save(t->nextbrother,ff);
	}
}

void save_tree_file(tree t, string ss)
{
	FILE *ff;
//  assign(ff,ss);rewrite(ff);
	if ((ff=fopen(ss,"w"))==NULL){
		printf("\nCan't open the file !\007");
		getch();
		exit(1);
	}
	fprintf(ff,"tree\n");
	if (t!=NULL) fprintf(ff,"  0\n");
	else fprintf(ff,"  1\n");
	save(t,ff);
	fclose(ff);
}

void load(tree &t,tree fa,tree lb,int xx,FILE *ff)
{
	int k1,k2;
	if (xx==1) t=NULL;
	else{
		t=(tree)malloc(sizeof(struct grtnode));
		t->father=fa;
		t->lbro=lb;
		fscanf(ff,"%c%d%d%d%d",&(t->data),&(t->x),&(t->y),&k1,&k2);
		while (fgetc(ff)!='\n');
		load(t->firstson,t,NULL,k1,ff);
		load(t->nextbrother,fa,t,k2,ff);
	}
}

void load_tree_file(tree &t,string ss)
{
	char bs[255];
	int xx;
	FILE *ff;
//	assign(ff,ss); reset(ff);
	if ((ff=fopen(ss,"r"))==NULL){
		printf("\nCan't open file!\007");
		getch();
		exit(1);
	}
   	fscanf(ff,"%s",bs);
   	while (fgetc(ff)!='\n');
   	fscanf(ff,"%d",&xx);
   	while (fgetc(ff)!='\n');
   	if ( strcmp(bs,"tree")) printf("file error!\007");
	else{
		load(t,NULL,NULL,xx,ff);
		Into_graph();
		comput_tree_card(t);
	}
    fclose(ff);
}
     
void save_tree(tree t)
{
	char ss[255];
	boolean canorno;
	strcpy(ss,"trees\\*.tre");
	Savequestion("save tree to ",ss,canorno);
	if (canorno) save_tree_file(t,ss);
}

void load_tree(tree &t)
{
	char ss[255];
	boolean selected;
	strcpy(ss,"trees\\*.tre");
	Loadquestion("load tree from ",ss,selected);
    if (selected) load_tree_file(t,ss);
}


void handle_tree_event(pmenunode &pmenu,tree &t)
{
	int xl,yl,xr,yr;
	char ss[255],yn1[255];
    switch (pmenu->command-100){
    	case comgrcreatebitre/*tree*/: create_tree(t);break;
    	case comreadbitre/*tree*/:     load_tree(t);break;
    	case comsavebitre/*tree*/:    save_tree(t);break;
    	case comsetrange/*t*/:    set_tree_range(t);break;
    	case comdisp/*t*/:        disp_tree("tree",t);break;
    	case commove1/*t*/:{
    		tree_range(t,xl,yl,xr,yr);
            Inputstrinwnd(20,4,65,"move1disp tree(s),press enter to move root ",ss);
            move_tree("tree",t); 
            Clear_range(xl,yl,xr,yr); 
            disp_tree("tree",t);
            break;}
    	case commove2/*t*/:{
    		Inputstrinwnd(20,4,60,"move2disp tree(s) ",ss); 
    		move_tree("tree",t);
    		break;
    	}
    }
}

void handle_tree_menu(mymenu &treemenu1,boolean &selectorno,pmenunode &pemnu,tree &t)
{
	// with  treemenu1 do
	Mymenu_selectmenu( treemenu1,pmenu,selectorno);
	if ( selectorno)
		if (Mymenu_issubmenuitem(treemenu1)){
			Mymenu_disabledispsubmenu(treemenu1,pmenu->numofmenu / 100);
			handle_tree_event(pmenu,t);
		}else return;
	else return;
}

void handle_tree(tree &t)
{
	tree_graph_state=0; 
	initial_tree();
    bmp=Newmenu1(
         Newsubmenu1("建    树",
            Newmenu1(
              Newitem1("图形方式建树"," ",0,0,comgrcreatebitre/*tree*/+100,
              Newitem1("读文件"," ",0,0,comreadbitre/*tree*/+100,
              Newitem1("存盘"," ",0,0,comsavebitre/*tree*/+100,
              NULL)))),
         Newsubmenu1("显  示  树",
            Newmenu1(
              Newitem1("设定显示区域"," ",0,0,comsetrange/*t*/+100,
              Newitem1("按原定位置显示"," ",0,0,comdisp/*t*/+100,
              Newitem1("平移显示  并清除原位"," ",0,0,commove1/*t*/+100,
              Newitem1("平移显示  不清除原位"," ",0,0,commove2/*t*/+100,
              NULL))))),
         Newsubmenu1("返回",NULL,NULL))));
    Mymenu_init(treemenu1,bmp);
	do{
		handle_tree_menu(treemenu1,selectorno,pmenu,t);
	}while (strcmp(pmenu->menuname,"返回"));
	Mymenu_clearmainmenu(treemenu1);
	Mymenu_reset_cursubmenu(treemenu1);
}

void get_tree(tree &t)
{
	handle_tree(t);
}