intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: Hấp Hấp | Ngày: | Loại File: PDF | Số trang:17

Thêm vào BST
Báo xấu
48
lượt xem 3
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Cấu trúc dữ liệu và giải thuật: Cây và duyệt cây" cung cấp cho người học các kiến thức: Các khái niệm về cây, cài đặt cây, duyệt cây theo thứ tự trước, duyệt cây theo thứ tự sau. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

  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 2 3 4 2 3 4 (3) (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 2 3 4 2 3 4 (3) (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 2 3 4 2 3 4 (11) (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 2 3 4 (15) (16) 5 6 7 8 5 6 7 8
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
85=>1