1
Thi cuoi ky`... 2009-12-21, 16:17
Kem_Skillno1_group
 |  | |
 | ||
 |  |
thieu cau 4: ba con bo? vao
- Code:
/* Ho va Ten:Le Thi Vinh Quyen
MSSV:0866112
Phong may:3
Giao vien:Vu Quoc Hoang
*/
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<math.h>
struct NODE
{
int key;
NODE *left;
NODE *right;
};
struct TREE
{
NODE *root;
};
void init(TREE &t)
{
t.root=NULL;
}
NODE *getnode(int key)
{
NODE *p=new NODE;
if(p!=NULL)
{
p->key=key;
p->left=p->right=NULL;
}
else
return NULL;
}
void insertDQ(NODE *&r, int key)
{
if(r==NULL)
r=getnode(key);
else if(r->key > key)
insertDQ(r->left,key);
else if(r->key < key)
insertDQ(r->right,key);
else
return;
}
void insert(TREE &t,int key)
{
insertDQ(t.root,key);
}
void Nhap(TREE &t)
{
int n;
printf("\n Nhap vao so nut cua cay:");
scanf("%d",&n);
init(t);
for(int i=0;i<n;i++)
{
int x;
printf("\n Nhap vao gia tri x:");
scanf("%d",&x);
insert(t,x);
}
}
void XuatDQ(NODE *r)
{
if(r==NULL)
return ;
XuatDQ(r->left);
printf("%4d",r->key);
XuatDQ(r->right);
}
void Xuat(TREE t)
{
XuatDQ(t.root);
}
// cau 2: Xuat ra cac nut co gia tri le va theo chieu tang dan
void LeDQ (NODE *r)
{
if (r==NULL)
return;
LeDQ (r->left);
if (r->key%2!=0)
printf ("%4d",r->key);
LeDQ (r->right);
}
void XuatLe (TREE t)
{
LeDQ (t.root);
}
// Tinh do cao cua tung nhanh
int Docao(NODE *&r)
{
if(r==NULL)
return 0;
if(r->left==NULL && r->right==NULL)
{
return 0;
}
int a=Docao(r->left);
int b=Docao(r->right);
return 1+((a>b)?a:b);
}
// cau 3: Kiem tra cay co phai la "Kha can bang" hay khong
int kiemtracanbang(NODE *r)
{
int flag=1;
if(!r)
return 0;
int k=Docao(r->left) - Docao(r->right);
if(k<-1||k>1)
flag=0;
kiemtracanbang(r->left);
kiemtracanbang(r->right);
return flag;
}
int Kiemtra(TREE t)
{
return kiemtracanbang(t.root);
}
void main()
{
TREE t;
init(t);
printf("\n Cau 1: ... cay nhi phan tim kiem:");
Nhap(t);
printf("\n Cay nhi phan tim kiem duoc duyet LNR theo thu tu tang dan:");
Xuat(t);
printf("\n Cac nut co gia tri le va sap theo chieu tang dan:");
XuatLe(t);
int kq=Kiemtra (t);
if (kq==0)
printf ("\nCay da cho la khong kha can bang");
else
printf ("\nCay da cho la kha can bang");
}
Chuc may man!
