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

Chương 3: cây

Chia sẻ: Trung Bùi | Ngày: | Loại File: PPT | Số trang:28

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

Slide bộ môn cấu trúc dữ liệu, giành cho các sinh viên đại học cao đẳng

Chủ đề:

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

Lưu

Nội dung Text: Chương 3: cây

  1. CHƯƠNG 3- CÂY 1
  2. Chương 3: Cây 3.1 Các khái niệm cơ bản 3.2 Cây nhị phân 3.2.1 Định nghĩa và tính chất 3.2.2 Biểu diễn cây nhị phân 3.2.3 Duyệt cây nhị phân 2
  3. 3.1 CÁC KHÁI NIỆM CƠ BẢN Khái niệm cây: – Cây gồm một tập hợp hữu hạn các nút- node – Có một quan hệ thứ tự bộ phận (cha-con) giữa các nút. – Có một nút đặc biệt, không là con của bất cứ nút nào và là tổ tiên của mọi nút trong cây, gọi là nút gốc (root). – Cây không có nút nào gọi là cây rỗng. 3
  4. 3.1 CÁC KHÁI NIỆM CƠ BẢN Bậc – degree – của một nút là số con của nó. Nút lá (leaf) –terminal node – là nút không có con, bậc của nút lá bằng 0. Ngược với nút lá là các nút có con, gọi là nút phân nhánh hay nút trung gian (internal node). Bậc của cây là bậc cao nhất của các nút trong cây. Cây nhị phân là cây bậc 2. Nếu cây có bậc cao hơn 2 ta gọi là cây nhiều nhánh. 4
  5. 3.1 CÁC KHÁI NIỆM CƠ BẢN Mức – level – là đẳng cấp của nút trong mô hình phân cấp. Quy ước nút gốc có mức 1, nếu nút cha có mức i thì nút con có mức i + 1. Chiều cao – height – hay con gọi là chiều sâu – depth – là mức lớn nhất của nút trên cây. Đường đi – path – từ nút p đến nút q trên một cây là dãy nút p = n1,n2,…,nk = q sao cho ni là cha của ni+1. 5
  6. 3.1 CÁC KHÁI NIỆM CƠ BẢN Độ dài đường đi – path length – là số cung nối từng cặp hai nút trên đường đi, nó chính là số nút trừ 1. Cây có thứ tự - ordered tree – là cây mà có xét đến thứ tự giữa các con của một nút. Nói nôm na là có xét đến quan hệ “anh em”. Con trưởng hay con cực trái là một nút là con thứ nhất trong quan hệ thứ tự giữa các nút cùng cha. Em liền kề của một nút là nút đứng ngay sau trong quan hệ thứ tự giữa các nút cùng cha. Rừng – forest- là danh sách hữu hạn cây. 6
  7. 3.2 CÂY NHỊ PHÂN 3.2.1 Định nghĩa và tính chất. 3.2.2 Biểu diễn cây nhị phân. 3.2.3 Duyệt cây nhị phân 7
  8. 3.2.1 ĐỊNH NGHĨA VÀ TÍNH CHẤT Cây nhị phân là cây bậc 2, một nút có nhiều nhất là hai con. Cây nhị phân là cây có xét đến thứ tự, phân biệt con thứ nhất, con thứ hai gọi là con trái và con phải. Ba cây nhị phân này có cùng số nút nhưng có cấu trúc khác nhau 8
  9. 3.2.1 ĐỊNH NGHĨA VÀ TÍNH CHẤT Tinh chât cua cây nhị phân: ́ ́ ̉ – Số lượng tôi đa cua môi nut ở mức i trên ́ ̉ ̃ ́ cây nhị phân là 2i-1 (i ≥ 1). – Số lượng tôi đa cua môi nut trên cây nhị ́ ̉ ̃ ́ phân có chiêu cao h là 2h -1 (h ≥ 1). ̀ ( Chứng minh) 9
  10. 3.2.1 BIỂU DIỄN CÂY NHỊ PHÂN Biểu diễn cây nhị phân bằng cấu trúc mảng. Biểu diễn cây nhị phân bằng danh sách các nút. Biểu diễn cây nhị phân bằng móc nối các nút. 10
  11. 3.2.1 BIỂU DIỄN CÂY NHỊ PHÂN BẰNG CẤU TRÚC MẢNG Với cây nhị phân hoàn chỉnh hoặc đầy đủ trái ta có thể dùng cấu trúc mảng để thể hiện một cây: Xếp liên tiếp các nút của cây vào mảng theo thứ tự từ trên xuống dưới, từ trái sang phải. Trường hợp một nút bị khuyết thì thay bằng giá trị đặc biệt ví dụ giá trị Null. 11
  12. 3.2.1 BIỂU DIỄN CÂY NHỊ PHÂN BẰNG CẤU TRÚC MẢNG Ví du: ̣ A 1 C 3 B 2 D E F G 4 5 6 7 Ta lưu trữ cây nhị phân đây đủ băng 1 vector V theo ̀ ̀ nguyên tăc nut thứ i cua cây được lưu trữ ở V[i] ́ ́ ̉ 12
  13. 3.2.1 BIỂU DIỄN CÂY NHỊ PHÂN BẰNG CẤU TRÚC MẢNG Ví du: ̣ A B C D E F G V[1] V[2] V[3] V[4] V[5] V[6] V[7] 13
  14. 3.2.1 BIỂU DIỄN CÂY NHỊ PHÂN BẰNG CẤU TRÚC MẢNG Phép xác định nút con trái và con phải: nút tại chỉ số mảng i có con trái tại chỉ số 2i và con phải tại chỉ số 2i+1. Phép xác định nút cha: nút tại chỉ số mảng j có cha tại chỉ số [j/2]. Phép duyệt: là phép duyệt mảng. 14
  15. 3.2.1 BIỂU DIỄN CÂY NHỊ PHÂN BẰNG CẤU TRÚC MẢNG Ưu điểm: – Triển khi nhanh. – Truy cập nhanh chóng vào bất kỳ nút nào, chi phí truy cập là đồng đều cho mọi nút. Nhược điểm: – Rất phí chỗ nếu cây “gầy”, khuyết nhiều nút – Khó khăn trong viêc bổ sung, loai bỏ cac phân ̣ ̣ ́ ̀ tử 15
  16. 3.2.2 BIỂU DIỄN CÂY NHỊ PHÂN BẰNG CACH LƯU TRỮ MÓC NỐI ́ Nhược điêm cua viêc lưu trữ cây nhị ̉ ̉ ̣ phân băng câu truc mang là khó và mât ̀ ́ ́ ̉ ́ thời gian trong viêc bổ sung, loai bỏ cac ̣ ̣ ́ nut thường xuyên, để khăc phuc ta có thể ́ ́ ̣ lưu trữ băng cach lưu trữ moc nôi. ̀ ́ ́ ́ Trường hợp nay ta moc nôi trực tiêp nut ̀ ́ ́ ́ ́ cha với nut con băng con tro. ́ ̀ ̉ 16
  17. BIỂU DIỄN CÂY NHỊ PHÂN BẰNG MÓC NỐI CÁC NÚT Cấu trúc của một nút gồm 3 trường: – Data: chứa dữ liệu; – Left: trỏ đến nút con trái – Right: trỏ đến nút con phải typedef int element_type; typedef struct node { element_type element; struct node *left, *right; } NODE; 17
  18. BIỂU DIỄN CÂY NHỊ PHÂN BẰNG MÓC NỐI CÁC NÚT Cây sẽ được trỏ bằng một con trỏ đến nút gốc cây. Kiểu Ref là kiểu con trỏ đến 1 nút; 18
  19. BIỂU DIỄN CÂY NHỊ PHÂN BẰNG MÓC NỐI CÁC NÚT Phép toán cơ sở: – Phép xác định con trái: V=*V.Left – Phép xác định con phải: V=*V.right – Phép xác định nút cha: rất khó xác định nên phải thêm một con trỏ cha nữa trong cấu trúc. – Phép duyệt cây được trình bày sau: 19
  20. BIỂU DIỄN CÂY NHỊ PHÂN BẰNG MÓC NỐI CÁC NÚT Ưu điểm: – Rất linh hoạt đối với các phép toán thêm vào, lấy ra một nút, một cây con. – Không lãng phí vùng nhớ nếu cây “gầy” Nhược điểm: – Rất phức tạp khi biểu diễn. 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