Giáo trình Cấu trúc dữ liệu (Bản đẹp)

của 1 cây. 
Hình 4. 3 Biểu diễn cây bằng mảng các nút cha 
Với phương pháp biểu diễn này, ta có thể dễ dàng tìm nút cha của 1 nút 
trên cây, nhưng nhược điểm là việc tìm nút con của 1 nút khá phức tạp, đăc biệt 
là tìm tất cả các nút con của một nút sẽ tốn rất nhiều công sức. Ngoài ra, với 
cách biểu diễn này, ta cũng không ấn định được thứ tự của các nút con. 
2.1.2. Cài đặt cây thông qua danh sách các nút con 
Cây có thể được cài đặt một cách hiệu quả hơn bằng cách tạo ra 1 danh 
sách các nút con cho mỗi nút của cây. Tuy nhiên, do số nút con của 1 nút là 
không xác định trước, do vậy nên dùng danh sách liên kết để biểu thị danh sách 
các nút con. 
Biểu diễn cây theo danh sách các nút con như sau: 
1 2 3 4 5 6 7 8 9 
0 1 2 3 3 1 1 7 7 
1 2 3 4 5 6 7 8 9 
0 1 2 3 3 1 1 7 7 
Chương 4: Cây 
KHOA CÔNG NGHỆ THÔNG TIN Trang 61 
Hình 4. 4 Cài đặt cây bằng danh sách các nút con 
Biểu diễn cây theo phương pháp này cho phép duyệt cây dễ dàng và hợp 
logic hơn. Xuất phát từ gốc, ta tìm các nút con của gốc, rồi tìm các nút con của 
các nút vừa tìm được, v.v. cho tới khi đến các nút lá. 
2.2. Phép duyệt 
Duyệt cây là hành động duyệt qua tất cả các nút của một cây theo một trình 
tự nào đó. Trong quá trình duyệt, tại mỗi nút ta có thể tiến hành một thao tác xử lý 
nào đó. Đối với các danh sách liên kết, việc duyệt qua danh sách đơn giản là đi từ nút 
đầu, qua các liên kết và tới nút cuối cùng. Tuy nhiên, đối với cây, mỗi nút có thể có 
nhiều liên kết tới các nút con, vì vậy thứ tự duyệt qua các nút sẽ cho các phương pháp 
duyệt cây theo trình tự khác nhau. 
Nhìn chung, có 3 trình tự duyệt cây phổ biến nhất, đó là: 
 - Duyệt cây theo thứ tự trước. 
- Duyệt cây theo thứ tự giữa. 
- Duyệt cây theo thứ tự sau. 
a) Duyệt cây theo thứ tự trước. 
Giả sử ta có một cây T với gốc n và k cây con là T1, T2, ..., Tk 
Chương 4: Cây 
KHOA CÔNG NGHỆ THÔNG TIN Trang 62 
Hình 4. 5 Hình ảnh một cây mô tả phép duyệt 
Quá trình duyệt cây thứ tự trước được tiến hành theo trình tự như sau: 
- Thăm nút gốc n. 
- Thăm cây con T1 theo phương pháp thứ tự trước. 
- Thăm cây con T2 theo phương pháp thứ tự trước. 
- ... 
- Thăm cây con Tk theo phương pháp thứ tự trước. 
Ví dụ 1: trình tự thăm cây theo thứ tự trước như sau: 
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 
b) Duyệt cây thứ tự giữa 
Quá trình duyệt cây thứ tự giữa được tiến hành theo trình tự như sau: 
- Thăm cây con T1 theo phương pháp thứ tự giữa. 
- Thăm nút gốc n. 
- Thăm cây con T2 theo phương pháp thứ tự giữa. 
 ... 
- Thăm cây con Tk theo phương pháp thứ tự giữa. 
Ví dụ 2: Trình tự thăm cây theo thứ tự giữa như sau: 
Chương 4: Cây 
KHOA CÔNG NGHỆ THÔNG TIN Trang 63 
4 -> 3 -> 5 -> 2 -> 1 -> 6 -> 8 -> 7 -> 9 
c) Duyệt cây thứ tự sau 
Quá trình duyệt cây thứ tự sau được tiến hành theo trình tự như sau: 
- Thăm cây con T1 theo phương pháp thứ tự sau. 
- Thăm cây con T2 theo phương pháp thứ tự sau. 
- ... 
- Thăm cây con Tk theo phương pháp thứ tự sau. 
- Thăm nút gốc n. 
Ví dụ 3: Trình tự thăm cây theo thứ tự sau như sau: 
4 -> 5 -> 3 -> 2 -> 6 -> 8 -> 9 -> 7 -> 1 
2.3.Cây nhị phân 
Định nghĩa: 
- Cây nhị phân là cây mà mỗi nút có tối đa 2 cây con. 
- Trong thực tế thường gặp các cấu trúc có dạng cây nhị phân. Một cây tổng quát có 
thể biểu diễn thông qua cây nhị phân. 
Chương 4: Cây 
KHOA CÔNG NGHỆ THÔNG TIN Trang 64 
Hình 4. 6 Hình ảnh một cây nhị phân 
Ví dụ 1: Cây nhị phân dùng để biểu diễn một biểu thức toán học: 
((((3 x (1 + (4 + 6))) + (2 + 8)) x 5) + (4 x (7 + 2))) 
Một số tính chất của cây nhị phân: 
- Số nút nằm ở mức i 
- Số nút lá 2h-1, với h là chiều cao của cây. 
- Chiều cao của cây h log2(số nút trong cây). 
- Số nút trong cây 2h-1. 
Hình 4. 7 Hình ảnh mô tả tính chất một cây nhị phân 
Cây con trái 
Cây con phải 
Chương 4: Cây 
KHOA CÔNG NGHỆ THÔNG TIN Trang 65 
Biểu diễn cây nhị phân T: 
Cây nhị phân là một cấu trúc bao gồm các phần tử (nút) được kết nối với nhau 
theo quan hệ “cha-con” với mỗi cha có tối đa 2 con. Để biểu diễn cây nhị phân ta chọn 
phương pháp cấp phát liên kết. Ứng với một nút, ta sử dụng một biến động lưu trữ các 
thông tin sau: 
- Thông tin lưu trữ tại nút. 
- Địa chỉ nút gốc của cây con trái trong bộ nhớ. 
- Địa chỉ nút gốc của cây con phải trong bộ nhớ. 
Để đơn giản, ta khai báo cấu trúc dữ liệu như sau : 
 typedef struct NODE 
 { 
 int data; 
 NODE* left; 
 NODE* right; 
 }; 
 typedef struct NODE* TREE; 
 TREE root; 
void CreateTree(TREE &root) 
{ 
 int x; 
 printf(“\nGia tri node :”); 
 x=toupper(getch()); 
 if(isspace(x)==0) 
 { 
 root=(node*)malloc(sizeof(node)); 
 root ->data=x; 
 printf(“\nCon trai cua %c (ENTER NULL)”,x); 
 CreateTree(root->left); 
 printf(“\nCon phai cua %c (ENTER NULL)”,x); 
Chương 4: Cây 
KHOA CÔNG NGHỆ THÔNG TIN Trang 66 
 CreateTree(root->right); 
 } 
 else root=NULL; 
} 
Duyệt cây nhị phân 
Có 3 kiểu duyệt chính có thể áp dụng trên cây nhị phân: 
- Duyệt theo thứ tự trước (NLR) 
- Duyệt theo thứ tự giữa (LNR) 
- Duyệt theo thứ tựï sau (LRN). 
Tên của 3 kiểu duyệt này được đặt dựa trên trình tự của việc thăm nút gốc so với việc 
thăm 2 cây con. 
Duyệt theo thứ tự trước (Node-Left-Right) 
Kiểu duyệt này trước tiên thăm nút gốc sau đó thăm các nút của cây con trái rồi đến 
cây con phải. 
Thủ tục duyệt có thể trình bày đơn giản như sau: 
Void NLR(TREE root) 
{ 
if (Root != NULL) 
{ 
;//Xử lý tương ứng theo nhu cầu 
NLR(root->left); 
NLR(root->right); 
} 
} 
Chương 4: Cây 
KHOA CÔNG NGHỆ THÔNG TIN Trang 67 
Ví dụ 2: Cho cây nhị phân T, duyệt cây theo thứ tự NLR? 
Kết quả: A, B, D, H, I, N, E, J, O, K, C, F, L, P, G, M 
Duyệt theo thứ tự giữa (Left - Node -Right) 
Kiểu duyệt này trước tiên thăm các nút của cây con trái sau đó thăm nút gốc rồi đến 
cây con phải. 
Thủ tục duyệt có thể trình bày đơn giản như sau: 
void LNR(TREE root) 
{ 
if (root != NULL) 
{ 
 LNR(root->left); 
 ; //Xử lý tương ứng theo nhu cầu 
 LNR(root->right); 
} 
} 
Ví dụ 3: Cho cây nhị phân T, duyệt cây theo thứ tự LNR? 
Chương 4: Cây 
KHOA CÔNG NGHỆ THÔNG TIN Trang 68 
Kết quả: H, D, N, I, B, J, O, E, K, A, F, P, L, C, M, G 
Duyệt theo thứ tự giữa (Left - Node -Right) 
- Kiểu duyệt này trước tiên thăm các nút của cây con trái sau đó thăm đến cây con phải 
rồi cuối cùng mới thăm nút gốc. 
Thủ tục duyệt có thể trình bày đơn giản như sau: 
void LRN(TREE root) 
{ 
if (root != NULL) 
{ 
LRN(root->left); 
LRN(root->right); 
; //Xử lý tương ứng theo nhu cầu 
} 
} 
Ví dụ 4: Cho cây nhị phân T, duyệt cây theo thứ tự LRN? 
Kết quả: H, N, I, D, O, J, K, E, B, P, L, F, M, G, C, A 
Ví dụ 5: Tính toán giá trị của biểu thức dựa trên cây biểu thức (duyệt cây theo thứ tự 
LRN)? 
Chương 4: Cây 
KHOA CÔNG NGHỆ THÔNG TIN Trang 69 
(3+1) x 3/ (9-5+2) - (3 x (7 - 4) + 6) = -13 
Chương 4: Cây 
KHOA CÔNG NGHỆ THÔNG TIN Trang 70 
DANH MỤC HÌNH ẢNH CHƯƠNG 4 
Hình 4. 1 Hình ảnh một Cây mô tả thứ tự đọc một quyển sách .................................... 59 
Hình 4. 2 Hình ảnh tính chấy Cây ................................................................................. 59 
Hình 4. 3 Biểu diễn cây bằng mảng các nút cha ........................................................... 60 
Hình 4. 4 Cài đặt cây bằng danh sách các nút con ........................................................ 61 
Hình 4. 5 Hình ảnh một cây mô tả phép duyệt .............................................................. 62 
Hình 4. 6 Hình ảnh một cây nhị phân ............................................................................ 64 
Hình 4. 7 Hình ảnh mô tả tính chất một cây nhị phân ................................................... 64 
Chương 4: Cây 
KHOA CÔNG NGHỆ THÔNG TIN Trang 71 
CÂU HỎI VÀ BÀI TẬP 
1. Cho các hình vẽ sau: hãy chỉ hình vẽ nào là cây, hình vẽ nào không là cây và 
giải thích? 
(a) 
(b) 
(c) 
(d) 
2. Với cây nhị phân bên dưới, hãy biểu thị cây theo phương pháp dùng mảng và 
danh sách liên kết. 
3. Cho cây nhị phân T chứa các số nguyên, 
a. Duyệt cây theo thứ tự NLR? 
7 
3 36 
1 6 15 40 
23 4 
Chương 4: Cây 
KHOA CÔNG NGHỆ THÔNG TIN Trang 72 
b. Duyệt cây theo thứ tự LNR? 
c. Duyệt cây theo thứ tự LRN? 
3. Hãy vẽ cây nhị phân tìm kiếm T biết rằng khi duyệt cây T theo thứ tự Node – Left - 
Right thì được dãy sau: 40, 5, 35, 15, 13, 16, 45, 56, 48, 47, 49? 
4. Hãy vẽ cây nhị phân tìm kiếm T biết rằng khi duyệt cây T theo thứ tự Left - Right - 
Node thì được dãy sau: 3, 8, 11, 6, 19, 37, 25, 21, 15, 12? 
5. Hãy vẽ cây nhị phân tìm kiếm T biết rằng khi duyệt cây T theo thứ tự Node - Left-
Right thì được dãy sau: 12, 6, 3, 11, 8, 15, 21, 19, 25, 37? 
6. Viết chương trình tạo , tra cứu và sữa chữa tử điển Anh – Việt. 
 73 
TÀI LIỆU THAM KHẢO 
TT Tên tác giả Tên sách – giáo trình NXB Năm XB 
1 
PGS.TS. Hàn Viết Thuận 
ThS. Nguyễn Anh Phương 
Cấu trúc dữ liệu và 
giải thuật 
Đại Học Kinh Tế 
Quốc Dân 
2018 
2 Robert Sedgewick Algorithms 
Bản dịch tiếng 
Việt, NXB Khoa 
học và Kỹ thuật, 
1994 
 KHOA CÔNG NGHỆ THÔNG TIN Trang 74 
PHỤ LỤC MÃ NGUỒN THAM KHẢO 
CHƯƠNG TRÌNH SẮP XẾP CHÈN 
#include 
#include 
#include 
#include 
#include 
int *a, n, m; 
void Init(); 
void In(); 
void Init(){ 
int i; 
printf("\n Tao lap day so:"); 
for (i=0; i<n;i++){ 
a[i]=random(100); 
printf("%5d",a[i]); 
} 
delay(1000);} 
void insertion_sort(){ 
int i, j, k, temp; 
for (i = 1; i< n; i++){ temp = a[i]; j=i-1; 
while ((a[j] > temp)&&(j>=0)) { 
a[j+1]=a[j]; 
j--; 
} 
a[j+1]=temp; 
} 
} 
void In(){ 
register int i; for(i=0;i<n;i++) 
 KHOA CÔNG NGHỆ THÔNG TIN Trang 75 
printf("%5d",a[i]); 
printf("\n"); 
getch(); 
} 
void main(void){ 
clrscr(); 
printf("\n Nhap n="); scanf("%d",&n); 
a=(int *) malloc(n*sizeof(int)); Init(); 
insertion_sort(); 
printf("\n\n Day da sap: "); In(); 
free(a); 
} 
CHƯƠNG TRÌNH SẮP XẾP NỔI BỌT 
#include 
#include 
#include 
#include 
#include 
int *a, n, m; 
void Init(); 
void In(); 
void Init(){ 
int i; 
printf("\n Tao lap day so:"); 
for (i=0; i<n;i++) 
{ 
a[i]=random(100); 
printf("%5d",a[i]); 
} 
delay(1000); 
 KHOA CÔNG NGHỆ THÔNG TIN Trang 76 
} 
void bubble_sort(){ 
int i, j, temp, no_exchange; 
i = 1; 
do{ 
no_exchange = 1; 
for (j=n-1; j >= i; j--){ 
if (a[j-1] > a[j]){ temp=a[j-1]; a[j-1]=a[j]; 
a[j]=temp; no_exchange = 0; 
} 
} 
i++; 
} while (!no_exchange && (i < n-1)); 
} 
void In(){ 
register int i; 
for(i=0;i<n;i++) 
printf("%5d",a[i]); 
printf("\n"); 
getch();} 
void main(void){ 
clrscr(); 
printf("\n Nhap n="); 
scanf("%d",&n); 
a=(int *) malloc(n*sizeof(int)); 
Init(); 
bubble_sort(); 
printf("\n\n Day da sap: "); 
In(); 
free(a); 
 KHOA CÔNG NGHỆ THÔNG TIN Trang 77 
} 
DANH SÁCH LIÊN KẾT ĐƠN 
#include 
#include 
struct node{ 
int item; 
struct node *next; 
}; 
typedef struct node *listnode; 
void Insert_Begin(listnode *p, int x); 
void Insert_End(listnode *p, int x); 
void PrintList(listnode p); 
void Insert_Begin(listnode *p, int x){ 
listnode q; 
q = (listnode)malloc(sizeof(struct node)); 
q-> item = x; 
q-> next = *p; 
*p = q; 
printf("\nThem nut vao dau danh sach thanh cong, bam phim bat 
ky de tiep tuc!"); 
getch(); 
} 
void Insert_End(listnode *p, int x){ 
listnode q, r; 
q = (listnode)malloc(sizeof(struct node)); 
q-> item = x; 
q->next=NULL; 
if (*p==NULL) 
*p=q; 
else{ 
 KHOA CÔNG NGHỆ THÔNG TIN Trang 78 
r = *p; 
while (r->next != NULL) 
r = r->next; 
r->next = q; 
} 
printf("\nThem nut vao cuoi danh sach thanh cong, bam phim bat 
ky de tiep tuc!"); 
getch(); 
} 
void Insert_Middle(listnode *p, int position, int x){ 
int count=1, found=0; 
listnode q, r; r = *p; 
while ((r != NULL)&&(found==0)){ 
if (count == position){ 
q = (listnode)malloc(sizeof(struct node)); 
q-> item = x; 
q-> next = r-> next; 
r-> next = q; found = 1; 
} 
count ++; 
r = r-> next; 
} 
if (found==0) 
printf("Khong tim thay vi tri can chen "); 
else 
printf("\nThem nut vao vi tri %d thanh cong, bam phim 
bat ky de tiep tuc!", position); 
getch(); 
} 
void Remove_Begin(listnode *p){ 
 KHOA CÔNG NGHỆ THÔNG TIN Trang 79 
listnode q; 
if (*p == NULL) return; 
q = *p; 
*p = (*p)-> next; 
q-> next = NULL; 
free(q); 
printf("\nXoa nut dau danh sach thanh cong, bam phim bat ky 
de tiep tuc!"); 
getch(); 
} 
void Remove_End(listnode *p){ 
listnode q, r; 
if (*p == NULL) 
return; 
if ((*p)-> next == NULL) 
{ 
Remove_Begin(*p); 
return; 
} 
r = *p; 
while (r-> next != NULL) 
{ 
q = r; 
r = r-> next; 
} 
q-> next = NULL; 
free(r); 
printf("\nXoa nut cuoi danh sach thanh cong, bam phim bat ky de 
tiep tuc!"); 
getch(); 
 KHOA CÔNG NGHỆ THÔNG TIN Trang 80 
} 
void Remove_Middle(listnode *p, int position){ 
int count=1, 
found=0; 
listnode q, r; 
r = *p; 
while ((r != NULL)&&(found==0)){ 
if (count == position){ 
q = r-> next; 
r-> next = q-> next; 
q-> next = NULL; 
free (q); 
found = 1; 
} 
count ++; 
r = r-> next; 
} 
if (found==0) 
printf("Khong tim thay vi tri can xoa"); 
else 
printf("\nXoa nut o vi tri %d thanh cong, bam phim bat ky 
de tiep tuc!", position); 
getch(); 
} 
void PrintList(listnode p){ 
listnode q; q=p; 
while (q!=NULL){ 
printf("%d ",q->item); 
q=q->next; 
} 
 KHOA CÔNG NGHỆ THÔNG TIN Trang 81 
printf("\nBam phim bat ky de tiep tuc"); 
getch(); 
} 
void main(void){ 
listnode *p; 
int x, chon, vitri; 
*p=NULL; 
do{ 
clrscr(); 
printf("CHUWONG TRINH MINH HOA SU DUNG 
DANH SACH LIEN KET DON\n\n"); 
printf("Moi ban chon chuc nang:\n"); 
printf(" 1. Khoi tao danh sach\n"); 
printf(" 2. Them phan tu vao dau danh sach\n"); 
printf(" 3. Them phan tu vao cuoi danh sach\n"); 
printf(" 4. Them phan tu va giua danh sach\n"); 
printf(" 5. Xoa phan tu o dau danh sach\n"); 
printf(" 6. Xoa phan tu o cuoi danh sach\n"); 
printf("7 xoa phan tu o giua danh sach\n"); 
printf(" 8. In danh sach\n"); 
printf(" 9 Thoat khoi chuong trinh\n"); 
printf("Lua chon: "); 
scanf("%d",&chon); 
switch (chon) { 
case 1: 
*p=NULL; 
break; 
case 2: 
clrscr(); 
printf("Cho x= "); 
 KHOA CÔNG NGHỆ THÔNG TIN Trang 82 
scanf("%d",&x); 
Insert_Begin(p, x); 
break; 
case 3: 
clrscr(); 
printf("Cho x= "); 
scanf("%d",&x); 
Insert_End(p, x); 
break; 
case 4: 
clrscr(); 
printf("Cho vi tri can chen:"); 
scanf("%d",&vitri); 
printf("\nCho x= "); 
scanf("%d",&x); 
Insert_Middle(p, vitri, x); 
break; 
case 5: 
clrscr(); 
Remove_Begin(p); 
break; 
case 6: 
clrscr(); 
Remove_End(p); 
break; 
case 7: 
clrscr(); 
printf("Cho vi tri can xoa: "); 
scanf("%d",&vitri); 
Remove_Middle(p,vitri); 
 KHOA CÔNG NGHỆ THÔNG TIN Trang 83 
break; 
case 8:: 
PrintList(*p); 
break; 
default: 
break; 
} 
}while (chon!=9); 
return; 
}