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

Bài giảng Trees (Cấu trúc cây)

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PPT | Số trang:72

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

Bài giảng Trees (Cấu trúc cây) được biên soạn nhằm trang bị cho các bạn những kiến thức về khái niệm cấu trúc cây; cấu trúc dữ liệu cây nhị phân tìm kiếm (tổ chức, các thuật toán, ứng dụng); cấu trúc dữ liệu cây nhị phân tìm kiếm. Mời các bạn tham khảo.

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 Trees (Cấu trúc cây)

  1. TREES         (Cấu trúc  cây)
  2. Mục tiêu  Giới thiệu khái niệm cấu trúc cây.  Cấu trúc dữ liệu cây nhị phân tìm kiếm: tổ chức, các thuật toán, ứng dụng.  Giới thiệu cấu trúc dữ liệu cây nhị phân tìm kiếm Cấu trúc Dữ liệu ­ Cấu trúc cây 2
  3. Cấu trúc cây
  4. Cấu trúc cây  Định  nghĩa  : cây là một tập hợp T các phần tử (gọi là nút của cây) trong đó có 1 nút đặc biệt được gọi là gốc, các nút còn lại được chia thành những tập rời nhau T1, T2 , ... , Tn theo quan hệ phân cấp trong đó Ti cũng là một cây. Mỗi nút ở cấp i sẽ quản lý một số nút ở cấp i+1. Quan hệ này người ta còn gọi là quan hệ cha-con. Cấu trúc Dữ liệu ­ Cấu trúc cây 4
  5. Cấu trúc cây Cấu trúc Dữ liệu ­ Cấu trúc cây 5
  6. Cấu trúc cây Cấu trúc Dữ liệu ­ Cấu trúc cây 6
  7. Cấu trúc cây Một số khái niệm cơ bản  Bậc của một nút : là số cây con của nút đó  Bậc của một cây : là bậc lớn nhất của các nút trong cây (số cây con tối đa của một nút thuộc cây ). Cây có bậc n thì gọi là cây n- phân.  Nút gốc : là nút không có nút cha.  Nút lá : là nút có bậc bằng 0 .  Nút nhánh : là nút có bậc khác 0 và không phải là gốc .  Mức của một nút :  Mức (gốc (T) ) = 0.  Gọi T1, T2, T3, ... , Tn là các cây con của T0  Mức (T1) = Mức (T2) = ... = Mức (Tn) = Mức (T0) + 1. Cấu trúc Dữ liệu ­ Cấu trúc cây 7
  8. Cấu trúc cây Một số khái niệm cơ bản  Độ dài đường đi từ gốc đến nút x : là số nhánh cần đi qua kể từ gốc đến x  Độ dài đường đi tổng của cây : PT PX X T trong đó Px là độ dài đường đi từ gốc đến X.  Độ   dài   đường   đi   trung   bình : PI = PT/n (n là số nút trên cây T).  Rừng  cây: là tập hợp nhiều cây trong đó thứ tự các cây là quan trọng. Cấu trúc Dữ liệu ­ Cấu trúc cây 8
  9. Khái niệm J gốc Cạnh nút Z A B R D Q K A F L Lá Cấu trúc Dữ liệu ­ Cấu trúc cây 9
  10. Cấu trúc cây Một số ví dụ về đối tượng các cấu trúc dạng cây  Sơ đồ tổ chức của một công ty BB­Electronic Corp. R&D Kinh doanh Tài vụ Sản xuất Nội địa Quốc tế TV CD Amplier Châu âu Mỹ Các nước Cấu trúc Dữ liệu ­ Cấu trúc cây 10
  11. Cấu trúc cây Một số ví dụ về đối tượng các cấu trúc dạng cây  Mục lục một quyển sách Student guide Giới thiệu Điểm Môi trường NN LT CT mẫu Bài tập Thực hành Thi Cấu trúc Dữ liệu ­ Cấu trúc cây 11
  12. Cấu trúc cây Nhận xét:  Trong cấu trúc cây không tồn tại chu trình Cấu trúc Dữ liệu ­ Cấu trúc cây 12
  13. Cây nhị phân
  14. Cây nhị phân  Định  nghĩa:  Cây nhị phân là cây mà mỗi nút có tối đa 2 cây con  Trong thực tế thường gặp các cấu trúc có dạng cây nhị phân. Một cây tổng quát có thể biểu diễn thông qua cây nhị phân. Cấu trúc Dữ liệu ­ Cấu trúc cây 14
  15. Cây nhị phân Cây con  Cây con  trái phải Hình ảnh một cây nhị phân Cấu trúc Dữ liệu ­ Cấu trúc cây 15
  16. Cây nhị phân Figure 7.3: Binary tree structure.  Cấu trúc Dữ liệu ­ Cấu trúc cây 16
  17. Cây nhị phân Figure 7.4: Skewed trees.  Cấu trúc Dữ liệu ­ Cấu trúc cây 17
  18. Cây nhị phân  Cây nhị phân dùng để biểu diễn một biểu thức toán học: Cấu trúc Dữ liệu ­ Cấu trúc cây 18
  19. Cây nhị phân Một số tính chất của cây nhị phân i  Số nút nằm ở mức i 2  Chiều  cao  cây  h  là  mức  cao  Mức nhất + 1.  Số nút lá 2h-1, với h là chiều cao của cây.  Chiều cao của cây h log2(số nút trong cây).  Số nút trong cây 2h-1.  Đường đi (path)  Tên  các  node của  quá  trình  đi  từ  node  gốc  theo  các  cây  con  đến một node nào đó. Cấu trúc Dữ liệu ­ Cấu trúc cây 19
  20. Cây nhị phân Biểu diễn cây nhị phân T  Cây nhị phân là một cấu trúc bao gồm các phần tử (nút) được kết nối với nhau theo quan hệ “cha-con” với mỗi cha có tối đa 2 con. Để biểu diễn cây nhị phân ta chọn phương pháp cấp phát liên kết. Ứng với một nút, ta sử dụng một biến động lưu trữ các thông tin sau:  Thông tin lưu trữ tại nút.  Địa chỉ nút gốc của cây con trái trong bộ nhớ.  Địa chỉ nút gốc của cây con phải trong bộ Cấu trúc Dữ liệu ­ Cấu trúc cây 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