Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4 - GV. Nguyễn Minh Thành

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

Thêm vào BST

Báo xấu

72
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chương 4 Cây nhị phân thuộc bài giảng cấu trúc trúc dữ liệu và giải thuật nhằm trình bày về khái niệm, định nghĩa và tính chất của cấu trúc cây, các thuật ngữ liên quan và các ví dụ về cấu trúc cây, cây nhị phân, cách lưu trữ cây, 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 - GV. Nguyễn Minh Thành

Chương 4 : CÂY NHỊ PHÂN Giảng viên : Nguyễn Minh Thành Email : thanhnm.itc@itc.edu.vn
Nội Dung I. Cấu Trúc Cây 1. Khái việm và ví dụ 2. Định nghĩa 3. Các tính chất 4. Các thuật ngữ liên quan II. Cây Nhị Phân 1. Định nghĩa 2. Cách thức lưu trữ cây III. Cây Nhị Phân Tìm Kiếm 1. Ý nghĩa 2. Định nghĩa 3. Ví dụ 4. Cài đặt 2
I. Cấu Trúc Cây 1. Khái việm và ví dụ 2. Định nghĩa 3. Các tính chất 4. Các thuật ngữ liên quan 3
I.1 Khái Niệm và Ví Dụ  Ví dụ 1: bài toán đưa thư  Trên thế giới hơn có ~ 10 tỉ người  Thành, khoa CNTT, CĐ CNTT, TpHCM, Việt Nam.  Cách tìm ra “Thành” nhanh nhất ?  Sử dụng mảng ?  Sứ dụng danh sách liên kết (linked list) ? 4
I.1 Khái Niệm và Ví Dụ  Ví dụ 1: bài toán đưa thư 5
I.1 Khái Niệm và Ví Dụ  Cây là một cấu trúc dữ liệu quan trọng để biểu diễn và lưu trữ dữ liệu trong bộ nhớ chính và mang tính “kế thừa”  Tính kế thừa :  Các node con phải liên quan đến node cha  Các cây mang tính kế thừa :  Cây gia phả  Cây phân cấp các loài (sinh vật) 6
I.2 Định Nghĩa  Một cây (Tree) là  Một tập hợp các phần tử, gọi là các node p1,p2,…,pN  Nếu N=0, cây gọi là cây rỗng (NULL)  Nếu N>0 :  Tồn tại duy nhất một node pk duy nhất gọi là gốc cây  Các nút còn lại được chia thành m tập không giao nhau : T1, T2, … TM  Mỗi Ti cây con của cây 7
I.2 Định Nghĩa 8
I.2 Định Nghĩa 9
I.2 Định Nghĩa 10
I.3 Các Tính Chất Của Cây  Nút gốc không có nút cha  Mỗi nút khác chỉ có 1 nút cha  Mỗi nút có thể có nhiều nút con  Không có chu trình 11
I.4 Các Thuật Ngữ Liên Quan  Node : là 1 phần tử trong cây. Mỗi node chứa 1 dữ liệu bất kỳ  Nhánh : là đoạn nối giữa 2 nút  Node cha  Node con  Nút anh em : là những node có cùng nút cha  Bậc của 1 node pi : là số node con của pi  Tìm bậc của các node trên cây T trong ví dụ trên ?  Node gốc : node không có node cha  Node lá (node ngoài) : node có bậc = 0 (không có node con)  Node trong (node nhánh) : là node có node con và node cha  Cây con  Trong cây T có bao nhiêu cây con ? 12
I.4 Các Thuật Ngữ Liên Quan  Bậc của cây : là bậc lớn nhất của các node trong cây  Bậc () = max { bậc(pi) / pi  }  Tìm bậc của cây T ?  Đường đi (path) giữa node pi và pj : là dảy các nút liên tiếp từ pi đến pj sao cho giữa 2 node kề nhau đều có nhánh.  Độ dài đường đi từ node pi và pj : là số nhánh cần đi qua từ pi đến pj . 13
I.4 Các Thuật Ngữ Liên Quan  Mức (level)  Mức (p)=0 nếu p là gốc  Mức (p) = mức (cha(p)) +1 nếu p không phải gốc  Chiều cao của cây (hT): đường đi dài nhất từ node gốc đến node lá  hT = max { path (gốc, pi) / pi là node lá  }  Tính chiều cao của cây T trong ví dụ trên 14
I.4 Các Thuật Ngữ Liên Quan  Mức (level)  Mức (p)=0 nếu p là gốc  Mức (p) = mức (cha(p)) +1 nếu p không phải gốc  Chiều cao của cây (hT): đường đi dài nhất từ node gốc đến node lá  hT = max { path (gốc, pi) / pi là node lá  }  Tính chiều cao của cây T trong ví dụ trên 15
II. Cây Nhị Phân 1. Định nghĩa 2. Cách thức lưu trữ cây 16
II.1 Định Nghĩa  Cây Nhị Phân là cây có bậc = 2  Bậc của các nút trong
II.1 Định Nghĩa  Độ cao của cây nhị phân có N node:  hT(max) = N  hT(min) = [log2N] + 1 18
II.2 Lưu Trữ Cây  Có 2 cách tổ chức cây nhị phân :  Lưu trữ bằng mảng  Lưu trữ bằng con trỏ cấu trúc  Chi tiết ở phần Cây Nhị Phân Tìm Kiếm 19
III. Cây Nhị Phân Tìm Kiếm 1. Định nghĩa 2. Ý nghĩa 3. Cài đặt 20