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: Chương 9 - Nguyễn Xuân Vinh

Chia sẻ: Xaydung K23 | Ngày: | Loại File: PPTX | Số trang:66

Thêm vào BST
Báo xấu
79
lượt xem 6
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 - Chương 9: Tree trình bày về khái niệm, thuật ngữ của cấu trúc cây, cây nhị phân và cây nhị phân tìm kiếm. Đây là tài liệu tham khảo hữu ích cho bạn đọc nghiên cứu và tìm hiểu về Cấu trúc dữ liệu.

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: Chương 9 - Nguyễn Xuân Vinh

  1. GV: NGUYỄN XUÂN VINH CẤU TRÚC DỮ LIỆU DATA STRUCTURES [214331] TREE MÔN: CẤU TRÚC DỮ LIỆU Nguyễn Xuân Vinh 6/12/14 nguyenxuanvinh@hcmuaf.edu. vn /XX 1
  2. 2 /XX 6/12/14 MÔN: CẤU TRÚC DỮ LIỆU GV: NGUYỄN XUÂN VINH - Linear Cấu trúc dữ liệu 2 Hierarchical structures
  3. GV: NGUYỄN XUÂN VINH Nội dung • Cấu trúc cây • Cây nhị phân • Cây nhị phân tìm kiếm MÔN: CẤU TRÚC DỮ LIỆU 6/12/14 /XX 3 - 3
  4. GV: NGUYỄN XUÂN VINH Cấu trúc cây • Tập hợp các nút và cạnh nối các nút đó • Có một nút gọi là gốc • Quan hệ one-to-many giữa các nút • Có duy nhất một đường đi từ gốc đến một nút MÔN: CẤU TRÚC DỮ LIỆU • Các loại cây: – Nhị phân: mỗi nút có {0,1, 2} nút con – Tam phân: mỗi nút có {0,1,2,3} nút con – n-phân: mỗi nút có {0,1,..,n} nút con 6/12/14 /XX 4 - 4
  5. 5 /XX 6/12/14 MÔN: CẤU TRÚC DỮ LIỆU GV: NGUYỄN XUÂN VINH - Cấu trúc cây 5
  6. 6 /XX 6/12/14 MÔN: CẤU TRÚC DỮ LIỆU GV: NGUYỄN XUÂN VINH - Q B Cạnh K Z Khái niệm R A J A F D gốc L nút Lá 6
  7. GV: NGUYỄN XUÂN VINH Thuật ngữ – Root node: nút gốc: không có nút cha – Leaf node: nút lá: không có nút con – Internal node: nút trong: không phải nút con và nút gốc – Height: chiều cao: khoảng cách từ gốc đến lá MÔN: CẤU TRÚC DỮ LIỆU – Parent node (or ancestor, or superior): nút cha – Child nodes (successor): nút con Nút gốc 1 Nút trong 6/12/14 2 3 4 Chiều cao Nút lá /XX 5 6 7 8 7 - 7
  8. GV: NGUYỄN XUÂN VINH Thuật ngữ Root MÔN: CẤU TRÚC DỮ LIỆU Node A Node B Node C Node D Node E Node F Node G Node H Node I Node J Node K 6/12/14 Node L /XX Cây con Nút anh em 8 - 8
  9. GV: NGUYỄN XUÂN VINH Ví dụ cây • Một số loại cây thường gặp: MÔN: CẤU TRÚC DỮ LIỆU – Cây nhị phân. – Cây quyết định. – Cây biểu thức. – Cây đỏ đen. 6/12/14 /XX 9
  10. GV: NGUYỄN XUÂN VINH Nội dung n Cấu trúc cây n Cây nhị phân n Cây nhị phân tìm kiếm n Cây nhị phân tìm kiếm cân bằng AVL MÔN: CẤU TRÚC DỮ LIỆU 6/12/14 /XX 10
  11. GV: NGUYỄN XUÂN VINH Cây nhị phân (Binary Tree) • Cấu trúc cây đơn giản nhất • Tại mỗi nút gồm các 3 thành phần – Phần data: chứa giá trị, thông tin… – Liên kết đến nút con trái (nếu có) – Liên kết đến nút con phải (nếu có) MÔN: CẤU TRÚC DỮ LIỆU • Cây nhị phân có thể rỗng (ko có nút nào) • Cây NP khác rỗng có 1 nút gốc – Có duy nhất 1 đường đi từ gốc đến 1 nút – Nút không có nút con bên trái và con bên phải là nút lá 6/12/14 /XX 11 - 11
  12. GV: NGUYỄN XUÂN VINH Binary Tree Kích thước = 9 (số nút) Mức 0 A Cây con trái Cây con phải MÔN: CẤU TRÚC DỮ LIỆU Mức 1 B C Mức 2 D E F G 6/12/14 Mức 3 Độ sâu/chiều cao = 3 H I /XX 12 - 12
  13. GV: NGUYỄN XUÂN VINH Binary Tree • Cây nhị phân đúng: – Nút gốc và nút trung gian có đúng 2 con • Cây nhị phân đúng có n nút lá thì số nút trên cây 2n-1 MÔN: CẤU TRÚC DỮ LIỆU A B C 6/12/14 D E F G /XX H I J K 13 - 13
  14. GV: NGUYỄN XUÂN VINH Binary Tree • Cây nhị phân đầy đủ với chiều sâu d – Phải là cây nhị phân đúng – Tất cả nút lá có chiều sâu d MÔN: CẤU TRÚC DỮ LIỆU A Số nút = (2d+1 -1) Số nút trung gian = ? Biết số nút tính d của cây NP đầy đủ B C 6/12/14 D E F G /XX 14 - 14
  15. GV: NGUYỄN XUÂN VINH Binary Tree • Duyệt cây: – Do cây là cấu trúc phi tuyến tính – 3 cách duyệt cây nhị phân • Duyệt theo thứ tự trước PreOrder: NLR • Duyệt theo thứ tự giữa InOrder: LNR MÔN: CẤU TRÚC DỮ LIỆU • Duyệt theo thứ tự sau PostOrder: LRN A B C 6/12/14 D E F G /XX 15 - 15
  16. GV: NGUYỄN XUÂN VINH Binary Tree P MÔN: CẤU TRÚC DỮ LIỆU D S A M W Pre-order (trước): PDAM SWT T Post-order (sau): AMDTWSP In-order (giữa): ADMPSTW 6/12/14 Level-Order (rộng): P D S A M W T /XX 16 - 16
  17. GV: NGUYỄN XUÂN VINH Cài đặt cây • Cây có thể được cài đặt bằng: – Mảng – Danh sách con – Theo con trái nhất và anh em ruột phải MÔN: CẤU TRÚC DỮ LIỆU – Danh sách liên kết 6/12/14 /XX 17
  18. GV: NGUYỄN XUÂN VINH Cài đặt cây: bằng mảng • Cách 1: Nếu cây T có n nút, ta gán tên các nút lần lượt là 0,1,2,..n-1 sau đó ta dùng 2 mảng A và L để lưu trữ cây bằng cách: – Cho A[i] = j với j là nút cha của nút i. – A[i] = -1 nếu i là nút gốc. MÔN: CẤU TRÚC DỮ LIỆU – L[i] = x với x là nhãn của nút thứ i. 6/12/14 18 /XX 18
  19. GV: NGUYỄN XUÂN VINH Cài đặt cây: bằng mảng • Cách 2: – Dùng 1 mảng A là mảng các nút mà mỗi nút bao gồm: • Biến parent dùng để lưu trữ chỉ số của nút cha. • Biến data dùng để lưu trữ thông tin của nút đó. MÔN: CẤU TRÚC DỮ LIỆU – Một biến maxNode để giữ số nút hiện tại đang có trên cây. 6/12/14 19 /XX 19
  20. GV: NGUYỄN XUÂN VINH Cài đặt cây: bằng mảng • Nhận xét: – hàm PARENT(n,T) tốn chỉ một hằng thời gian để lấy ra cha của nút n trong cây T. – Các hàm đòi hỏi thông tin về các con không làm việc tốt vì phải tốn vòng lặp để dò tìm. MÔN: CẤU TRÚC DỮ LIỆU – Tìm nút con trái nhất của nút i là không thể xác định được. – Cách khắc phục qui ước cách đánh thứ tự như sau: • Đánh số theo thứ tự tăng dần bắt đầu tại nút gốc. • Nút cha được đánh số trước các nút con. • Các nút con cùng một nút cha được đánh số lần lượt từ trái sang phải. 6/12/14 20 /XX 20
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
2=>2