btreedemodlg.cpp

B-树演示程序(vc++)可执行程序.rar

	NewNode(ap);
	q->keynum=q->keynum-(B_M-s+1);
	(*ap)->keynum=B_M-s;
	for(i=s;i<=B_M;i++)  {
		if(i!=s)  (*ap)->key[j++]=q->key[i];
		(*ap)->ptr[k++]=q->ptr[i];
		if((*ap)->ptr[k-1])  {
			(*ap)->ptr[k-1]->parent=*ap;
		}
	}
	(*ap)->parent=q->parent;

}

int   F_DeleteNode(BTree p,int k)  {  //将p所指的结点中第k个关键字删除,及ptr[k]
	int i;
	for(i=k;i<p->keynum;i++)  {
        p->key[i]=p->key[i+1];
		p->ptr[i]=p->ptr[i+1];
	}
    --p->keynum;
	return 1;
}


int Comp_child(BTree r)  {
	//该函数返回结点r所对应的parant中的ptr个数（num）
	//调用该函数要保证r结点有parent!!! 
	//如果调用出错该函数返回-1!!
	int i=0,j=0;
	BTree p=r->parent;
	BTree tmp=p->ptr[j];
	while(r!=tmp)  {
		++i;
		tmp=p->ptr[++j];
	}
	return i;
}

int   F_GetSbInfo(BTree p)  {//获得兄弟结点的信息：在删除时用于判断属于那种情况
    //此函数返回0表示没有兄弟结点的num大于[m/2]-1，
    
	BTree q;
	int Try=B_M%2?B_M/2+1:B_M/2;
    int num;
	num=Comp_child(p);   //获得父结点指针的num


	if(num+1<=p->parent->keynum)  {//右优先
		q=p->parent->ptr[num+1];   
		if(q->keynum>=Try)  return num+1;
	}
	if((num-1)>=0){   //否则左
		q=p->parent->ptr[num-1];
		if(q->keynum>=Try)  return -num+1;
	}
    return 9999;

}


int   F_FarentExChild(BTree r,int ri,BTree p,int pi)  {
	//将r所指的第ri个关键字，与p所指的第pi个关键字交换
//该函数用于删除非叶子结点
	int tmp;
	tmp=p->key[pi];
	p->key[pi]=r->key[ri];
	r->key[ri]=tmp;
    return 1;
}


BTree F_GetPMaxMin(BTree p,int k,int flag)  {
	//返回p所指结点第k个关键字所对应的ptr[k-1](ptr[k])
    //最大(最小)关键字所对应的BTree指针
	//flag=0表示ptr[k-1]及左端最大值。
	//flag=1表示ptr[k]及右端最小值。
	BTree re=NULL,q=NULL;
	if(flag)  {
		q=p->ptr[k];
		while(q&&q->ptr[0])  {
			q=q->ptr[0];
		}
		if(q)  re=q;
	}
	else  {
		q=p->ptr[k-1];
		while(q&&q->ptr[q->keynum])  {
			q=q->ptr[q->keynum];
		}
		if(q)  re=q;
	}
    return re;
}

BTree   F_DeleteNLeaf(BTree p,int k)  {
//该函数完成删除非叶子结点的第一步：
//与右端最小交换并删除，p为要删除的非叶子结点的指针
	BTree right;
	right=F_GetPMaxMin(p,k,1);  //获得右端最小指针
	F_FarentExChild(p,k,right,1);  //交换之
    F_DeleteNode(right,1);    //删除
	return right;
}



void  F_Combineright(BTree* p)  {
//该函数完成p结点于其父亲结点以及其右兄弟结点的结合
//并且删除相应的结点
	BTree par;
	BTree rsib;
	int num,i;
	//该函数返回结点r所对应的parant中的ptr个数（num）
    num=Comp_child(*p);
	par=(*p)->parent;
	if(num==par->keynum)	*p=par->ptr[num-1],--num;
	rsib=par->ptr[num+1];
	++(*p)->keynum;        //以下两句连接父结点的相应关键字
	(*p)->key[(*p)->keynum]=par->key[num+1];

	for(i=0;i<=rsib->keynum;i++)  {   //将右兄弟连接到p上
		if(i>0)  {
			++(*p)->keynum;
			(*p)->key[(*p)->keynum]=rsib->key[i];
		}
		(*p)->ptr[(*p)->keynum]=rsib->ptr[i];
		if(rsib->ptr[i]) rsib->ptr[i]->parent=*p;
	}
	free(rsib); rsib=NULL; //删除右兄弟
	F_DeleteNode(par, num+1);  //删除父结点相应的关键字

}




void  F_Exchange(BTree p,int flag)  {
//该函数用于被删除结点的兄弟可用的情况
//p为待处理结点
	//flag表示可用兄弟在p->parent上的ptr的num
	BTree par;
	BTree lsib,rsib,tmpp;
	int i;
	//该函数返回结点r所对应的parant中的ptr个数（num）
    par=p->parent;
    if(flag>0)  {  //表示右兄弟可用
	    rsib=par->ptr[flag];
	    ++p->keynum;        //以下两句连接父结点的相应关键字
	    p->key[p->keynum]=par->key[flag];
	    tmpp=rsib->ptr[0];
	    p->ptr[p->keynum]=tmpp;	
	    if(tmpp)  {
		    tmpp->parent=p;//->ptr[p->keynum];
		}
		par->key[flag]=rsib->key[1];
		rsib->ptr[0]=rsib->ptr[1];
		F_DeleteNode(rsib,1);
	}
	else  {
		flag=-flag;
		lsib=par->ptr[flag];
		++p->keynum;
		for(i=p->keynum-1;i>=0;i--)  {
			p->ptr[i+1]=p->ptr[i];
			p->key[i+1]=p->key[i];
		}
		p->key[1]=par->key[flag+1];
		p->ptr[0]=lsib->ptr[lsib->keynum];
		if(p->ptr[0])  {
			lsib->ptr[lsib->keynum]->parent=p;
		}
		par->key[flag+1]=lsib->key[lsib->keynum];
		--lsib->keynum;
	}
}

void DeleteBTree(BTree* t,int k)  {
    Result res;
	BTree q;
	int i,finished=0,found;
    int Try=B_M%2?B_M/2+1:B_M/2;

    res=SearchBTree(*t,k);
    if(res.tag==0)  return ;
	q=res.pt;  i=res.i; 

	if(q->ptr[0])  q=F_DeleteNLeaf(q,i);
	else  F_DeleteNode(q,i);
	if(b_run)  {
	    pwnd->SendMessage(WS_USER_REDRAW);
	    m_ev.Lock();
				//add!!!
	}
	if(q->keynum>=Try-1||!q->parent)  {
		finished=1;
		if(q->keynum==0)  free(*t),*t=NULL;
	}
	while(!finished)  {
        found=F_GetSbInfo(q);
		if(found!=9999)  {
			F_Exchange(q,found);
			if(b_run)  {
			    pwnd->SendMessage(WS_USER_REDRAW);
			    m_ev.Lock();
				//add!!!
			}
            finished=1;
		}
		else  {
			F_Combineright(&q);
			if(b_run)  {
			    pwnd->SendMessage(WS_USER_REDRAW);
			    m_ev.Lock();
				//add!!!
			}
			
			if(q->parent==*t)  {
                if((*t)->keynum==0)  {
					free(*t);
				    (*t)=q;
				    q->parent=NULL;
				    finished=1;
				}
				else if((*t)->keynum<=B_M-1)  finished=1;
			}
			else if(q->parent->keynum>=Try-1) finished=1;
			else q=q->parent;
		}

	}
	pwnd->SendMessage(WS_USER_REDRAW);


}
	//Tree Begin
void Compute_xy(BTree t)  {
	int i;
    BTree q;
	++deep;
	if(t)  {
		t->x=2*deep;
		if(!t->ptr[0])  {
			t->y=p_y;
            q=t->parent;
			while(q)  {
				if(q->y==0)  q->y=t->y;
                else         ++q->y;
                q=q->parent;
			}
			p_y+=t->keynum+1;
		}
		for(i=0;i<=t->keynum;i++)  {
			Compute_xy(t->ptr[i]);
		}
	}
	--deep;	
}//该函数计算屏幕输出相对位置

void Set_xy_Zero(BTree t)  {
	int i;
	if(t)  {
		t->x=t->y=0;
		for(i=0;i<=t->keynum;i++)  {
			Set_xy_Zero(t->ptr[i]);
		}
	}

}


  //删除所有的结点  
void F_DelAll(BTree* t)  {
	int i;
	if(*t)  {
		for(i=0;i<=(*t)->keynum;i++)  {
			Compute_xy((*t)->ptr[i]);
		}
		free(*t);  *t=NULL;
	}
}

void CBTreeDemoDlg::OnRandtree() 
{
	// TODO: Add your control notification handler code here
	if(UpdateData(TRUE)==FALSE)  return;
	if(m_BM<3||m_BM>8)  {
		MessageBox("B-树最大阶数请在3到8之间输入");
		return ;
	}
	if(m_randnum<2||m_randnum>50)  {
		MessageBox("结点个数请在2到50之间输入!");
		return;
	}


	if(B_Tree)  {
		F_DelAll(&B_Tree);
	}
	rand_ip=1;
	B_M=m_BM;
	NewNode(&B_Tree);
    m_randtree.EnableWindow(FALSE);
	m_crandnum.EnableWindow(FALSE);
	m_cBM.EnableWindow(FALSE);
	m_f_delete.EnableWindow(FALSE);
	m_f_insert.EnableWindow(FALSE);
	m_cdelnum.EnableWindow(FALSE);
	m_cinsnum.EnableWindow(FALSE);
	m_delball.EnableWindow(FALSE);
	m_setit.EnableWindow(FALSE);
	m_travorder.EnableWindow(FALSE);
	SetTimer(1,200,NULL);	
}

void CBTreeDemoDlg::OnFInsert() 
{
    if(b_finish)  {
		if(UpdateData()==FALSE)  return;
		if(m_insnum<0||m_insnum>1000)  {
			MessageBox("请在0-999之间选择插入值");
			return;
		}

        DPARAMs ptp;
		ptp.num=m_insnum;
		ptp.sel=1;	
		if(!B_Tree)  NewNode(&B_Tree);
		m_randtree.EnableWindow(FALSE);
	    m_crandnum.EnableWindow(FALSE);
	    m_cBM.EnableWindow(FALSE);
	    m_f_delete.EnableWindow(FALSE);
	    m_cdelnum.EnableWindow(FALSE);
	    m_cinsnum.EnableWindow(FALSE);
		m_delball.EnableWindow(FALSE);
		m_setit.EnableWindow(FALSE);
		m_travorder.EnableWindow(FALSE);

		CWinThread* pThread=AfxBeginThread(ThreadFunc,&ptp,
			THREAD_PRIORITY_NORMAL,0,CREATE_SUSPENDED);
//		::DuplicateHandle(GetCurrentProcess(),pThread->m_hThread,
//			GetCurrentProcess(),&m_handle,0,FALSE,DUPLICATE_SAME_ACCESS);
		pThread->ResumeThread();
		::Sleep(10);
		//m_ev.SetEvent();
		m_f_insert.SetWindowText("继续");

	}
	else  {
		m_ev.SetEvent();

	}
}

LRESULT CBTreeDemoDlg::OnThreadRedraw(WPARAM wParam,LPARAM lParam)  {
	deep=2;
    p_y=1;
	Set_xy_Zero(B_Tree);
	Compute_xy(B_Tree);
	EreaseMdc();
	Draw_To_Mdc(B_Tree);
	MdcDsp();
    return 0;
}

LRESULT CBTreeDemoDlg::OnThreadFinish(WPARAM wParam,LPARAM lParam)  {
	m_randtree.EnableWindow(TRUE);
    m_crandnum.EnableWindow(TRUE);
	m_cBM.EnableWindow(TRUE);
	m_f_delete.EnableWindow(TRUE);
	m_f_insert.EnableWindow(TRUE);
	m_cdelnum.EnableWindow(TRUE);
	m_cinsnum.EnableWindow(TRUE);
	m_delball.EnableWindow(TRUE);
	m_setit.EnableWindow(TRUE);
	m_travorder.EnableWindow(TRUE);
	if((int)wParam==1)  {  //insert
        m_f_insert.SetWindowText("插入");
		m_insnum=rand()%998+1;
		UpdateData(FALSE);
	}
	else  {
		m_f_delete.SetWindowText("删除");
		m_delnum=rand()%998+1;
		UpdateData(FALSE);

	}

	return 0;
}

UINT ThreadFunc(LPVOID pParam)  {
	int num,sel;
    DPARAMs* ptp=(DPARAMs*)pParam;
	num=ptp->num;
	sel=ptp->sel;

	b_finish=FALSE;/////
	b_run=TRUE;/////
        
    if(sel)  {  //如果是插入命令
        Sch_InsBTree(&B_Tree,num);

	}
	else  {   //否则是删除命令
		//add later!!
		DeleteBTree(&B_Tree,num);

	}


	b_finish=TRUE;/////
	b_run=FALSE;/////
	pwnd->SendMessage(WS_USER_FINISH,sel);
	return 0;
}

void CBTreeDemoDlg::OnFDelete() 
{
	// TODO: Add your control notification handler code here
 if(b_finish)  {
		if(UpdateData()==FALSE)  return;
		if(m_delnum<0||m_delnum>1000)  {
			MessageBox("请在0-999之间选择删除值");
			return;
		}

        DPARAMs ptp;
		ptp.num=m_delnum;
		ptp.sel=0;	
		if(!B_Tree)  NewNode(&B_Tree);
		m_randtree.EnableWindow(FALSE);
	    m_crandnum.EnableWindow(FALSE);
	    m_cBM.EnableWindow(FALSE);
		m_f_insert.EnableWindow(FALSE);
	    m_cdelnum.EnableWindow(FALSE);
	    m_cinsnum.EnableWindow(FALSE);
		m_delball.EnableWindow(FALSE);
		m_setit.EnableWindow(FALSE);
		m_travorder.EnableWindow(FALSE);

		CWinThread* pThread=AfxBeginThread(ThreadFunc,&ptp,
			THREAD_PRIORITY_NORMAL,0,CREATE_SUSPENDED);
//		::DuplicateHandle(GetCurrentProcess(),pThread->m_hThread,
//			GetCurrentProcess(),&m_handle,0,FALSE,DUPLICATE_SAME_ACCESS);
		pThread->ResumeThread();
		::Sleep(10);
		//m_ev.SetEvent();
		m_f_delete.SetWindowText("继续");

	}
	else  {
		m_ev.SetEvent();

	}
	
}

void CBTreeDemoDlg::OnDelAll() 
{
	EreaseMdc();
    F_DelAll(&B_Tree);
	MdcDsp();
	// TODO: Add your control notification handler code here
	
}

void CBTreeDemoDlg::post_order(BTree T)  {
    int i;
	char stmp[100];
	if(T)  {  
		for(i=0;i<=T->keynum;i++)  {
			post_order(T->ptr[i]);
			if(i<T->keynum)   out_p+=itoa(T->key[i+1],stmp,10),out_p+=",";
		}
	}
}

void CBTreeDemoDlg::OnTravOrder() 
{
	out_p="中序:";
	// TODO: Add your control notification handler code here
    post_order(B_Tree);
	//mdc.
		
	CDC *dc=GetDC();
	mdc.TextOut(10,10,out_p);
	MdcDsp();

	// TODO: Add your control notification handler code here
	
}

void CBTreeDemoDlg::OnSetIt() 
{
	// TODO: Add your control notification handler code here
	if(UpdateData()==FALSE)  return;
	if(m_BM<3||m_BM>8)  {
		MessageBox("B-树最大阶数请在3到8之间输入");
		return ;
	}
    B_M=m_BM;
	if(B_Tree)  {
		F_DelAll(&B_Tree);
	}
	EreaseMdc();
	MdcDsp();
	
}