trees.h

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

	tptrlink p;
	int k,n,l,sg;
	n=0;
	l=8*strlen(sptr->ptrname) / 2;
	k=0;
    if (sp!=NULL){
    	p=frsttptr;
    	while ((p!=NULL)){
    		if ((p->ptr==sp) && (strcmp(p->ptrname,sptr->ptrname))) n=n+1;
    		p=p->next;
    		k=k+1;
	    }
	    if ( sptr->x>0 ) ptrcases(sptr,l);
	    sptr->ptr=sp;
	    sptr->num=n % 4+1;
        switch (sptr->num){
        	case 1:{sptr->x=sp->x-l;sptr->y=sp->y-36;break; }
        	case 2:{sptr->x=sp->x-l;sptr->y=sp->y+28;break; }
        	case 3:{sptr->x=sp->x-2*l-28;sptr->y=sp->y-4;break; }
        	case 4:{sptr->x=sp->x+28;sptr->y=sp->y-4;break; }
        }
        sptr->x=sptr->x+rdx;
        sptr->y=sptr->y+rdy;
        ptrcases(sptr,l);
	}else{
		sptr->x=0;
		sptr->y=0;
		sptr->ptr=NULL;
	}
}

void initial_tree()
{
	Into_graph(); 
	int w;
	if ((graph_state==0) || (tree_graph_state==0)){
		tree_graph_state=1; 
		may=25;
        if (getmaxy()>250){
        	steprowt=3*Round(getmaxy()/may)-4;
        	rdy=steprowt / 8;
			startrow=2*Round(getmaxy()/may)+2;
        }
 //     setfillstyle(1,0);
 //     setcolor(forcolor);
 //		setbkcolor(1);
 //		textcolor(14);
 //		textbackground(1);
        settextjustify(CENTER_TEXT,CENTER_TEXT);
        directvideo=false;
        w=rdx+rdx;
        ellipse(rdx+1,rdy+1,0,360,rdx,rdy);
        size=imagesize(1,1,w+1,2*rdy+1);
        ff=farmalloc(size);
        getimage(1,1,w+1,2*rdy+1,ff);
        ellipse(rdx+1,rdy+1,0,360,rdx-1,rdy-1);
        size=imagesize(1,1,2*rdx,2*rdy); 
        datafild=farmalloc(size);
        getimage(1,1,2*rdx,2*rdy,datafild);
        setfillpattern(fillmode,fillcolor);
        pieslice(rdx+1,rdy+1,0,359,rdx-1);  
        putimage(1,1,datafild,1);
        size=imagesize(2,2,2*rdx,2*rdy);
        datafild=farmalloc(size);
        getimage(2,2,2*rdx,2*rdy,datafild);
        putimage(2,2,datafild,1);
        size=imagesize(1,1,5,20);
        fd1t=farmalloc(size);
        fd2t=farmalloc(size);
        Arrow(3,1,3,20);
        getimage(1,1,5,20,fd1t); 
        putimage(1,1,fd1t,1);
        Arrow(3,20,3,1); 
        getimage(1,1,5,20,fd2t);
        putimage(1,1,fd2t,1);
        size=imagesize(1,1,20,5);
        fd3t=farmalloc(size);
        fd4t=farmalloc(size);
        Arrow(1,3,20,3);
        getimage(1,1,20,5,fd3t);
        putimage(1,1,fd3t,1);
        Arrow(20,3,1,3);
        getimage(1,1,20,5,fd4t);
        putimage(1,1,fd4t,1);
        size=imagesize(1,1,20,20); 
        ndcur=farmalloc(size);
        bar(1,1,20,20);
        getimage(1,1,20,20,ndcur);
        putimage(1,1,ndcur,1);
	}
    setfillstyle(1,0);
    bar(0,0,getmaxx(),getmaxy());
    setfillstyle(1,fillcolor);//white
	for(i=0;i<4;i++) visitetreemodes[i]=onevisitemodet;
}

void fifild(tree t,int orxor)
{
	putimage(t->x+1,t->y+1,datafild,orxor);
}

void disp_tnode_data(tree t)
{
	fifild(t,2);
	fifild(t,1);
	outtextxy(t->x+rdx,t->y+rdy,conv(t->data));
}

void disnodedat(tree t)
{
	disp_tnode_data(t);
}

void copy_grtree_tree(tree grt,tree &tre)
{
	if (grt==NULL) tre=NULL;
	else{
		tre=(tree)malloc(sizeof(struct grtnode));
		tre->data=grt->data;
		copy_grtree_tree(grt->firstson,tre->firstson);
		copy_grtree_tree(grt->nextbrother,tre->nextbrother);
	}
}
  
void copy_tree(tree grt,tree &tre)
{
	copy_grtree_tree(grt,tre);
}

void copy_tree_bitre(tree tre,bitre &bt)
{
	if (tre==NULL) bt=NULL;
	else {
		bt=(bitre)malloc(sizeof(struct bnode));
		bt->data=tre->data;
		copy_tree_bitre(tre->firstson,bt->lchild);
		copy_tree_bitre(tre->nextbrother,bt->rchild);
	}
}

void copy_bitre_tree(bitre bt,tree &tre)
{
	if (bt==NULL) tre=NULL;
	else{
		tre=(tree)malloc(sizeof(struct grtnode));
		tre->data=bt->data;
		copy_bitre_tree(bt->lchild,tre->firstson);
		copy_bitre_tree(bt->rchild,tre->nextbrother);
	}
}


boolean is_tree_leaf(tree t)
{
	if (t->firstson==NULL) return true;
	else return false;
}

void tw(tree &t,int &h)
{
	int w,wr,hr;
	tree ts;
	if (is_tree_leaf(t)){
		t->x=2;
		h=1;
	}else{
		ts=t->firstson;
		w=0;
		wr=0;
		h=0;
		while (ts!=NULL){
			tw(ts,hr);
			h=Max(h,hr);
			if (is_tree_leaf(ts)){
				wr=wr-2;
				if (wr<2) w=w+2;
			}else{
				wr=ts->x / 2;
				w=w+ts->x;
			}
		    ts=ts->nextbrother;
		}
		t->x=w;
		h=h+1;
	}
}

void tcol(tree &t,int startx,int &rightx,int &rootx)
{
	int w,wr,leftrotx,lastcol;
	grtlink ts;
	w=t->x; 
	t->x=1+startx+t->x / 2;
	rightx=startx+w;
	rootx=t->x;
    wr=0;
    ts=t->firstson;
    leftrotx=startx;
    lastcol=startx;
	while (ts!=NULL){
		if (! is_tree_leaf(ts)){
			wr=ts->x / 2;
			tcol(ts,lastcol,lastcol,leftrotx);
		}else{
			wr=wr-2;
			if (wr>=2) tcol(ts,leftrotx,lastcol,leftrotx);
			else tcol(ts,lastcol,lastcol,leftrotx);
		}
		lastcol=lastcol;
		ts=ts->nextbrother;
	}
}

void tc(tree &t)
{
	int s1,s2;
	tcol(t,1,s1,s2);
}

void cc1(tree &t,int y0,int stepcol,int steprowt,int startx,int starty)
{
	if (t!=NULL){
		t->x=(t->x-2)*stepcol+startx;
		t->y=y0*steprowt+starty;
		cc1(t->firstson,y0+1,stepcol,steprowt,startx,starty);
		cc1(t->nextbrother,y0,stepcol,steprowt,startx,starty);
	}
}

void cc(tree &t,int stepcol,int steprowt,int startx,int starty)
{
	cc1(t,0,stepcol,steprowt,startx,starty);
}

void cal_card(tree &grt)
{
	int w,lsz,mmx,mmy,may,key,i,ww,hh;
	tree rr;
	rr=(tree)malloc(sizeof(struct grtnode));
	rr->firstson=grt;
	rr->nextbrother=NULL;
	rr->lbro=NULL;
	rr->father=NULL;
	tw(rr,hh);
	ww=rr->x;
	tc(rr);
    mmx=Min(getmaxx()-40,(ww-1)*stepcol+2*rdx);
    mmy=Min(getmaxy()-3*startrow / 2,hh*steprowt+2*rdy);
    stepcol=(mmx-2*rdx) / (ww-1);
    steprowt=(mmy-2*rdy) / (hh-1);
    cc(rr,stepcol,steprowt,(getmaxx()-mmx) / 2,startrow);
}
/*
void quest_save_tree(tree t)
{
	if (Answer_yes("save"))  save_tree(t);
}
 
void quest_load_tree(tree &t)
{
	if (Answer_yes("load"))  load_tree(t);
}
*/
void comput_tree_card(tree &t)
{
	cal_card(t);
}
   
void  range(tree t, int &xl,int &yl,int &xr,int &yr)
{
	if (t!=NULL){
		if (t->x<xl) xl=t->x;
		if (t->y<yl) yl=t->y;
		if (t->x>xr) xr=t->x;
		if (t->y>yr) yr=t->y;
		range(t->firstson, xl,yl,xr,yr);
		range(t->nextbrother,xl,yl,xr,yr);
	}
}

void tree_range(tree &t, int &xl,int &yl,int &xr,int &yr)
{
	xl=t->x;  
	yl=t->y;
	xr=t->x;
	yr=t->y;
	range(t,xl,yl,xr,yr);
	xl=xl-2*rdx-10;
	yl=yl-2*rdy-20;
	xr=xr+4*rdx+10;
	yr=yr+4*rdy+10;
}
 
 
void join(float x,float y,float x1,float y1,int &nx,int &ny)
{
	float dx,dy,l;
	if (x==x1){
		dx=0;
		dy=rdy;
	}else{
		l=(pow(pow(x-x1,2)+pow(y-y1,2),0.5));
		dx=((x-x1)*rdx/l);
		dy=((y-y1)*rdy/l);
	}
	nx=Round(x1+dx);
	ny=Round(y1+dy);
} 

void dis_tre1(tree f,tree t,int x1,int y1)
{
	int nx,ny;
	if (t!=NULL){
		if (x1+y1!=0){
			join(t->x+rdx,t->y,x1,y1-rdy,nx,ny);
			line(nx,ny,t->x+rdx,t->y);
		}
		ellipse(t->x+rdx,t->y+rdy,0,360,rdx,rdy);
		disnodedat(t);
        dis_tre1(t,t->firstson,t->x+rdx,t->y+2*rdy);
        dis_tre1(f,t->nextbrother,x1,y1);
    }
}
  
void clear_tree_range(tree t)
{
	int v1,v2,v3,v4;
	tree_range(t,v1,v2,v3,v4); 
	Clear_range(v1,v2,v3,v4);
}


void dis_tree1(string s, tree &t)
{
	int v1,v2,v3,v4;
	tree_range(t,v1,v2,v3,v4);
	Clear_range(v1,v2,v3,v4);
	v1=v1+10;
	v2=v2+20;
	v3=v3-10;
	v4=v4-10;
    rectangle(v1,v2,v3,v4);
    outtextxy((v1+v3) / 2,v2-5,s);
    dis_tre1(NULL,t,0,0);
    getch();
    getch();
}

void dis_tree(tree t)
{
	dis_tre1(NULL,t,0,0);
}

void display_tree(string s,tree &t)
{
	initial_tree();
	comput_tree_card(t);
	dis_tree1(s,t);
	getch();
	getch();
}

void disp_tree(string s,tree &t)
{
	dis_tree1(s,t);
}

void change(tree &t,int dx,int dy)
{
	if (t!=NULL){
		t->x=t->x+dx;
		t->y=t->y+dy;
		change(t->firstson,dx,dy);
		change(t->nextbrother,dx,dy);
	}
}

void disp_tree_at(string s,tree &t,int x,int y)
{
	comput_tree_card(t);
	change_trecard_to(t,x,y);
	disp_tree(s,t);
}

void change_trecard_dxy(tree &t,int dx,int dy)
{
	if (t!=NULL)  change(t,dx,dy);
}

void change_trecard_to(tree &t,int x,int y)
{
	int xl,yl,xr,yr;
	tree_range(t,xl,yl,xr,yr); 
	change_trecard_dxy(t,x-xl,y-yl);
}
 
void move_tree_dxy(string s,tree &t,int dx,int dy)
{
	int xl,yl,xr,yr;
	if (t!=NULL){
		tree_range(t,xl,yl,xr,yr);
		setfillstyle(1,0);
		bar(xl-stepcol-10,yl-steprowt-10,xr+stepcol+20,yr+steprowt);
		change_trecard_dxy(t,dx,dy);
		disp_tree(s,t);
	}
}
 
void move_tree_to(string s,tree &t,int x1,int y1)
{
	int xl,yl,xr,yr;
	tree_range(t,xl,yl,xr,yr);
	move_tree_dxy(s,t,x1-xl,y1-yl);
}

void calnewtree(int  &x,int &y,int key,int dxl,int dyl,int dxr,int dyr)
{
	int i,x0,y0;
	i=0;
	while ((i<=dirnum) && (key!=mv[i][2]))  i++;
	x0=x+mv[i][0]*mvstep;
	y0=y+mv[i][1]*mvstep;
	if (((x0>getmaxx()-dxr) || (x0<dxl) || (y0>getmaxy()-dyr) || (y0<dyl))) printf("\007");
	else{
		x=x0;
		y=y0;
	}
}

void mvcurtree(int &x,int &y,int dxl,int dyl,int dxr,int dyr,ffield &ff)
{
	int key;
	boolean funckey;
	putimage(x,y,ff,1);
	do{
		Getkey(key,funckey);
		if ((key!=10)&&(key!=13))
			if ((key==up)||(key==down)||(key==left)||(key==right)||(key==bigleft)||(key==bigright)){
				putimage(x,y,ff,1);
				calnewtree(x,y,key,dxl,dyl,dxr,dyr);
				putimage(x,y,ff,1);
			}else printf("\007");
	}while ((key!=10)&&(key!=13));
}

void mmmtre(int &curx,int &cury, tree &t)
{
//	dir_keyset=[up,down,left,right,bigleft,bigright];
	Menu("the referenced  node is root");
	tree_range(t,xl,yl,xr,yr);
	dxl=stepcol+t->x-xl; 
	dyl=steprowt*3 / 2;
	dxr=stepcol+xr-t->x;
	dyr=yr-t->x+2*rdy;
	mvcurtree(curx,cury,dxl,dyl,dxr,dyr,ndcur);
}

void set_tree_range(tree &t)
{
	int x,y,dxl,dyl,dxr,dyr;