CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT - CHƯƠNG 6: CÂY VÀ CÂY NHỊ PHÂN
lượt xem 15
download
Tham khảo bài thuyết trình 'cấu trúc dữ liệu và giải thuật - chương 6: cây và cây nhị phân', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT - CHƯƠNG 6: CÂY VÀ CÂY NHỊ PHÂN
- CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Cấu trúc dữ liệu 1 vá thuật giải Click To Edit 1 NỘMaster CÂY VÀ CÂY NHỊ PHÂN I DUNGTitle Style
- Click Định NghĩaTo Edit Cây Master Title Style 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ó một nút đặc biệt gọi là nút gốc, các nút còn lại được chia thành Cấu trúc dữ liệu 1 vá thuật giải những tập rời nhau T1, T2, …,Tn theo quan hệ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 phân cấp, trong đó Ti cũng là 1 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 gọi là quan hệ cha – con. 2
- MộtClick ToNiEdit Số Khái ệm Master Title Style • 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 • 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 . Cấu trúc dữ liệu 1 vá thuật giải • Mức của một nút: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 – 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. • Độ 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. 3
- Ví DClick ụ 1 TổTo ChEdit ức DạMaster ng Cây Title Style BB-Electronic Corp. R&D Kinh doanh Taøi vuï Saûn xuaát Cấu trúc dữ liệu 1 vá thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Noäi ñòa Quoác teá TV CD Amplier Chaâu aâu Myõ Caùc nöôùc 4
- CâyClick To Edit Nhị Phân Master Title Style • Mỗi nút có tối đa 2 cây con Caây Caây con con Cấu trúc dữ liệu 1 vá thuật giải traùi phaûi CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 5
- MộtClick ToCh Số Tính Edit ất CMaster Title ủa Cây Nh Style ị Phân • Số nút nằm ở mức i ≤ 2i. • 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 ≥ Cấu trúc dữ liệu 1 vá thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 log2(N) – N = số nút trong cây • Số nút trong cây ≤ 2h- 1. 6
- CấuClick To Trúc D Edit ữ Liệu CMaster Title ủa Cây Nh Style ị Phân typedef struct tagTNode { Data Key; struct tagTNode *pLeft; Key struct tagTNode *pRight; }TNode; Cấu trúc dữ liệu 1 vá thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 typedef TNode *TREE; 7
- Ví Dụ Cây Được Tổ Chức Trong Bộ Nhớ Click Trong To Edit Master Title Style 1f 2f 6 3f 3f 2f Cấu trúc dữ liệu 1 vá thuật giải 7f 9 N CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 N 4 5f 5f 7f N 5 N N 8 N 8
- DuyClick ệt CâyTo NhịEdit PhânMaster Title Style Có 3 trình tự thăm gốc : Duyệt trước Duyệt giữa Duyệt sau Cấu trúc dữ liệu 1 vá thuật giải Độ phức tạp O (log2(h)) CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Trong đó h là chiều cao cây 9
- Ví DClick ụ Kết To QuảEdit CủaMaster Title Phép Duy Style ệt Cây 9 2 8 6 1 5 7 Cấu trúc dữ liệu 1 vá thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 10 3 12 4 • NLR: 9, 2, 6, 1, 10, 8, 5, 3, 7, 12, 4. • LNR: 6, 2, 10, 1, 9, 3, 5, 8, 12, 7, 4. • Kết quả của phép duyệt : LRN, NRL,LRN, 10
- DuyClick To ệt Trướ c Edit Master Title Style void NLR(TREE Root) { if (Root != NULL) { ; //Xử lý tương ứng theo nhu cầu Cấu trúc dữ liệu 1 vá thuật giải NLR(Root->pLeft); CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 NLR(Root->pRight); } } 11
- DuyClick ệt GiữTo a Edit Master Title Style void LNR(TREE Root) { if (Root != NULL) { LNR(Root->pLeft); Cấu trúc dữ liệu 1 vá thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 ; // Xử lý tương ứng theo nhu cầu LNR(Root->pRight); } } 12
- DuyClick ệt SauTo Edit Master Title Style void LRN(TREE Root) { if (Root != NULL) { LRN(Root->pLeft); Cấu trúc dữ liệu 1 vá thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 LRN(Root->pRight); ; // Xử lý tương ứng theo nhu cầu } } 13
- BiểuClick To TEdit Diễn Cây Master ổng Quát BằngTitle Cây NhStyle ị Phân A B E C A Cấu trúc dữ liệu 1 vá thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 F H D B C D G I J E F G H I J 14
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Giáo trình cấu trúc dữ liệu và giải thuât part 1
16 p | 825 | 365
-
Giáo trình cấu trúc dữ liệu và giải thuât part 2
16 p | 551 | 286
-
Bài giảng Cấu trúc dữ liệu - Bài 1:Tổng quan về cấu trúc dữ liệu và giải thuật
47 p | 175 | 17
-
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Các khái niệm cơ bản về Cấu trúc dữ liệu và giải thuật
20 p | 44 | 8
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây đỏ đen - Bùi Tiến Lên
25 p | 81 | 8
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu
193 p | 58 | 7
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (Trường Đại học Hồng Bàng )
62 p | 159 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (2016)
62 p | 94 | 6
-
Giáo trình Cấu trúc dữ liệu và giải thuật - CĐ Nghề Đắk Lắk
60 p | 45 | 6
-
Giáo trình Cấu trúc dữ liệu và giải thuật (Ngành: Công nghệ thông tin - Cao đẳng) - Trường Cao đẳng Xây dựng số 1
77 p | 12 | 5
-
Bài giảng Cấu trúc dữ liệu và giải thuật – Chương 1: Tổng quan về giải thuật và cấu trúc dữ liệu
10 p | 66 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 – Trần Minh Thái (2017)
67 p | 106 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Một số khái niệm cơ bản về cấu trúc dữ liệu và giải thuật
12 p | 91 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Tổng quan - Nguyễn Đức Cương
6 p | 99 | 4
-
Giáo trình Cấu trúc dữ liệu và giải thuật (Nghề: Công nghệ thông tin - Trung cấp) - Trường Trung cấp Công nghệ và Du lịch Hà Nội
59 p | 15 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - Th.S Thiều Quang Trung
41 p | 68 | 3
-
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Cấu trúc dữ liệu và giải thuật
42 p | 55 | 3
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Ngô Quang Thạch
49 p | 63 | 3
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