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

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT - CHƯƠNG 6: CÂY VÀ CÂY NHỊ PHÂN

Chia sẻ: Lê Trinh Vàng | Ngày: | Loại File: PPT | Số trang:14

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

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ả

Chủ đề:
Lưu

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

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2