btrechar.h

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

void postorder(bitre t)
{
	if (t!=NULL){
		postorder(t->lchild);
		postorder(t->rchild);
		printf("%c",t->data);
	}
}

int high(bitre t)
{
	if (t==NULL)  return 0;
	else return (Max(high(t->lchild),high(t->rchild))+1);
}

int width(bitre t)
{
	if (t==NULL)  return 0;
	else return (width(t->lchild)+width(t->rchild)+1);
}

int nodes(bitre t)
{
	return (width(t));
}

boolean leaf(bitre p)
{
	if ((p->lchild==NULL) && (p->rchild==NULL)) return true;
	else return false;
}

void copy_bitre(bitre t,bitre &tt)
{
	if (t==NULL) tt=NULL;
	else{
		tt=(bitre)malloc(sizeof(struct bnode));
		tt->data=t->data;
		tt->x=t->x;
		tt->y=t->y;
		tt->ltag=0;
		tt->rtag=0;
		copy_bitre(t->lchild,tt->lchild);
		copy_bitre(t->rchild,tt->rchild);
	}
}
       
void  dispose_bitre(bitre &tt)
{
	if (tt!=NULL){
		if (tt->ltag==0)
		dispose_bitre(tt->lchild);
		if (tt->rtag==0)
		dispose_bitre(tt->rchild);
		free(tt);
	}
}

void  gtmaxxy(int &mx,int &my)
{
	mx=getmaxx();
	my=getmaxy();
}

void  dis_btre1(bitre tt,int x1,int y1)
{
	if (tt!=NULL){
		line(x1,y1,tt->x,tt->y-radiuy);
		ellipse(tt->x,tt->y,0,360,radiux,radiuy);
		outtextxy(tt->x,tt->y,conv(tt->data));
		dis_btre1(tt->lchild,tt->x-xl,tt->y+yl);
		dis_btre1(tt->rchild,tt->x+xl,tt->y+yl);
	}
}
       
void  dis_bitre(bitre tt)
{
	int v1,v2,v3,v4;
	if (tt!=NULL){
		xl=radiux*7 / 10;
		yl=radiuy*7 / 10;
		ellipse(tt->x-20, tt->y-20,0,360,5,5);
		dis_btre1(tt,tt->x-20,tt->y-20);
	}
	getch();
}

void  reset_tag(bitre &t)
{
	if (t!=NULL){
		t->ltag=0;
		t->rtag=0;
		reset_tag(t->lchild);
		reset_tag(t->rchild);
	}
}
        
void  comput_btre_widthp(bitre &tt)
{
	if (tt!=NULL){
		comput_btre_widthp(tt->lchild);
		comput_btre_widthp(tt->rchild);
		if ((tt->lchild==NULL)&&(tt->rchild==NULL)){ tt->lw=0;tt->rw=0;}
		else
			if (tt->lchild==NULL){
				tt->lw=Max(0,tt->rchild->lw-1);
				tt->rw=tt->rchild->rw+1;
			}else
				if (tt->rchild==NULL){
					tt->rw=Max(0,tt->lchild->rw-1);
					tt->lw=tt->lchild->lw+1;
				}else
					if (leaf(tt->lchild)){
						tt->lw=Max(1,tt->rchild->lw-1);
						tt->rw=tt->rchild->rw+1;
					}else
						if (leaf(tt->rchild)){
							tt->rw=Max(1,tt->lchild->rw-1);
							tt->lw=tt->lchild->lw+1;
						}else{
							tt->lw=tt->lchild->w;
							tt->rw=tt->rchild->w;
						}
		tt->w=tt->lw+tt->rw+1;
	}
}

void  comput_btre_cardp0(bitre &tt,int xt,int d)
{
	if (tt!=NULL){
		d=d+1;
		tt->y=d;
		tt->x=xt;
		if (tt->lchild==NULL) comput_btre_cardp0(tt->rchild,tt->x+1,d);
		else
			if (tt->rchild==NULL) comput_btre_cardp0(tt->lchild,tt->x-1,d);
			else
				if (leaf(tt->lchild) || leaf(tt->rchild)){
					comput_btre_cardp0(tt->lchild,tt->x-1,d);
					comput_btre_cardp0(tt->rchild,tt->x+1,d);
				}else{
					comput_btre_cardp0(tt->lchild,tt->x-1-tt->lchild->rw,d);
					comput_btre_cardp0(tt->rchild,tt->x+1+tt->rchild->lw,d);
				}  
	}
}

void  comput_node_card1(bitre &tt)
{
	if (tt!=NULL){
		tt->x=tt->x*step_col+strt_col;
		tt->y=tt->y*step_row+strt_row;
        comput_node_card1(tt->lchild);
        comput_node_card1(tt->rchild);
	}
}

void  comput_btre_cardp(bitre &tt)
{
	reset_tag(tt);
	comput_btre_widthp(tt);
	comput_btre_cardp0(tt,tt->lw,0);
	gtmaxxy(mx,my);
    if (mx>tt->w*step_col-10){
    	strt_col=(mx-tt->w*step_col-10) / 2;
    }else step_col=mx / (tt->w+2);
    hi=high(tt);
    if ((hi+1)*step_row-10<my)  strt_row=(my-(hi+1)*step_row-10) / 2;
    else step_row=my / (hi+3);
    comput_node_card1(tt);
}

void   range(bitre t,int &xl,int &yl,int &xr,int &yr,int tag)
{
	if ((t!=NULL) && (tag==0)){
		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->lchild, xl,yl,xr,yr,t->ltag);
		range(t->rchild, xl,yl,xr,yr,t->rtag);
	}
}

void  bitre_range(bitre t,int &xl,int &yl,int &xr,int &yr)
{
	if (t==NULL){
		xl=0;
		yl=0;
		xr=0;
		yr=0;
	}else{
		xl=t->x;
		yl=t->y;
		xr=t->x;
		yr=t->y;
		range(t,xl,yl,xr,yr,0);
		xl=xl-step_col-15; 
		yl=yl-step_row-20;
		xr=xr+step_col+15; 
		yr=yr+step_row-10;
	}
}

void  clear_bitre_range(bitre t)
{
	int xl,yl,xr,yr;
	if (t!=NULL){
		bitre_range(t,xl,yl,xr,yr); 
		Clear_range(xl,yl,xr,yr);
	}
}

void  disp_bitre(string s,bitre &tt)
{
	int v1,v2,v3,v4;
    if ( tt==NULL){
    	rectangle(mx / 2-40,my / 2-40,mx / 2+40,my / 2+40);
    	outtextxy(mx / 2,my / 2-5,s);
    	ellipse(mx / 2,my / 2,0,359,radiux,radiuy);
    	line(mx / 2+10,my / 2-10,mx / 2-10,my / 2+10);
    }else{
    	clear_bitre_range(tt);
    	bitre_range(tt,v1,v2,v3,v4);
		v1=v1+8;
		v2=v2+12;
		v3=v3-8;
		v4=v4-8;
        rectangle(v1,v2,v3,v4);
        outtextxy((v1+v3) / 2,v2-5,s);
        dis_bitre(tt);
    }
    getch();
}
          
void  comput_bitre_card(bitre &tt)
{
	comput_btre_cardp(tt);
}

void  display_bitre(string s,bitre &t)
{	
	initial_bitre();
	comput_btre_cardp(t);	
	disp_bitre(s,t);
	getch();   
}

void  change(bitre &t, int dx,int dy,int tag)
{
	if ((t!=NULL) && (tag==0)){
		t->x=t->x+dx;
		t->y=t->y+dy;
		change(t->lchild,dx,dy,t->ltag);
		change(t->rchild,dx,dy,t->rtag);
	}
}

void  disp_bitre_at(string s,bitre &tt,int x,int y)
{
	comput_bitre_card(tt);
	change_card_to(tt,x,y);
	disp_bitre(s,tt);
}

void  disp_thbitre_at(string s,bitre &tt,int x,int y)
{
	comput_thbitre_card(tt);
	change_card_to(tt,x,y);
	disp_thbitre(s,tt);
}

void  change_card_dxy(bitre &t,int dx,int dy)
{
	if (t!=NULL)  change(t,dx,dy,0);
}

void  change_card_to(bitre &t,int x,int y)
{
	int xl,yl,xr,yr;
	bitre_range(t,xl,yl,xr,yr);
	change_card_dxy(t,x-xl,y-yl);
}

void  move_bitre_dxy(string s,bitre &t,int dx,int dy)
{
	int xl,yl,xr,yr;
	if (t!=NULL){
		change_card_dxy(t,dx,dy); 
		disp_bitre(s,t);
	}
}
 
void  move_bitre_to(string s,bitre &t,int x1,int y1)
{
	int xl,yl,xr,yr;
	bitre_range(t,xl,yl,xr,yr);  
	move_bitre_dxy(s,t,x1-xl,y1-yl);
}

void  move_thbitre_dxy(string s,bitre &t,int dx,int dy)
{
	int xl,yl,xr,yr;
	if (t!=NULL){
		change_card_dxy(t,dx,dy);
		disp_thbitre(s,t);
	}
}

void  move_thbitre_to(string s,bitre &t,int x1,int y1)
{
	int xl,yl,xr,yr;
	bitre_range(t,xl,yl,xr,yr);
	move_thbitre_dxy(s,t,x1-xl,y1-yl);
}

void  calnew(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  mvcur(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);
				calnew(x,y,key,dxl,dyl,dxr,dyr);
				putimage(x,y,ff,1);
			}else printf("\007");
	}while ((key!=10)&&(key!=13));
}

void  mmmbtr(int &curx,int &cury,bitre t)
{
//	dir_keyset=[up,down,left,right,bigleft,bigright];
    Menu("the referenced  node is root");
    bitre_range(t,xl,yl,xr,yr);
	dxl=step_col+t->x-xl;
	dyl=step_row*3 / 2;
	dxr=step_col+xr-t->x;
	dyr=yr-t->x+2*radiuy;
    mvcur(curx,cury,dxl,dyl,dxr,dyr,ndcur);
}

void  set_range0(bitre &t,int &x,int &y)
{
	int dxl,dyl,dxr,dyr;
//	dir_keyset=[up,down,left,right,bigleft,bigright];
	Menu("set bitre left,up angle");
	x=70;
	y=70;
	dxl=30;
	dyl=30;
	dxr=70;
	dyr=70;
    mvcur(x,y,dxl,dyl,dxr,dyr, ndcur);
}

void  set_bitre_range(bitre &t)
{
	int x,y;
	set_range0(t,x,y);
	comput_bitre_card(t);
	change_card_to(t,x,y);
}

void  set_thbitre_range(bitre &t)
{
	int x,y;
	set_range0(t,x,y);
	comput_thbitre_card(t);
	change_card_to(t,x,y);
}

void  move_bitre(string s, bitre &t)
{
	int curx,cury;
	curx=t->x-radiux; 
	cury=t->y-radiuy;mmmbtr(curx,cury,t);
	move_bitre_dxy(s,t,curx-t->x,cury-t->y);
}

void  move_thbitre(string s, bitre &t)
{
	int curx,cury;
	curx=t->x-radiux;
	cury=t->y-radiuy;
	mmmbtr(curx,cury,t);
	move_thbitre_dxy(s,t,curx-t->x,cury-t->y);
}

void  move1_bitre(string s, bitre &t)
{
	int curx,cury,xl,yl,xr,yr;
	bitre_range(t,xl,xr,yl,yr);
	curx=t->x-radiux; 
	cury=t->y-radiuy;
	mmmbtr(curx,cury,t);
    Clear_range(xl,yl,xr,yr);
    move_bitre_dxy(s,t,curx-t->x,cury-t->y);
}

void  move1_thbitre(string s, bitre &t)
{
	int curx,cury,xl,yl,xr,yr;
	bitre_range(t,xl,xr,yl,yr);
	curx=t->x-radiux;
	cury=t->y-radiuy;
	mmmbtr(curx,cury,t);
	Clear_range(xl,yl,xr,yr);
	move_thbitre_dxy(s,t,curx-t->x,cury-t->y);
}

/*
  void  copy_threaded_bitre(bitre tt,var ttp:bitre)
    void  copy_half_thrdbtre(bitre t,bitre &tt)
      { if ( t==NULL )  tt=NULL
              else {  new(tt); tt->data=t->data;
                          tt->ltag=t->ltag;tt->rtag=t->rtag;
                       if ( t->ltag==0 ) 
                          copy_half_thrdbtre(t->lchild,tt->lchild);
                       if ( t->rtag==0 ) 
                          copy_half_thrdbtre(t->rchild,tt->rchild);
          }      }
     void  which(bitre thrd,bitre t,bitre tt,var ttnd:bitre;var find:boolean)
        {
            if ( thrd==NULL )  { ttnd=NULL;find=true }
            else if ( thrd==t )  { find=true;ttnd=tt }
                 else if ( t==NULL )  find=false
             else { if ( t->ltag==0
                           )   which(thrd,t->lchild,tt->lchild,ttnd,find)
                           else find=false;
                         if ( ! find ) 
                           if ( t->rtag==0 ) 
                            which(thrd,t->rchild,tt->rchild,ttnd,find)
                         else find=false;
        }       }
     void  fillthread(bitre t,var tp:bitre;bitre tt,var ttp:bitre)
        var find:boolean;    pp:bitre;
        { if ( t!=NULL ) 
           {
             if ( t->ltag==1
                )   which(t->lchild,tt,ttp,tp->lchild,find)
                else fillthread(t->lchild,tp->lchild,tt,ttp);
             if ( t->rtag==1
                )   which(t->rchild,tt,ttp,tp->rchild,find)
                else fillthread(t->rchild,tp->rchild,tt,ttp);
         } }
      {  copy_half_thrdbtre(tt,ttp); ccc=readkey; writeln;
             fillthread(tt,ttp,tt,ttp);  ccc=readkey;
      }
   void  copy_thread_bitre(bitre tt,var ttp:bitre)
      {  copy_threaded_bitre(tt,ttp) }
*/

int high1(int tag,bitre t)
{
	if ((t==NULL) || (tag==1))  return 0;
	else return (Max(high1(t->ltag,t->lchild),high1(t->rtag,t->rchild))+1);
}

int highth(bitre t)
{
	return (high1(0,t));
}

void  thread(ldr lr,bitre t,int x1,int y1)
{
	struct linesettingstype lpr;
	word clr;
	int y0;
	clr=getcolor();
	if (getmaxy()>250)  setcolor(GREEN);
	getlinesettings(&lpr);
	setlinestyle(DASHED_LINE,lpr.upattern,lpr.thickness);
	if (t==NULL)
		switch (lr){
			case lt:{
				ellipse(x1-radiux / 2,y1,180,359,radiux / 2,radiuy / 2);
				Arrow(x1-radiux,y1,x1-2*radiux,y1-step_row);
				break;
			}
			case r:{
				ellipse(x1+radiux / 2,y1,180,359,radiux / 2,radiuy / 2);
				Arrow(x1+radiux,y1,x1+2*radiux,y1-step_row);
				break;
			}
        }