Bài giảng Cấu trúc dữ liệu - Chương 6: Kiểu cấu trúc cây - Thiều Quang Trung

CHƯƠNG 6 
KIỂU CẤU TRÚC CÂY 
GV Th.S. Thiều Quang Trung 
Bộ môn Khoa học cơ bản 
Trường Cao đẳng Kinh tế Đối ngoại 
•Khái niệm cấu trúc cây - tree 1 
•Đặc điểm cấu trúc cây 2 
•Định nghĩa kiểu cấu trúc cây 3 
•Các thao tác trên cấu trúc cây 4 
Nội dung 
2 GV. Thiều Quang Trung 
Khái niệm cấu trúc cây 
• Cây là một tập hợp T các phần tử (gọi là nút 
của cây), gồm có: 
– một nút đặc biệt gọi là nút gốc, 
– các nút còn lại được chia thành những tập rời 
nhau T1, T2, ,Tn theo quan hệ phân cấp, trong đó 
Ti cũng là một cây. 
• Mỗi nút ở cấp i sẽ quản lý một số nút ở cấp 
i+1. Quan hệ này gọi là quan hệ cha –con. 
GV. Thiều Quang Trung 3 
Khái niệm cấu trúc cây 
• Bậc của một nút: là số 
cây con của nút đó 
• Nút gốc: là nút không 
có nút cha 
• Nút lá: là nút có bậc 
bằng 0 
• Nút nhánh: là nút có 
bậc khác 0 và không 
phải là gốc 
4 
2 
2 2 
1 1 0 
0 
0 
0 
GV. Thiều Quang Trung 
Mức 4 
Mức 3 
Mức 2 
Mức 1 
Khái niệm cấu trúc cây 
• Chiều dài đường đi đến nút x: là số nhánh cần đi qua 
kể từ gốc đến x 
• Độ cao của cây: Độ sâu (mức) của nút lá thấp nhất 
5 
x 
GV. Thiều Quang Trung 
Đặc điểm cây nhị phân tìm kiếm 
• Là cây nhị phân 
• Giá trị của một node 
bất kỳ luôn lớn hơn giá 
trị của tất cả các node 
bên trái và nhỏ hơn giá 
trị tất cả các node bên 
phải 
 Nút có giá trị nhỏ nhất 
nằm ở trái nhất của 
cây 
 Nút có giá trị lớn nhất 
nằm ở phải nhất của 
cây 
6 
7 
3 36 
1 6 15 40 
23 4 
GV. Thiều Quang Trung 
Định nghĩa kiểu dữ liệu 
7 
typedef struct TNODE 
{ 
 Key; 
 struct TNODE *pLeft, *pRight; 
} *TREE; 
Nút 
Giá trị 
Trỏ trái Trỏ phải 
TNODE 
Key 
pLeft pRight 
GV. Thiều Quang Trung 
Ví dụ khai báo 
typedef struct TNODE 
{ 
 int Key; 
 struct TNODE *pLeft, *pRight; 
} *TREE; 
8 GV. Thiều Quang Trung 
Các lưu ý khi cài đặt 
• Bước 1: Khai báo kiểu dữ liệu biểu diễn cây 
• Bước 2: Xây dựng hàm đưa dữ liệu (nhập) 
vào cây 
• Bước 3: Xây dựng các thao tác duyệt, tìm 
kiếm, huỷ,  
9 GV. Thiều Quang Trung 
Các thao tác 
1. Tạo cây 
2. Duyệt cây 
3. Cho biết các thông tin của cây 
4. Tìm kiếm 
5. Xoá node trên cây 
10 GV. Thiều Quang Trung 
Tạo cây 
11 
40 15461 36 
7 36 3 1 6 4 15 40 
7 • Nếu node cần 
thêm nhỏ hơn 
node đang xét thì 
thêm về bên trái 
• Ngược lại thì thêm 
về bên phải 
GV. Thiều Quang Trung 
Hàm tạo cây 
12 
int ThemNut (TREE & t, int x) 
{ if(t!=NULL) 
 { if(x==t->Key) return 0; 
 else 
 { if(xKey) ThemNut(t->pLeft, x); 
 else ThemNut(t->pRight, x); 
 } 
 } 
 else 
 { t=new TNODE; 
 if(t==NULL) return -1; 
 t->Key=x; 
 t->pLeft=t->pRight=NULL; 
 return 1; 
 } 
} GV. Thiều Quang Trung 
Duyệt cây 
• Thứ tự trước (NLR) 
• Thứ tự giữa (LNR) 
• Thứ tự sau (LRN) 
13 GV. Thiều Quang Trung 
14 
Bước Kết quả duyệt theo thứ tự NLR 
1 7 L7 R7 
2 3 L3 R3 R7 
3 1 R3 R7 
4 6 L6 R7 
5 4 R7 
6 36 L36 R36 
7 15 R15 R36 
8 23 R36 
9 40 
KQ 7 3 1 6 4 36 15 23 40 
7 
3 36 
1 6 15 40 
23 4 
GV. Thiều Quang Trung 
Hàm duyệt NLR 
• Tại node t đang xét, 
nếu khác rỗng thì: 
– In giá trị của t 
– Duyệt cây con bên 
trái của t theo thứ tự 
NLR 
– Duyệt cây con bên 
phải của t theo thứ 
tự NLR 
15 
void NLR (TREE t) 
{ 
 if(t!=NULL) 
 { 
 coutKey<<“\t”; 
 NLR(t->pLeft); 
 NLR(t->pRight); 
 } 
} 
GV. Thiều Quang Trung 
Bài tập 
Vẽ cây nhị phân tìm kiếm theo thứ tự nhập 
từ trái sang phải và duyệt cây theo thứ tự 
trước: 
• 27; 19; 10; 21; 35; 25; 41; 12; 46; 7 
• H; B; C; A; E; D; Z; M; P; T 
• Huế; Đà Nẵng; Hà Nội; Vĩnh Long; Cần Thơ; 
Sóc Trăng; Nha Trang; Đồng Nai; Vũng Tàu; 
An Giang; Tiền Giang; Bình Dương; Hải 
Dương 
16 GV. Thiều Quang Trung 16 
17 
Bước Kết quả duyệt theo thứ tự LNR 
1 L7 7 R7 
2 L3 3 R3 7 R7 
3 1 3 R3 7 R7 
4 3 R3 7 R7 
5 L6 6 7 R7 
6 4 6 7 R7 
7 6 7 R7 
8 7 R7 
9 L36 36 R36 
10 15 R15 36 R36 
11 23 36 R36 
12 36 R36 
13 40 
KQ 1 3 4 6 7 15 23 36 40 
7 
3 36 
1 6 15 40 
23 4 
GV. Thiều Quang Trung 
Hàm duyệt LNR 
• Tại node t đang xét, 
nếu khác rỗng thì 
– Duyệt cây con bên 
trái của t theo thứ 
tự LNR 
– In giá trị của t 
– Duyệt cây con bên 
phải của t theo thứ 
tự LNR 
18 
void LNR (TREE t) 
{ 
 if(t!=NULL) 
 { 
 LNR(t->pLeft); 
 coutKey<<“ “; 
 LNR(t->pRight); 
 } 
} 
 GV. Thiều Quang Trung 
19 
Bước Kết quả duyệt theo thứ tự LRN 
1 L7 R7 7 
2 L3 R3 3 R7 7 
3 1 R3 3 R7 7 
4 L6 6 3 R7 7 
5 4 6 3 R7 7 
6 6 3 R7 7 
7 3 R7 7 
8 L36 R36 36 7 
9 R15 15 R36 36 7 
10 23 15 R36 36 7 
11 15 R36 36 7 
12 40 36 7 
13 36 7 
14 7 
KQ 1 4 6 3 23 15 40 36 7 
7 
3 36 
1 6 15 40 
23 4 
GV. Thiều Quang Trung 
Hàm duyệt LRN 
• Tại node t đang xét, 
nếu khác rỗng thì: 
– Duyệt cây con bên trái 
của t theo thứ tự LRN 
– Duyệt cây con bên 
phải của t theo thứ tự 
LRN 
– In giá trị của t 
20 
void LRN (TREE t) 
{ 
 if(t!=NULL) 
 { 
 LRN(t->pLeft); 
 LRN(t->pRight); 
 coutKey<<“ “; 
 } 
} 
GV. Thiều Quang Trung 20 
Bài tập 
• Bài 4 Vẽ cây nhị phân tìm kiếm theo thứ tự 
nhập: 
 27, 19, 10, 21, 3, 15, 41, 50, 30, 27 
 Hãy duyệt cây trên theo thứ tự giữa 
• Bài 5 Vẽ cây nhị phân tìm kiếm theo thứ tự 
nhập: 
 H, B, C, A, E, D, T, M, X, O 
 Hãy duyệt cây trên theo thứ tự sau 
21 GV. Thiều Quang Trung 21 
Vấn đề cần quan tâm 
Tạo cây từ kết quả duyệt NLR 
•Chọn giá trị đầu tiên làm node gốc 
•Lần lượt đưa các giá trị còn lại từ trái sang 
phải vào cây theo nguyên tắc tạo cây 
Tạo cây từ kết quả duyệt LRN 
•Chọn giá trị cuối cùng làm node gốc 
•Lần lượt đưa các giá trị còn lại từ phải sang 
trái vào cây theo nguyên tắc tạo cây 
22 GV. Thiều Quang Trung 22 
Vấn đề cần quan tâm 
Tạo cây từ kết quả duyệt LNR 
• Gọi r: Số lượng giá trị cho trước 
• Gọi m = r div 2: Giá trị ở giữa 
• Chọn giá trị thứ m làm node gốc 
• Lần lượt đưa các giá trị bắt đầu từ vị trí m-1 lùi về 
trái vào cây theo nguyên tắc tạo cây 
• Lần lượt đưa các giá trị bắt đầu từ vị trí m+1 đến 
cuối vào cây theo nguyên tắc tạo cây 
23 GV. Thiều Quang Trung 23 
Bài tập 
Bài 6 Vẽ cây nhị phân tìm kiếm T biết rằng 
khi duyệt cây T theo thứ tự NLR thì được dãy 
sau: 9, 4, 1, 3, 8, 6, 5, 7, 10, 14, 12, 13, 16, 19 
• Hãy duyệt cây T trên theo thứ tự LRN 
• Liệt kê các nút lá của cây. Liệt kê các nút 
nhánh của cây 
24 GV. Thiều Quang Trung 24 
Bài 7 Vẽ cây nhị phân tìm kiếm T biết rằng 
khi duyệt cây T theo thứ tự LRN thì được 
dãy sau: 1, 4, 7, 5, 3, 16, 18, 15, 29, 25, 30, 
20, 8 
• Hãy duyệt cây T trên theo thứ tự NLR 
• Cây T có chiều cao là bao nhiêu? Tìm các 
đường đi từ gốc có độ dài là 4 trên cây 
25 
Bài tập 
GV. Thiều Quang Trung 25 
Hàm nhập dữ liệu vào cây 
void Nhap(TREE &t) 
{ 
 int x; 
 do{ 
 cout<<“Nhap gia tri: “; 
 cin>>x; 
 int kq=ThemNut(t, x); 
 if(kq==0||kq==-1) 
 break; 
 }while (true); 
} 26 GV. Thiều Quang Trung 26 
Hàm main gọi thao tác duyệt LNR 
void main() 
{ 
 TREE t; 
 t=NULL; 
 Nhap(t); 
 cout<<“Duyet cay theo thu tu giua: “; 
 LNR(t); 
 Huy(t); 
} 
27 GV. Thiều Quang Trung 27 
Tìm kiếm 
1. Tìm x 
2. Tìm min 
3. Tìm min của cây con bên phải 
4. Tìm max 
5. Tìm max của cây con bên trái 
28 GV. Thiều Quang Trung 28 
Ví dụ tìm x = 23 
29 
7 
3 36 
1 6 15 40 
23 4 
GV. Thiều Quang Trung 29 
Xóa node trên cây 
1. Node lá 
2. Node có 1 cây con 
3. Node có 2 cây con 
30 
7 
3 36 
1 6 15 40 
23 4 
GV. Thiều Quang Trung 30 
Xóa node lá 
Xóa 1 
Xóa 23 
31 
7 
3 36 
1 6 15 40 
23 4 
GV. Thiều Quang Trung 31 
Xóa node 1 cây con 
Xóa 6 
Xóa 15 
32 
7 
3 36 
1 6 15 40 
23 4 
4 23
GV. Thiều Quang Trung 32 
Xóa node 2 cây con 
Tìm node thế mạng 
• Cách 1: Tìm node trái 
nhất của cây con phải 
• Cách 2: Tìm node phải 
nhất của cây con trái 
Xóa 36 (Cách 2) 
33 
7 
3 36 
1 6 15 40 
23 4 
16 
23
GV. Thiều Quang Trung 33 
• Cho dãy số theo thứ tự nhập từ trái sang 
phải: 20, 15, 35, 30, 11, 13, 17, 36, 47, 16, 
38, 28, 14 
– Vẽ cây nhị phân tìm kiếm cho dãy số trên 
– Cho biết kết quả duyệt cây trên theo thứ tự 
trước, giữa và sau 
– Cho biết độ cao của cây, các nút lá, các nút có 
bậc 2 
– Vẽ lại cây sau khi thêm nút: 25 và 91 
– Trình bày từng bước và vẽ lại cây sau khi lần lượt 
xoá các nút: 11 và 35 
34 
Bài tập 
GV. Thiều Quang Trung 34 
Viết hàm 
1. In ra các node có giá trị chẵn 
2. In ra các node có giá trị lớn hơn x 
3. Độ cao của cây 
4. Số node của cây 
5. Tìm min, max 
6. Tìm node có giá trị x 
35 GV. Thiều Quang Trung 35 
Viết hàm 
7. Số node lá (node bậc 0) 
8. Số node có 1 cây con (node bậc 1) 
9. Số node chỉ có 1 cây con phải 
10. Số node có 1 cây con trái 
11. Số node 2 cây con (node bậc 2) 
12. Các node trên từng mức của cây 
13. Độ dài đường đi từ gốc đến node x 
36 GV. Thiều Quang Trung 36 
GV: Thiều Quang Trung 37