Cấu trúc cây - Trees ! ! ! ! Cây và các ứng dụng của cây Một số dạng cây

Chia sẻ: Nguyễn Hữu Thiên Sơn | Ngày: | Loại File: PDF | Số trang:52

Thêm vào BST

Báo xấu

383
lượt xem 64
download

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

Cấu trúc cây - Trees ! ! ! ! Cây và các ứng dụng của cây Một số dạng cây thường dùng: cây nhị phân, cây nhị phân tìm kiếm, cây cân bằng (AVL) Các thuật toán trên cây Đánh giá thuật toán 1 Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Nội dung trình bày ! ! ! ! Các khái niệm và thuật ngữ cơ bản Tổng quan về cây nhị phân (Binary Tree) Cây nhị phân tìm kiếm (BST – Binary Search Tree) Cây nhị phân tìm kiếm cân bằng (AVL Tree) Spring 2004 Data Structure & Algorithm - Nguyen...

Chủ đề:

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

Lưu

Nội dung Text: Cấu trúc cây - Trees ! ! ! ! Cây và các ứng dụng của cây Một số dạng cây

Cấu trúc cây - Trees Cây và các ứng dụng của ! cây Một số dạng cây thường ! dùng: cây nhị phân, cây nhị phân tìm kiếm, cây cân bằng (AVL) Các thuật toán trên cây ! Đánh giá thuật toán ! Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 1 Nội dung trình bày Các khái niệm và thuật ngữ cơ bản ! Tổng quan về cây nhị phân (Binary Tree) ! Cây nhị phân tìm kiếm (BST – Binary ! Search Tree) Cây nhị phân tìm kiếm cân bằng (AVL ! Tree) Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 2 1
Các khái niệm và thuật ngữ cơ bản Các ví dụ ! Định nghĩa cấu trúc cây ! Các thuật ngữ liên quan ! Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 3 Các khái niệm và thuật ngữ cơ bản Các ví dụ Ví dụ 1: bài toán đưa thư ! Trên thế giới hiện có 6 tỉ người ! Tuấn, khoa CNTT, ĐH KHTN, Tp.HCM, ! Việt nam Cách tìm ra “Tuấn” nhanh nhất ? ! Sử dụng mảng (array) ? ! Sử dụng danh sách liên kết (linked list) ? ! Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 4 2
Các khái niệm và thuật ngữ cơ bản Các ví dụ Trái đất China Korea Vietnam ... ... Hà nội Tp.HCM ... ... ĐH.KHTN ... ... ĐH.BK Khoa CNTT ... ... Khoa Toán “Tuấn” Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 5 Các khái niệm và thuật ngữ cơ bản Các ví dụ Ví dụ 2: cây biểu thức (a-b)*(c/d) ! * 0 / d c b a Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 6 3
Các khái niệm và thuật ngữ cơ bản Các ví dụ Cây là 1 cấu trúc dữ liệu quan trọng để ! biểu diễn tính “kế thừa” Các cây mô tả tính kế thừa: ! Cây gia phả (trong các dòng họ) ! Cây phân cấp các loài (trong sinh vật) ! … ! Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 7 Các khái niệm và thuật ngữ cơ bản Định nghĩa cấu trúc cây Một cây (Tree) là: ! Một tập các phần tử, gọi là các nút (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 1 nút pk gọi là gốc của 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 là 1 cây con của cây ! Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 8 4
Các khái niệm và thuật ngữ cơ bản Định nghĩa cấu trúc cây Nút gốc Cây con a c d k Cây con j e g i h f Cây rỗng b (NULL) Cây con Cây Cây con Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 9 Các khái niệm và thuật ngữ cơ bản Định nghĩa cấu trúc cây Cây a c j e d g k i h f Cây con Cây con b Cây con Cây con Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 10 5
Các khái niệm và thuật ngữ cơ bản Định nghĩa cấu trúc cây Cây a c j g k Cây con i b h f e d Cây con Cây con Cây con Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 11 Các khái niệm và thuật ngữ cơ bản Định nghĩa cấu trúc cây 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 ! Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 12 6
Các khái niệm và thuật ngữ cơ bản Các thuật ngữ liên quan Nút (Node): là 1 phần tử trong cây. Mỗi nút có ! thể chứa 1 dữ liệu bất kỳ Nhánh (Branch): là đoạn nối giữa 2 nút ! Nút cha (Parent node) ! Nút con (Child node) ! Nút anh em (sibling nodes): là những nút có cùng ! nút cha Bậc của 1 nút pi: là số nút con của pi ! Bậc (a) = 4; Bậc (j) = 3; Bậc (g) = 2; ! Bậc (k) = 1; Bậc (c) = 0 ! Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 13 Các khái niệm và thuật ngữ cơ bản Các thuật ngữ liên quan Nút gốc (Root node): nút không có nút cha ! Nút lá (Leaf node, hay nút ngoài – External ! node): nút có bậc = 0 (không có nút con) Nút nội (Internal node): là nút có nút cha ! và có nút con Cây con (Subtree) ! Trắc nghiệm: có bao nhiêu cây con trong cây ! ? Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 14 7
Các khái niệm và thuật ngữ cơ bản 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 nút ! trong cây Bậc () = max {bậc (pi) / pi ∈ } ! Bậc của cây ? ! Đường đi (Path) giữa nút pi đến nút pj: là ! dảy các nút liên tiếp từ pi đến pj sao cho giữa hai nút kề nhau đều có nhánh Path(a, d) ? ! Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 15 Các khái niệm và thuật ngữ cơ bản Các thuật ngữ liên quan Mức (Level): ! Mức (p) = 0 nếu p = root ! Mức (p) = 1 + Mức (Cha (p)) nếu p!=root ! Chiều cao của cây (Height - hT): đường đi ! dài nhất từ nút gốc đến nút lá hT = max {Path(root, pi) / pi là nút lá ∈ } ! hT ? ! Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 16 8
Các khái niệm và thuật ngữ cơ bản Các thuật ngữ liên quan Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 17 Các khái niệm và thuật ngữ cơ bản Các thuật ngữ liên quan Cây hoàn chỉnh (Complete tree) với h mức: là 1 ! cây thoả các điều kiện Những nút từ mức 0 đến mức h-1 đều đầy đủ ! Những nút ở mức h được thêm vào cây từ trái sang ! phải Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 18 9
Các khái niệm và thuật ngữ cơ bản Các thuật ngữ liên quan Cây hoàn chỉnh ? Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 19 Các khái niệm và thuật ngữ cơ bản Các thuật ngữ liên quan Cây hoàn chỉnh ? Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 20 10
Các khái niệm và thuật ngữ cơ bản Các thuật ngữ liên quan Cây đầy đủ (Full tree): là 1 cây thoả ! Tất cả các nút lá đều nằm trên cùng 1 mức ! Tất cả những nút khác có cùng bậc với cây ! Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 21 Các khái niệm và thuật ngữ cơ bản Các thuật ngữ liên quan Cây đầy đủ ? Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 22 11
Các khái niệm và thuật ngữ cơ bản Các thuật ngữ liên quan Cây đầy đủ ? Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 23 Các khái niệm và thuật ngữ cơ bản Các thuật ngữ liên quan Cây đầy đủ ? Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 24 12
Các khái niệm và thuật ngữ cơ bản Các thuật ngữ liên quan Mức h của cây đầy đủ bậc d có dh nút ! VD. mức h=2 của cây bậc 3 có bao nhiêu nút ? ! h mức đầu tiên của cây đầy đủ bậc d có số nút ! là: 1 + d + d2 + d3 + … + dh-1 = (dh - 1)/(d – 1) ! 3 mức đầu tiên của cây bậc 3 có bao nhiêu nút ? ! Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 25 Tổng quan về cây nhị phân Định nghĩa ! Cách thức lưu trữ cây ! Các phương pháp duyệt cây ! Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 26 13
Tổng quan về cây nhị phân Định nghĩa Cây nhị phân là cây có bậc = 2 ! * 0 / d c b a Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 27 Tổng quan về cây nhị phân Định nghĩa Độ cao của cây nhị phân có N nút: ! hT(max) = N ! hT(min) = [log2N] + 1 ! Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 28 14
Tổng quan về cây nhị phân Định nghĩa Trắc nghiệm: Hãy vẽ tất cả các cây nhị ! phân có 3 nút ? Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 29 Tổng quan về cây nhị phân Cách thức 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 ! Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 30 15
Tổng quan về cây nhị phân Cách thức lưu trữ cây, sử dụng mảng Con trái Con phải # Nút 0 * 1 2 * 1 - 3 4 2 / 5 6 0 3 a -1 -1 / 4 b -1 -1 5 c -1 -1 d c b a 6 d -1 -1 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 31 Tổng quan về cây nhị phân Cách thức lưu trữ cây, sử dụng mảng // Định nghĩa các cấu trúc dữ liệu typedef struct tagBT_NODE { int Data; // chỉ số nút con trái int Left; // chỉ số nút con phải int Right; } BT_NODE; // binary tree node // cây nhị phân có N nút BT_NODE tree[N]; Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 32 16
Tổng quan về cây nhị phân Cách thức lưu trữ cây, sử dụng con trỏ BIN_TREE pRoot Count Data pLeft pRight Nút gốc của Nút gốc của cây con phải BT_NODE cây con trái Data Data pLeft pRight pLeft pRight Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 33 Tổng quan về cây nhị phân Cách thức lưu trữ cây, sử dụng con trỏ // Định nghĩa các cấu trúc dữ liệu typedef struct tagBT_NODE { int Data; tagBT_NODE *pLeft; // con trỏ đến nút con trái tagBT_NODE *pRight; // con trỏ đến nút con phải } BT_NODE; // binary tree node Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 34 17
Tổng quan về cây nhị phân Cách thức lưu trữ cây, sử dụng con trỏ // Định nghĩa các cấu trúc dữ liệu … (tiếp theo) typedef struct BIN_TREE { Count; // Số nút trong cây int *pRoot; // con trỏ đến nút gốc BT_NODE }; // binary tree Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 35 Tổng quan về cây nhị phân Các phương pháp duyệt cây Có 3 cách duyệt cây: ! Duyệt gốc trước (Pre-Order) NLR ! Duyệt gốc giữa (In-Order) LNR ! Duyệt gốc sau (Post-Order) LRN ! Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 36 18
Tổng quan về cây nhị phân Các phương pháp duyệt cây void NLR(const BT_NODE *pCurr) { if (pCurr==NULL) return; “Xử lý nút gốc pCurr” NLR(pCurr->pLeft); NLR(pCurr->pRight); } Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 37 Tổng quan về cây nhị phân Các phương pháp duyệt cây Minh họa cách duyệt “gốc trước” Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 38 19
Tổng quan về cây nhị phân Các phương pháp duyệt cây void LNR(const BT_NODE *pCurr) { if (pCurr==NULL) return; LNR(pCurr->pLeft); “Xử lý nút gốc pCurr” LNR(pCurr->pRight); } Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 39 Tổng quan về cây nhị phân Các phương pháp duyệt cây void LRN(const BT_NODE *pCurr) { if (pCurr==NULL) return; LRN(pCurr->pLeft); LRN(pCurr->pRight); “Xử lý nút gốc pCurr” } Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 40 20