Bài giảng Cấu trúc dữ liệu - Chương VI: 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
Trường Cao đẳng Kinh tế Đối ngoại
•Khái niệm cấu trúc cây - tree1
•Đặc điểm cấu trúc cây2
•Định nghĩa kiểu cấu trúc cây3
•Các thao tác trên cấu trúc cây4
Nội dung
2GV. 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
22
110
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
234
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;
8GV. 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ỷ, 
9GV. 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
10GV. Thiều Quang Trung
Tạo cây
11
401546136
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)
13GV. 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
234
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
16GV. 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
234
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
234
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, 7
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
21GV. 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
22GV. 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
23GV. 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
24GV. 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);
} 26GV. 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);
}
27GV. 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
28GV. Thiều Quang Trung 28
Ví dụ tìm x = 23
29
7
3 36
1 6 15 40
234
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
234
GV. Thiều Quang Trung 30
Xóa node lá
Xóa 1
Xóa 23
31
7
3 36
1 6 15 40
234
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
234
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
234
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
35GV. 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 
36GV. Thiều Quang Trung 36
GV: Thiều Quang Trung 37
Viết các hàm C/C++ thao tác cây
• Thêm 1 nút
• Tìm nhánh thay thế
• Hủy 1 nút
• Tìm nút x
• Đếm số nút lá
• Đếm nút có 1 nhánh
• Đếm nút có 2 nhánh
• Tìm chiều cao của cây
• Duyệt cây theo thứ tự giảm dần RNL
• In cấu trúc cây
GV. Thiều Quang Trung 38
Thêm 1 nút x vào cây
int themnode(tree &t,int x)
{ if(t!=NULL)
{ if(t->key==x) return 0;
if(t->key>x) return themnode(t->pleft,x);
else return themnode(t->pright,x); }
t=new node;
if(t==NULL) return -1;
t->key=x;
t->pleft=t->pright=NULL;
return 1;
}
GV. Thiều Quang Trung 39
Tìm nhánh thay thế 
void thaythe(tree &p,tree &t)
{
if(t->pleft)
thaythe(p,t->pleft);
else
{
p->key=t->key;
p=t;
t=t->pright; 
} 
}
GV. Thiều Quang Trung 40
Xóa 1 nút x khỏi cây
void huynode(tree &t,int x)
{ if(t)
{ if(t->keypright,x);
else { if(t->key>x) huynode(t->pleft,x);
else { node *p; p=t;
if(t->pleft==NULL) t=t->pright;
else { if(t->pright==NULL) t=t->pleft;
else thaythe(p,t->pright);}
delete p; } 
} 
} else cout << "\nKhong tim thay so can tim!"; 
}
GV. Thiều Quang Trung 41
Tìm nút x
bool find(tree t,int x)
{ if (t!=NULL)
{ if (x==t->key)
{ cout key;
return TRUE; }
else
if(x key) find(t->pleft,x);
else
find(t->pright,x);
} else
{ cout << "Khong tim thay ";
return FALSE ; }
}
GV. Thiều Quang Trung 42
Đếm số nút lá
int sonutLa(tree t)
{ if (t==NULL)
return 0;
if ((t->pleft == NULL)&&(t->pright==NULL))
return 1;
return sonutLa(t->pleft)+sonutLa(t->pright);
}
GV. Thiều Quang Trung 43
Đếm chiều cao của cây
int height(tree t)
{ 
if (t==NULL) return(0);
else return (1+
max(height(t->pleft),height(t->pright)));
}
GV. Thiều Quang Trung 44
Đếm số nút có 1 nhánh
int sonut1con(tree t)
{ if (t==NULL)
return 0;
if ((t->pleft == NULL)&&(t->pright==NULL))
return 0;
if (t->pleft == NULL)
return 1 + sonut1con(t->pright);
if (t->pright == NULL)
return 1 + sonut1con(t->pleft);
else
return sonut1con(t->pleft)+sonut1con(t->pright);
}
GV. Thiều Quang Trung 45
Đếm số nút có 2 nhánh
int sonut2con(tree t)
{ if (t==NULL) return 0;
if ((t->pleft == NULL)&&(t->pright==NULL))
return 0;
if (t->pleft == NULL)
return sonut2con(t->pright);
if (t->pright == NULL)
return + sonut2con(t->pleft);
else
return 1 + sonut2con(t->pleft)+sonut2con(t->pright);
}
GV. Thiều Quang Trung 46
Duyệt cây theo thứ tự giảm dần
void RNL(tree t)
{
if(t)
{
RNL(t->pright);
cout key << ", ";
RNL(t->pleft); 
} 
}
GV. Thiều Quang Trung 47
In cấu trúc cây
void printtree(tree t,int dichphai)
{
int i;
tree temp=t;
if (temp!=NULL)
{
printtree(temp->pright,dichphai+4);
for (i=1;i<=dichphai;i++) cout << " ";
cout key << endl;
printtree(temp->pleft,dichphai+4);
}
}
GV. Thiều Quang Trung 48