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 17. Cấu trúc dữ liệu dạng cây
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
1
Lecture 17. Trees (1/2)
Nội dung bài học:
17.1. Khái niệm về cây.
17.2. Các phương pháp duyệt cây.
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 University
2
17.1. Khái niệm về cây (1/)
17.1.1. Giới thiệu.
Trees được dùng cho cấu trúc dữ liệu dạng phân cấp.
Ví dụ:
Vi ệc phân cấp cấu trúc dữ liệu được dùng cho minh họa lược đồ công việc.
Tổ chức của một đơn vị.
Cây biểu thức.
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
3
Khoa Công nghệ thông tin
BM KHMT
Ví dụ về cây: Tổ chức Khoa CNTT
BM HTTT BM ANM BM CNPM BM Toán TTMT
Phòng TN Giáo viên 1 Giáo viên 2
17.1. Khái niệm về cây (2/)
17.1.2. Định nghĩa về tree.
Cây được định nghĩa đệ quy như sau:
Một cây được định nghĩa bởi một tập các node T có dạng:
Có một node đặc biệt gọi là root.
Các node còn lại được phân chia rời nhau thành n tập dạng T1,
T2,…,Tn, trong đó Ticũng là một cây.
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
4
17.1. Khái niệm về cây (3/)
Hình trên minh họa 1 cây.
Tập hợp các node {A, B, C, D, G, H, I, E, F}.
A là root.
Các node còn lại được chia thành các tập {B, G, H, I}, {C, E, F} và
{D}. Mỗi tập trên lại tạo thành 1 cây.
@copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
5
A
B C D
G H I E F