Bài giảng Cấu trúc dữ liệu & giải thuật (Data Structures & Algorithms) - Bài 8: Cây và Duyệt cây (Trees & Tree Traversals)

Nội dung text: Bài giảng Cấu trúc dữ liệu & giải thuật (Data Structures & Algorithms) - Bài 8: Cây và Duyệt cây (Trees & Tree Traversals)

1. Cây và Duyệt cây (Trees & Tree Traversals) Nguyễn Mạnh Hiển Khoa Công nghệ thông tin hiennm@tlu.edu.vn
2. Các khái niệm về cây • Cây (tree) là một tập các nút (node), bao gồm: − Nút gốc R (root) − Các cây con T1, T2, , Tk được nối với nút gốc R bằng các cạnh (edge) • R được gọi là nút cha của cây con Ti, còn Ti được gọi là cây con của R • Cây có thể rỗng (không có nút nào) hoặc chỉ có nút gốc (không có cây con)
3. Các khái niệm về cây • Cây là một tập hợp N nút: − Một nút gốc − N – 1 cạnh vì mỗi nút (trừ nút gốc) có một cạnh nối với nút cha
4. Các khái niệm về cây • Nút lá: nút không có con (B, C, H) • Nút anh em: các nút cùng cha (K, L, M) • Nút ông (E) và nút cháu (P, Q)
5. Các khái niệm về cây • Đường đi từ nút n1 đến nút nk là dãy các nút n1, n2, , nk trong đó ni là cha của ni+1 (1 i < k) • Chiều dài đường đi là số cạnh trên đường đi đó (tức là k – 1) − Đường đi từ một nút tới chính nó có chiều dài bằng 0
6. Các khái niệm về cây • Chiều sâu của nút ni là chiều dài đường đi từ nút gốc đến nút ni − Nút gốc có chiều sâu 0 − Chiều sâu của cây bằng chiều sâu của nút lá sâu nhất • Chiều cao của nút ni là chiều dài của đường đi dài nhất từ nút ni đến một nút lá − Nút lá có chiều cao 0 − Chiều cao của cây bằng chiều cao của nút gốc • Chiều cao của cây = chiều sâu của cây
7. Các khái niệm về cây • Nếu có đường đi từ nút n1 đến nút n2: − n1 được gọi là tổ tiên (ancestor) của n2, và n2 được gọi là hậu duệ (descendant) của n1 − nếu n1 n2 thì có các khái niệm tổ tiên thực sự và hậu duệ thực sự
8. Cài đặt cây • Mỗi nút chứa: − dữ liệu − một con trỏ tới nút con đầu tiên − một con trỏ tới nút anh em kế tiếp
9. Cài đặt cây
10. Duyệt cây theo thứ tự trước (preorder traversal) Theo kiểu đệ quy: 1. Thăm (xử lý) một nút 2. Thăm các nút con
11. Duyệt cây theo thứ tự trước root 1 root 1 (1) 2 3 4 2 3 4 (2) 5 6 7 8 5 6 7 8 root 1 root 1 (3) 2 3 4 2 3 4 (4) 5 6 7 8 5 6 7 8
12. Duyệt cây theo thứ tự trước root 1 root 1 (5) (6) 2 3 4 2 3 4 5 6 7 8 5 6 7 8 root 1 root 1 (7) 2 3 4 2 3 4 (8) 5 6 7 8 5 6 7 8
13. Duyệt cây theo thứ tự sau (postorder traversal) Theo kiểu đệ quy: 1. Thăm (xử lý) các nút con 2. Thăm nút
14. Duyệt cây theo thứ tự sau root 1 root 1 (1) (2) 2 3 4 2 3 4 5 6 7 8 5 6 7 8 root 1 root 1 (3) 2 3 4 2 3 4 (4) 5 6 7 8 5 6 7 8
15. Duyệt cây theo thứ tự sau root 1 root 1 (5) (6) 2 3 4 2 3 4 5 6 7 8 5 6 7 8 root 1 root 1 (7) 2 3 4 2 3 4 (8) 5 6 7 8 5 6 7 8
16. Duyệt cây theo thứ tự sau root 1 root 1 (9) (10) 2 3 4 2 3 4 5 6 7 8 5 6 7 8 root 1 root 1 (11) 2 3 4 2 3 4 (12) 5 6 7 8 5 6 7 8
17. Duyệt cây theo thứ tự sau root 1 root 1 (13) (14) 2 3 4 2 3 4 5 6 7 8 5 6 7 8 root 1 root 1 2 3 4 (15) 2 3 4 (16) 5 6 7 8 5 6 7 8