Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 8: Cây và Duyệt Cây - Nguyễn Mạnh Hiển

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 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) 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 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) 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 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 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ự 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 Cài đặt cây 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 Duyệt cây theo thứ tự trước 1 2 3 4 5 6 8 7 root 1 2 3 4 5 6 8 7 root 1 2 3 4 5 6 8 7 root 1 2 3 4 5 6 8 7 root (1) (4) (2) (3) Duyệt cây theo thứ tự trước 1 2 3 4 5 6 8 7 root 1 2 3 4 5 6 8 7 root 1 2 3 4 5 6 8 7 root 1 2 3 4 5 6 8 7 root (5) (6) (7) (8) 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 Duyệt cây theo thứ tự sau 1 2 3 4 5 6 8 7 root 1 2 3 4 5 6 8 7 root 1 2 3 4 5 6 8 7 root 1 2 3 4 5 6 8 7 root (2) (1) (3) (4) Duyệt cây theo thứ tự sau 1 2 3 4 5 6 8 7 root 1 2 3 4 5 6 8 7 root 1 2 3 4 5 6 8 7 root 1 2 3 4 5 6 8 7 root (5) (6) (7) (8) Duyệt cây theo thứ tự sau 1 2 3 4 5 6 8 7 root 1 2 3 4 5 6 8 7 root 1 2 3 4 5 6 8 7 root 1 2 3 4 5 6 8 7 root (9) (10) (11) (12) Duyệt cây theo thứ tự sau 1 2 3 4 5 6 8 7 root 1 2 3 4 5 6 8 7 root 1 2 3 4 5 6 8 7 root 1 2 3 4 5 6 8 7 root (13) (14) (15) (16)