Đồ Án_CTDL1_Nhóm 3_(Nhớ-Hùng-Trang_DH10ST)_Đề Tài 4: Cây Tìm Kiếm Nhị Phân
Nhóm 3: Thành viên:
1. Nguyễn Văn Nhớ (Nhóm trưởng); MSSV: DST091291; Lớp: DH10ST
2. Huỳnh Thanh Hùng; MSSV: DST091291; Lớp: DH10ST
3. Nguyễn Thị Huyền Trang; MSSV: DST091291; Lớp: DH10ST
Đề Tài 4: Cây Tim Kiếm Nhị Phân
1. Tạo lập cây (chèn các nút vào cây)
2. Xác định tổng số nút trên cây
3. Xác định số nút lá trên cây
4. Xác định số nút trung gian trên cây
5. Xác định số nút trong từng mức
6. Xác định nút nhỏ nhất của cây
7. Xác định nút lớn nhất của cây
8. Xóa một nút khỏi cây
9. Duyệt cây theo kiểu NLR (tiền tự)
10. Duyệt cây theo kiểu LRN (hậu tự)
11. Duyệt cây theo kiểu LNR (trung tự)
12.Duyệt cây theo từng mức từ trái qua phải (nút gốc, các
nút ở mức 1, các nút ở mức 2,….,các nút lá)
13. Tìm kiếm trên cây
14. Xóa toàn bộ cây
Bảng phân công đồ án:
Nguyễn Văn Nhớ (A)
Duyệt cây theo kiểu NLR,LRN,LNR, từ trái qua phải, tiềm
kiếm một nút trên cây, xóa toàn bộ cây, viết báo cáo, tổng
hợp Code
Huỳnh Thanh Hùng (B)
Xác định nút nhỏ nhất cảu cây, xác định nút lớn nhất của
cây, xóa một nút khỏi cây
Nguyễn Thi Huyền Trang (C)
Tạo lập cây, xác định tông số nút trên cây, xác định số nút

tam->left=NULL;
tam->right=NULL;
if((*T)==NULL)
(*T)=tam;
else
chen(tam,T);
2. Xác định tổng số nút trên cây:
- B1: Nếu cây nhị phân khác rỗng thì tổng số nút trên cây =1 + tổng số nút ở cây trái + tổng số nút ở
cây phải
Code:
int dem = 0;
//===========ham xu ly================
int dem_phu(Tree T)
{
if (T != NULL)
{
dem++;
if (T->left != NULL)
dem_phu(T->left);
if (T->right != NULL)
dem_phu(T->right);
}
return dem;
}
//=========ham the hien===========
void tong_so_nut(Tree T)
{
dem = 0;
if (T)
{

{
dem_la = 0;
if (T)
{
dem_nut_la_phu(T);
printf ("\nSo nut la tren cay : %d ",dem_la);
dem_la = 0;
}
else
printf ("\nCay rong!");
}
4. Đếm tổng số nút trung giang:
- B1: Xác định cây nhị phân khác rỗng:
- B2: Nếu nút bất kỳ hoặc có nhánh trái hoặc có nhánh phải thì được xem là nút trung gian.
Code:
int dem_trung_gian = 0 ;
//========ham xu ly=====================
void dem_nut_trung_gian_phu(Tree T)
{
if (T)
{
3/10
Đồ Án_CTDL1_Nhóm 3_(Nhớ-Hùng-Trang_DH10ST)_Đề Tài 4: Cây Tìm Kiếm Nhị Phân
if (T->left != NULL || T->right != NULL)
dem_trung_gian++ ;
if (T->left != NULL)
dem_nut_trung_gian_phu(T->left);
if (T->right != NULL)
dem_nut_trung_gian_phu(T->right);
}

muc ;
}
//===========ham the hien================
void tong_so_nut_theo_muc (Tree T)
{
if (T)
{
muc = -1;
printf ("\nSo nut tren tung muc : ");
dem_nut_theo_muc_phu (T);
for (int i=0 ; i<10 ; i++)
if (a[i] != 0)
printf ("\n\tMuc %d : %d",i,a[i]);
for (i=0 ; i<10 ; i++)
4/10
Đồ Án_CTDL1_Nhóm 3_(Nhớ-Hùng-Trang_DH10ST)_Đề Tài 4: Cây Tìm Kiếm Nhị Phân
a[i] = 0;
muc = -1;
}
else
printf ("\nCay rong!\n");
}
6. Xác định nút nhỏ nhất của cây:
- B1: Nút nhỏ nhất chính là nút nằm bên trái nhất của cây
- B2: Cho T->left đến khi T->left =NULL thì T chính là giá trị nhỏ nhất của cây.
Code:
Node* min_nhanh_phai_phu (Tree T)// tree o day la T->right
{
if (T)
if (T->left == NULL)

return NULL;
}
//========ham the hien=============
void min_nhanh_trai (Tree T)
{
if (T)
5/10
Đồ Án_CTDL1_Nhóm 3_(Nhớ-Hùng-Trang_DH10ST)_Đề Tài 4: Cây Tìm Kiếm Nhị Phân
if (T->left == NULL)
{
printf ("\nCay khong co nhanh trai!\n");
return;
}
else
{
printf ("\nNut nho nhat tren Cay (nhanh trai) :
%d\n",min_nhanh_trai_phu(T->left)->Data);
}
else
printf ("\nCay rong!\n");
}
7. Xác định nút lớn nhất của cây:
- B1: Nút lớn nhất chính là nút nằm bên phải nhất của cây
- B2: Cho T->right đến khi T->right =NULL thì T chính là giá trị nhỏ nhất của cây.
Code:
Node* max_nhanh_trai_phu (Tree T)// tree o day la T->left
{
if (T)
if (T->right == NULL)
return (T);

return (T);
else
return (max_nhanh_phai_phu (T->right));
return NULL;
}
//========ham the hien===============
void max_nhanh_phai (Tree T)
{
if (T)
if (T->right == NULL)
{
printf ("\nCay khong co nhanh phai!\n");
return;
}
else
{
printf ("\nNut lon nhat Cay (tren nhanh phai) :
%d\n",max_nhanh_phai_phu(T->right)->Data);
}
else
printf ("\nCay rong!\n");
}
8. Xóa một nút khỏi cây:
VD: Ta có cây nhị phân như
hình vẽ bên: gồm có các nút.
-
Nếu xóa nút có giá trị (3) thì giá trị (2) sẽ
dời tới chỗ của giá trị (3).
7/10
Đồ Án_CTDL1_Nhóm 3_(Nhớ-Hùng-Trang_DH10ST)_Đề Tài 4: Cây Tìm Kiếm Nhị Phân

return (tim_nut (T->right,tam));
else
return (tim_nut (T->left,tam));
}
return NULL;
}
//===========ham the hien==================
void tim_kiem (Tree T)
{
if (T)
{
int x;
Node* tam;
printf ("\nNhap gia tri can tim : ");
scanf ("%d",&x);
tam=tim_nut (T,x);
if (tam)
printf ("\nTrong Cay co gia tri: %d",tam->Data);
else
printf ("\n Khong ton tai nut nay!\n");
}
else
printf ("\n Cay rong! ");
}
14. Xóa toàn bộ cây:
- Gán cho cây gia trị NULL. T->NULL;

Đánh giá Đồ Án:
9/10
Đồ Án_CTDL1_Nhóm 3_(Nhớ-Hùng-Trang_DH10ST)_Đề Tài 4: Cây Tìm Kiếm Nhị Phân