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: Chương 4 - ThS. Nguyễn Thị Khiêm Hòa (ĐH Ngân hàng TP.HCM)

Chia sẻ: Cxzvscv Cxzvscv | Ngày: | Loại File: PDF | Số trang:55

Thêm vào BST
Báo xấu
120
lượt xem 8
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: Chương 4 Cây nhằm trình bày về định nghĩa và các khái niệm Cây nhị phân, Cây nhị phân tìm kiếm và cây tổng quát từ đó giúp sinh viên hiểu rõ khái niệm và ứng dụng trên Cây Cài đặt các thuật toán trên cây, đặc biệt là cây nhị phân tìm kiếm.

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: Chương 4 - ThS. Nguyễn Thị Khiêm Hòa (ĐH Ngân hàng TP.HCM)

  1. Chương 4: Cây Giảng viên: Ths. Nguyễn Thị Khiêm Hòa Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
  2. Nội dung  Định nghĩa và các khái niệm  Cây nhị phân  Cây nhị phân tìm kiếm  Cây tổng quát Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 2
  3. Mục tiêu  Trang bị khái niệm và ứng dụng trên Cây  Cài đặt các thuật toán trên cây, đặc biệt là cây nhị phân tìm kiếm. Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 3
  4. Khái niệm  Cây là tập hữu hạn các nút (Tree node):  Có một nút gốc (root)  Các nút còn lại phân hoạch thành n tập riêng biệt T1, T2, …, Tn, với Ti là một cây  Giữa các nút có quan hệ phân cấp (hierarchical relationship) “cha con”.  Cây không có nút là cây rỗng (null tree). Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 4
  5. Biểu diễn cây  Bằng đồ thị  Bằng giản đồ  Bằng danh sách (các dấu ngoặc lồng nhau)  Bằng phương pháp Identatio Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 5
  6. Biểu diễn cây  Bằng đồ thị A / B C D A B C D E E F G H F G H I I J K J Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 6
  7. Biểu diễn cây  Bằng giản đồ D B A J G H I E C F Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 7
  8. Biểu diễn cây  Bằng danh sách (các dấu ngoặc lồng nhau) (/( A (C (F), D (G ( J ) ) ) ), (B (E ( H, I ) ) ) ) A / A B B C D C D E E F G H F G H I J I J K ( A ( B ( E, F( I, J, K) ), C ( G,H ), D ) ) Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 8
  9. Biểu diễn cây  Bằng phương pháp Indentatio / A C / F A B D G C D E J B F G H I E H J I Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 9
  10. Các thuật ngữ  Bậc của nút và bậc của cây  Nút gốc, Nút lá và nút nhánh  Nút cha (Parent), nút con (children) A B C D E F G H I J K L M Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 10
  11. Các thuật ngữ  Đường đi (path) / A B C D E F G H I J Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 11
  12. Các thuật ngữ  Mức của nút và chiều cao của cây Root 1 2 Chiều cao 3 của cây: 5 4 5 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 12
  13. Các thuật ngữ  Tổ tiên (ancestors) của một nút  Con cháu (Descendant) của một nút:  Các con của cùng một cha gọi là anh em ruột (siblings) / A B C D E F G H I J Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 13
  14. Cây có thứ tự và Rừng  Cây có thứ tự (ordered tree)  Một cây gọi là có thứ tự khi ta thay đổi vị trí của các cây con, ta nhận được một cây mới  Rừng (forest)  Tập hợp hữu hạn các cây phân biệt  Nếu bỏ đi nút gốc của một cây, ta sẽ thu được một rừng gồm nhiều cây phân biệt Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 14
  15. Cây nhị phân  Định nghĩa Cây con Cây con trái phải Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 15
  16. Cây nhị phân  Cây nhị phân biểu diễn biểu thức toán học Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 16
  17. Tính chất của cây nhị phân  Số nút tối đa mức i trong cây 2i-1  Số nút tối đa trong cây là 2h-1 (h chiều cao của cây)  Chiều cao của cây h  log2N (N là số nút trong cây). 1 2 3 4 5 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 17
  18. Cây nhị phân hoàn chỉnh / A B C D I E G J G Các nút ứng với các mức trừ mức cuối đều đạt tối đa, ở mức cuối, các nút đều đạt về phía trái Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 18
  19. Cây nhị phân đầy đủ / A B C D I E Các nút đạt tối đa ở cả mọi mức Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 19
  20. Cây nhị phân gần đầy / A B C D I E J G G Các nút ứng với các mức trừ mức cuối đều đạt tối đa, ở mức cuối, các nút không dạt đều về phía trái Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 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
3=>0