Hàm liên quan đến cây nhị phân tìm kiếm
int mx(int a,int b)
{
if(a>=b) return a;
else return b;
}
int chieucao(TREE T)
{
int n;
if(T==NULL) return 0;
if(T->pleft==NULL&&T->pright==NULL)
return 1;
n=1+mx(chieucao(T->pleft),chieucao(T->pright));
return n;
}
int sonut(TREE T)
{
int n;
if(T==NULL) return 0;
if(T->pleft==NULL&&T->pright==NULL) return 1;
return 1+sonut(T->pleft)+sonut( T->pright);
}
TNODE *timnut(TREE T,int x)
{
TNODE *p=T;
while(p!=NULL)
{
if(x==p->k) return p;
else
{
if(x<p->k) p=p->pleft;
else p=p->pright;
}
}
return NULL;
}
int ktnt(int x)
{
int i=2;
if(x<2) return 0;
for(i=2;i<=sqrt(x);i++)
if(x%i==0) return 0;
return 1;
}
int demnt(TREE &T)
{
int n;
if(T==NULL) return 0;
if(ktnt(T->k)==1)
{
n=1+demnt(T->pleft)+demnt(T->pright);
}
if(ktnt(T->k)==0)
{
n=demnt(T->pleft)+demnt(T->pright);
}
return n;
}
int timduong(TREE T,int x)
{
int n;
n=1;
while(T!=NULL)
{
if(T->k==x) return n;
else
{
if(T->k>x)
{
n=n+1;
T=T->pleft;
}
else
{
n=n+1;
T=T->pright;
}
}
}
return 0;
}
void sosanh(TREE T,int x,int y)
{
if(timduong(T,x)!=0&&timduong(T,y)!=0)
{
if(timduong(T,x)==timduong(T,y))
printf("
2 nut cung muc %d.",timduong(T,x));
else
printf("
2 nut khac muc.");
}
if(timduong(T,x)==0||timduong(T,y)==0)
printf("
gia tri nhap khong hop le.");
}
TNODE *timnutcha(TREE T,int x)
{
TNODE *t;
t=timnut(T,x);
if(t==NULL) return NULL;
if(t!=NULL)
{
if(T->k==x) return NULL;
else
{
while(T!=NULL)
{
if(T->pleft==t||T->pright==t) return T;
else
{
if(T->k>x) T=T->pleft;
else T=T->pright;
}
}
}
}
}
void timthemang(TREE &p,TREE &q)
{
if(q->pleft!=NULL)
{
timthemang(p,q->pleft);
}
else
{
p->k=q->k;
p=q;
q=q->pright;
}
}
void del(TREE &T,int x)
{
if(T==NULL) printf("Cay rong.");
if(timnut(T,x)!=NULL){
if(T->k>x)return del(T->pleft,x);
if(T->k<x)return del(T->pright,x);
else
{
TNODE *p=T;
if(T->pleft==NULL) T=T->pright;
else
{
if(T->pright==NULL) T=T->pleft;
else
{
TNODE *q=T->pright;
timthemang(p,q);
delete p;
}
}
}
}
else printf("Khong co nut can xoa.
");
}
void xoanutnt(TREE &T)
{
if(T==NULL) ;
if(T!=NULL)
{
xoanutnt(T->pleft);
xoanutnt(T->pright);
if(ktnt(T->k)==1)
{
del(T,T->k);
}
}
}
void huycay(TREE &T)
{
if(T==NULL);
if(T!=NULL)
{
huycay(T->pleft);
huycay(T->pright);
del(T,T->k);
}
}
int demchan(TREE T)
{
int n;
if(T==NULL) return 0;
if(T->k%2==0)
{
n=1+demchan(T->pleft)+demchan(T->pright);
printf("
%d" ,T->k);
}
if(T->k%2!=0)
{
n=demchan(T->pleft)+demchan(T->pright);
}
return n;
}
int demle(TREE T)
{
int n;
if(T==NULL) return 0;
if(T->k%2!=0)
{
n=1+demle(T->pleft)+demle(T->pright);
printf("
%d" ,T->k);
}
if(T->k%2==0)
{
n=demle(T->pleft)+demle(T->pright);
}
return n;
}
TNODE *rootmin(TREE T)
{
TNODE *min;
if(T==NULL) return NULL;
else
{
min=T;
while(T->pleft!=NULL)
{
T=T->pleft;
min=T;
}
return min;
}
}
TNODE *rootmax(TREE T)
{
TNODE *max;
if(T==NULL) return NULL;
else
{
max=T;
while(T->pright!=NULL)
{
T=T->pright;
max=T;
}
return max;
}
}
int nutla(TREE T)
{
if(T==NULL) return 0;
else
{
if(T->pleft==NULL&&T->pright==NULL)
{
printf("
%d",T->k);
return 1;
}
else
return nutla(T->pleft)+nutla(T->pright);
}
}
int nutnhiphan(TREE T)
{
if(T==NULL) return 0;
else
{
if((T->pleft==NULL&&T->pright!=NULL)||(T->pright==NULL&&T->pleft!=NULL))
{
printf("
%d",T->k);
return 1+nutnhiphan(T->pleft)+nutnhiphan(T->pright);
}
else
return nutnhiphan(T->pleft)+nutnhiphan(T->pright);
}
}
int nuttoanphan(TREE T)
{
if(T==NULL) return 0;
else
{
if(T->pleft!=NULL&&T->pright!=NULL)
{
printf("
%d",T->k);
return 1+nuttoanphan(T->pleft)+nuttoanphan(T->pright);
}
else
return nuttoanphan(T->pleft)+nuttoanphan(T->pright);
}
}
int nutnhohon(TREE T,int x)
{
if(T==NULL) return 0;
else
{
if(T->k<x)
{
printf("
%d",T->k);
return 1+nutnhohon(T->pleft,x)+nutnhohon(T->pright,x);
}
else
return nutnhohon(T->pleft,x)+nutnhohon(T->pright,x);
}
}
int nutlonhon(TREE T,int x)
{
if(T==NULL) return 0;
else
{
if(T->k>x)
{
printf("
%d",T->k);
return 1+nutlonhon(T->pleft,x)+nutlonhon(T->pright,x);
}
else
return nutlonhon(T->pleft,x)+nutlonhon(T->pright,x);
}
}
int xrooty(TREE T,int x,int y)
{
if(T==NULL) return 0;
else
{
if(T->k>x&&T->k<y)
{
printf("
%d",T->k);
return 1+xrooty(T->pleft,x,y)+xrooty(T->pright,x,y);
}
else
return xrooty(T->pleft,x,y)+xrooty(T->pright,x,y);
}
}
Bạn đang đọc truyện trên: Truyen4U.Com