Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 19: Cây nhị phân - Ngô Hữu Phước
19.1. Khái niệm về cây nhị phân (1/7) 19.1.1. Giới thiệu và định nghĩa: Cây nhị phân là trường hợp đặc biệt của cây, trong đó không có node nào trên cây có bậc lớn hơn 2. Do đó cây nhị phân T có thể định nghĩa: Có một node đặc biệt trên cây gọi là root của cây. Các node khác trên cây được chia thành 2 tập T1 và T2, trong đó chúng cũng là cây nhị phân. Cây con T1 được gọi là cây con bên trái. Cây con T2 được gọi là cây con bên phải. 19.1. Khái niệm về cây nhị phân (2/7) Từ định nghĩa cây nhị phân ta nhận thấy rằng: Số node tối đa trên cây nhị phân tại mức i là 2i−1 Nếu k là độ sâu của cây thì số phần tử tối đa trên cây là: 2k − 1 = 2k−1 + 2k−2 + + 20
Bạn đang xem trước 20 trang tài liệu Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 19: Cây nhị phân - Ngô Hữu Phước, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Giảng viên: TS. Ngo Huu Phuc
Tel: 0438 326 077
Mob: 098 5696 580
Email: ngohuuphuc76@gmail.com
Cấu trúc dữ liệu và giải thuật
Bài 19. Cây nhị phân
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University1
Bài 19: Cây nhị phân
Nội dung:
19.1. Khái niệm về cây nhị phân.
19.2. Biểu diễn cây nhị phân.
19.4. Duyệt cây nhị phân.
Tham khảo:
1. Deshpande Kakde: C and Data structures.chm, Chapter 21: Trees
2. Elliz Horowitz – Fundamentals of Data Structures.chm, Chapter 5: Trees
3. Kyle Loudon: Mastering Algorithms with C.chm, Chapter 9 Trees.
4. Bài giảng TS Nguyễn Nam Hồng.
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University2
19.1. Khái niệm về cây nhị phân (1/7)
19.1.1. Giới thiệu và định nghĩa:
Cây nhị phân là trường hợp đặc biệt của cây, trong đó không
có node nào trên cây có bậc lớn hơn 2.
Do đó cây nhị phân T có thể định nghĩa:
Có một node đặc biệt trên cây gọi là root của cây.
Các node khác trên cây được chia thành 2 tập T1 và T2, trong đó
chúng cũng là cây nhị phân.
Cây con T1 được gọi là cây con bên trái.
Cây con T2 được gọi là cây con bên phải.
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University3
19.1. Khái niệm về cây nhị phân (2/7)
Từ định nghĩa cây nhị phân ta
nhận thấy rằng:
Số node tối đa trên cây nhị
phân tại mức i là 2i−1
Nếu k là độ sâu của cây thì số
phần tử tối đa trên cây là:
2k − 1 = 2k−1 + 2k−2 + + 20
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University4
A
B C
GD
H
E
I
F
Ví dụ về cây nhị phân
19.1. Khái niệm về cây nhị phân (3/7)
Cây lệch:
Trong thực tế, có dạng đặc biệt: cây lệch. Cây lệch là cây chỉ có
cây con trái hoặc phải.
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University5
A
B
C
A
B
C
Cây lệch trái Cây lệch phải
19.1. Khái niệm về cây nhị phân (4/7)
Cây nhị phân đầy đủ (Full binary tree):
Cây nhị phân đầy đủ có độ cao là k thì các node ở mức thấp hơn có đủ con trái
và phải.
Như vậy, với cây nhị phân đầy đủ có độ cao là k thì số node trên cây là 2k-1.
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University6
A
B
C
E
F G
Ví dụ về cây nhị
phân đầy đủ có độ
cao là 3
D
Ví dụ: Với k=3, số node trên cây
nhị phân đầy đủ là 23-1=7
19.1. Khái niệm về cây nhị phân (5/7)
Cây nhị phân hoàn chỉnh (Complete binary tree):
Cây nhị phân hoàn chỉnh có độ cao là k, với độ cao k-1 là đầy đủ.
Tại độ cao là k, các node được đưa vào cây từ trái sang phải.
Nhận xét:
Các node tại mức k-2 về trước có đủ 2 con.
Các node ở mức k-1 có thể có 2 con hoặc 1 con. Nếu có 1 con trì có con trái
(các node cùng mức trước đó đã có 2 con)
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University7
A
B
C
E
F
Ví dụ về cây nhị phân hoàn chỉnh
D
A
B
C
E
D
19.1. Khái niệm về cây nhị phân (6/7)
So sánh giữa cây nhị phân đầy đủ và hoàn chỉnh:
Cây nhị phân đầy đủ là trường hợp riêng của cây nhị phân hoàn chỉnh.
Cây nhị phân hoàn chỉnh chưa chắc đã là cây nhị phân đầy đủ.
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University8
A
B
C
E
F
Cây nhị phân hoàn chỉnh
D
A
B
C
E
D F G
Cây nhị phân đầy đủ
19.1. Khái niệm về cây nhị phân (7/7)
Cây nhị phân cân bằng (Balanced binary tree):
Cây nhị phân cân bằng là cây mà tại mỗi node độ cao cây con trái và phải
không lệch nhau quá 1.
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University9
A
B
C
E
F
Ví dụ về cây nhị phân cân bằng
D
A
B
C
E
D
19.2. Biểu diễn cây nhị phân (1/6)
Với cây nhị phân hoàn chỉnh có thể biểu diễn cây bằng mảng có n phần tử.
Nếu cây nhị phân hoàn chỉnh được biểu diễn dưới dạng mảng, giá trị của
phần tử thứ i sẽ được chứa trong mảng tại vị trí thứ i (1<=i<=n).
Khi đó, phần tử “cha” của i sẽ là i/2 và 2 con của node i sẽ là 2i và 2i+1.
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University10
A1
2
3
4
5
A
B
D
C
E
B
C
D
E
Biểu diễn cây nhị phân hoàn chỉnh bằng mảng
19.2. Biểu diễn cây nhị phân (2/6)
Với cây nhị phân bất kỳ cũng có thể biểu diễn dạng mảng.
Tuy nhiên, cách biểu diễn trên gây lãng phí bộ nhớ.
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University11
A1 A
B
D
C
E F G
H I
B
C
D
E
F
G
H
I
2
3
4
5
6
7
8
9
10
11 Ô nhớ lãng phí
19.2. Biểu diễn cây nhị phân (3/6)
Với cách biểu diễn trên có ưu điểm là có khả năng truy cập dữ
liệu nhanh. Tuy nhiên, nhược điểm chính là lãng phí ô nhớ.
Có thể biểu diễn cây dạng mảng, trong đó, mỗi node sẽ có cấu
trúc:
Dữ liệu của node.
Chỉ số của node con trái.
Chỉ số của node con phải.
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University12
Data Right indexLeft index
19.2. Biểu diễn cây nhị phân (4/6)
Ví dụ về biểu diễn cây nhị phân.
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University13
Data Right indexLeft index
A
B
D
C
E F G
H I
1. A 32
2. B 54
3. C 76
4. D 00
5. E 98
6. F 00
7. G 00
8. H 00
9. I 00
19.2. Biểu diễn cây nhị phân (5/6)
Việc biểu diễn cây dạng mảng không phù hợp với việc thường
xuyên thêm bớt trên cây. Chi phí cho việc thêm bớt quá lớn. Do đó,
ta có thể biểu diễn cây dạng liên kết. Trong trường hợp này, mỗi
phần tử sẽ có 3 thành phần:
Thành phần dữ liệu,
Con trỏ liên kết trái,
Con trỏ liên kết phải
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University14
Data Right ptrLeft ptr
Biểu diễn trên ngôn ngữ C:
struct tnode
{
TreeEntry data;
struct tnode *lchild,*rchild;
};
19.2. Biểu diễn cây nhị phân (6/6)
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University15
A
B C
D
NULL NULL
NULL NULL
Ví dụ về biểu diễn cây dạng liên kết
19.3. Duyệt cây nhị phân (1/9)
Đối với cây nói chung, cây nhị phân nói riêng, dữ liệu
được lấy ra phụ thuộc vào cách duyệt cây.
Thông thường, có 4 cách duyệt cây sau:
Duyệt tiền thứ tự (PreOrder): NLR.
Duyệt hậu thứ tự (PostOrder): LRN.
Duyệt trung thứ tự (InOrder): LNR
Duyệt theo chiều rộng (LevelOrder).
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University16
19.3. Duyệt cây nhị phân (2/9)
Duyệt tiền thứ tự (Preorder): NLR
1. Thăm node đang xét trước các node con của nó.
2. Thăm cây con bên trái.
3. Thăm cây con bên phải.
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University17
19.3. Duyệt cây nhị phân (3/9)
Duyệt tiền thứ tự (Preorder): NLR
Thứ tự đã duyệt: A B D E H I C F G
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University18
void NLR(Tree root)
{
if (root != NULL)
{
xử lý root;
NLR (root->left);
NLR (root->right);
}
}
A
B C
D E F G
1
2
3 4
5 6
7
8 9
H I
19.3. Duyệt cây nhị phân (4/9)
Duyệt trung thứ tự (Inorder): LNR
1. Thăm cây con bên trái của node đang xét trước.
2. Thăm node đang xét.
3. Thăm cây con bên phải của node đang xét.
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University19
19.3. Duyệt cây nhị phân (5/9)
Duyệt trung thứ tự (Inorder): LNR
Thứ tự đã duyệt: D B H E I A F C G
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University20
void LNR(Tree root)
{
if (root != NULL)
{
LNR(root->left);
xử lý root;
LNR(root->right);
}
}
A
B C
D E F G
6
2
1 4
3 5
8
7 9
H I
19.3. Duyệt cây nhị phân (6/9)
Duyệt hậu thứ tự (Postorder): LRN
1. Thăm cây con bên trái của node đang xét trước.
2. Thăm cây con bên phải của node đang xét trước.
3. Thăm node đang xét.
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University21
19.3. Duyệt cây nhị phân (7/9)
Duyệt hậu thứ tự (Postorder): LRN
Thứ tự đã duyệt: D H I E B F G C A
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University22
void LRN(Tree root)
{
if (root != NULL)
{
LRN (root->left);
LRN (root->right);
xử lý root;
}
}
A
B C
D E F G
9
5
1 4
2 3
8
6 7
H I
19.3. Duyệt cây nhị phân (8/9)
Thăm các node bắt đầu từ mức thấp nhất cho đến các mức cao.
Tại mỗi mức, thăm từ con trái trước, sau đó thăm con phải.
Sử dụng queue hỗ trợ trong quá trình duyệt cây.
Phương pháp này còn được gọi là Level-Order Traversal.
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University23
19.3. Duyệt cây nhị phân (9/9)
Thứ tự đã duyệt: A B C D G H I E F
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University24
A
B C
D E F G
1
2
4 5
8 9
3
6 7
H I
