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

Chương 7:Cấu trúc cây

Chia sẻ: Nguyen Ha | Ngày: | Loại File: PDF | Số trang:76

Thêm vào BST
Báo xấu
60
lượt xem 6
download
 
  Download Vui lòng tải xuống để xem tài liệu đầ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 T, T2 , ... , Tn 1 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+. Quan hệ này người ta còn gọi là 1 quan hệ cha-con.

Chủ đề:

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

Lưu

Nội dung Text: Chương 7:Cấu trúc cây

  1. CHAPTER 7: 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 Caáu truùc Döõ lieäu - Caáu truùc caâ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 T, T2 , ... , Tn 1 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+. Quan hệ này người ta còn gọi là 1 quan hệ cha-con. Caáu truùc Döõ lieäu - Caáu truùc caây 4
  5. Cấu trúc cây Caáu truùc Döõ lieäu - Caáu truùc caây 5
  6. Cấu trúc cây Caáu truùc Döõ lieäu - Caáu truùc caâ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 T, T, T, ... , Tn là các cây con của T0 1 2 3  Mức (T) = Mức (T) = ... = Mức (Tn) = Mức (T) + 1. 1 2 0 Caáu truùc Döõ lieäu - Caáu truùc caâ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 : P  T  XT PX 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. Caáu truùc Döõ lieäu - Caáu truùc caâ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á Caáu truùc Döõ lieäu - Caáu truùc caâ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- BB-Electronic Corp. R&D Kinh doanh aøi Taøi vuï aûn Saûn xuaát Noäi ñòa Quoác teá TV CD Amplier haâu Chaâu aâu Myõ aùc Caùc nöôùc Caáu truùc Döõ lieäu - Caáu truùc caâ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 thieäu Ñieåm Moâi tröôøng NN LT CT maãu aøi Baøi taäp höïc Thöïc haønh Thi Caáu truùc Döõ lieäu - Caáu truùc caây 1
  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  Tổ chức 1 cấu trúc cây cho phép truy cập nhanh đến các phần tử của nó. Caáu truùc Döõ lieäu - Caáu truùc caâ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. Caáu truùc Döõ lieäu - Caáu truùc caâ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 Caáu truùc Döõ lieäu - Caáu truùc caây 15
  16. Cây nhị phân Figure .: inary 73 B tree structure. Caáu truùc Döõ lieäu - Caáu truùc caây 16
  17. Cây nhị phân Figure .: kewed 74 S trees. Caáu truùc Döõ lieäu - Caáu truùc caâ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: Caáu truùc Döõ lieäu - Caáu truùc caâ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á  h-1, với h là chiều 2 cao của cây.  Chiều cao của cây h  log(số2 nút trong cây).  Số nút trong cây  h-. 2 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 đó. đó. Caáu truùc Döõ lieäu - Caáu truùc caâ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ộ Caáu truùc Döõ lieäu - Caáu truùc caây nhớ. 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