goupee.vn goupee.com Đại Học Bách Khoa Hà Nội Viện Điện Tử - Viễn Thông LẬP TRÌNH Phần 3: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Chương 11: Cấu trúc cây cuu duong than cong . com fb.com/goupee.vn Bộ Môn ĐT-KTMT - Viện ĐT-VT. Chương 11: Cấu trúc cây 1 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Nội dung goupee.com • Các khái niệm cơ bản – Mô tả cấu trúc cây (tree) – Các khái niệm cơ bản trong cây – Các tính chất cơ bản – Các thao tác cơ bản • Cây nhị phân (binary tree) – Khái niệm – Phân loại • Các trường hợp đặc biệt – Cây suy biến (degenerate binary tree)cuu duong than cong . com – Cây đầy đủ (full binary tree) – Cây hoàn chỉnh (complete binary tree) fb.com/goupee.vn Bộ Môn ĐT-KTMT - Viện ĐT-VT. Chương 11: Cấu trúc cây 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Nội dung goupee.com • Một số tính chất của cây nhị phân • Cài đặt cây nhị phân – Dùng cấu trúc lưu trữ móc nối – Dùng cấu trúc lưu trữ tuần tự • Duyệt cây nhị phân – Phép thăm và duyệt – Các phép duyệt cây • Duyệt theo thứ tự trước • Duyệt theo thứ tự giữa • Duyệt theo thứ tự saucuu duong than cong . com • Duyệt theo từng mức (tầng) – Một số ứng dụng của cấu trúc cây nhị phân fb.com/goupee.vn Bộ Môn ĐT-KTMT - Viện ĐT-VT. Chương 11: Cấu trúc cây 3 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Các khái niệm cơ bản goupee.com • Mô tả cấu trúc cây (tree) list head – Các phần tử hay các nút • nút (node) • gốc (root) – Các quan hệ phân cấp giữa các cặp nút. tail • nhánh • quan hệ cha-con tree root • quan hệ cấp trên-cấp dưới – Cây rỗng nodes parent cuu duong than cong . com child Leaves (childless nodes) fb.com/goupee.vn Bộ Môn ĐT-KTMT - Viện ĐT-VT. Chương 11: Cấu trúc cây 4 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Các khái niệm cơ bản goupee.com • Giới thiệu chung – Ví dụ – Ví dụ về các tiêu đề – Ví dụ thư mục trong windows C Users 4 Windows Temp Program Files 4.1 4.2 cuu duong than cong . com 4.1.1 4.1.2 4.1.3 4.2.1 4.2.2 fb.com/goupee.vn Bộ Môn ĐT-KTMT - Viện ĐT-VT. Chương 11: Cấu trúc cây 5 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Các khái niệm cơ bản goupee.com • Giới thiệu chung – Khái niệm – Kích thước cây (size): là số nút có trên cây S(T) – Cấp của một nút (degree): là số con mà nút này có d(A) – Cấp của cây: d(T) • là cấp của nút có số con nhiều nhất trên cây 1 – Nút nhánh (node-branch node) • là nút có ít nhất một con • tên gọi khác: nút trong, nút không tận cùng 2 7 – Nút lá (leaf node or terminal node) • là nút không có con nào • tên gọi khác: nút ngoài, nút tận cùng 3 4 5 6 – Mức của một nút (level): L(A)cuu duong than cong . com • Nếu A là nút gốc thì L(A) = 1 8 • Nếu B là cha của A thì L(A) = L(B) +1 fb.com/goupee.vn Bộ Môn ĐT-KTMT - Viện ĐT-VT. Chương 11: Cấu trúc cây 6 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Các khái niệm cơ bản goupee.com • Giới thiệu chung – Khái niệm 1 – Chiều cao của một nút (height) – Độ sâu (degree) 2 7 • h(A) = L(A)-1 – Chiều cao của cây: h(T) • là chiều cao của nút cao nhất trong cây 3 4 5 6 – Đường đi giữa nút gốc và một nút khác (path): p(A) • là dãy các nhánh nối từ gốc đến nút đó 8 – Độ dài đường đi (path length): PL(A) • là tổng độ dài các nhánh tạo thành đường đi • Thực tế: nhánh thường là khái niệm logic biểu diễn quan hệ phân cấp giữacuu duong than cong . com một cặp nút, nên không có độ dài. Vì vậy, thường quy ước độ dài của tất cả các nhánh trong một cây đều bằng 1 (đơn vị). Khi đó, độ dài đường đi tương đương với chiều cao fb.com/goupee.vn Bộ Môn ĐT-KTMT - Viện ĐT-VT. Chương 11: Cấu trúc cây 7 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Các khái niệm cơ bản goupee.com • Giới thiệu chung – Khái niệm – Cây con – Cây được sắp (có thứ tự - ordered tree) • Có thứ tự (ordered tree): có trật tự tuyến tính giữa các nút con • Không có thứ tự (unordered tree): không có trật 1 tự tuyến tính – Rừng (forest) • là cấu trúc bao gồm nhiều cây 2 7 • có thể có rừng rỗng cuu duong than cong . com 6 3 4 5 8 fb.com/goupee.vn Bộ Môn ĐT-KTMT - Viện ĐT-VT. Chương 11: Cấu trúc cây 8 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Các khái niệm cơ bản goupee.com • Giới thiệu chung – Các tính chất cơ bản 1 – Số nút của cây bằng số nhánh cộng 1 – Cây có tính chất đệ quy. Tính chất này sẽ được sử dụng trong nhiều thao tác sau này. 2 7 – Cây là một cấu trúc dữ liệu động, tức là kích thước của nó (số nút của cây) có thể thay đổi. 3 4 5 6 – Cấu trúc cây không còn cấu trúc tuyến tính nữa mà là cấu trúc phân cấp. 8 – Chỉ tồn tại duy nhất một đường đi từ gốc đến một nút khác.cuu duong than cong . com fb.com/goupee.vn Bộ Môn ĐT-KTMT - Viện ĐT-VT. Chương 11: Cấu trúc cây 9 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Các khái niệm cơ bản goupee.com • Giới thiệu chung – Các thao tác cơ bản trên cây – Khởi tạo: chuẩn bị CTLT để lưu trữ cấu trúc cây – Bổ sung một nút mới vào cây 1 • Xác định vị trí • Xác định quan hệ nút mới và nút tại vị trí bổ sung – Lấy ra một nút 2 7 • Xác định vị trí • Cấu trúc lại cây – Tìm cha mỗi đỉnh 3 4 5 6 • Parent(x) – Tìm con bên trái ngoài cùng (con trưởng) của mỗi đỉnh 8 • EldestChild(x)cuu duong than cong . com – Tìm em liền kề mỗi đỉnh • NextSibling(x) fb.com/goupee.vn Bộ Môn ĐT-KTMT - Viện ĐT-VT. Chương 11: Cấu trúc cây 10 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Các khái niệm cơ bản goupee.com • Giới thiệu chung – Các thao tác cơ bản trên cây – Duyệt cây • Preorder: 1, 2, 4, 3, 5, 7, 6, 8, 9 a => a, b, c, d 1 b c d • Inorder: 4, 2, 3, 5, 1, 8, 6, 7, 9 : Thường chỉ dùng với cây NP b 2 7 a c d => a, b, c, d • Postorder: 4, 3, 5, 2, 8, 6, 9, 7, 1cuu duong than cong . com4 3 5 6 9 d => a, b, c, d 8 a b c fb.com/goupee.vn Bộ Môn ĐT-KTMT - Viện ĐT-VT. Chương 11: Cấu trúc cây 11 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Các khái niệm cơ bản goupee.com • Giới thiệu chung – Các thao tác cơ bản trên cây – Ghép cây • MergeTree(T1,T2,x): x=1 • Vai trò của x: nút ghép, gốc của T2 sẽ là con của x, và ta có thể ghép trái, ghép phải – Cắt cây 1 • CutTree(T1,x,T2): x=2 1 2 2 7 7 3 4 5cuu duong than cong . com T2 T1 6 3 4 5 6 8 8 fb.com/goupee.vn Bộ Môn ĐT-KTMT - Viện ĐT-VT. Chương 11: Cấu trúc cây 12 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Cây nhị phân (binary tree) goupee.com • Mô tả cây nhị phân và các khái niệm cơ bản – Cây có thứ tự và là cây cấp hai, tức là mỗi nút có tối đa 2 con. – Hai con của một nút được phân biệt thứ tự và quy ước nút trước gọi là nút con trái và nút sau được gọi là nút con phải – Khi biểu diễn cây nhị phân, ta cũng 1 cần có sự phân biệt rõ ràng giữa con trái và con phải, nhất là khi nút chỉ có một con. 2 3 cuu duong than cong . com4 5 6 7 8 fb.com/goupee.vn Bộ Môn ĐT-KTMT - Viện ĐT-VT. Chương 11: Cấu trúc cây 13 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Cây nhị phân (binary tree) goupee.com • Mô tả cây nhị phân và các khái niệm cơ bản – Loại nút: • Nút có đủ hai con được gọi là nút kép: 2, 3 • Nút chỉ có một con gọi là nút đơn: 7 • Nút không có con được gọi là nút lá: 4, 5, 6, 8 – Cây con có gốc là nút con trái/phải được 1 Phải gọi là cây con trái/phải. (Right) Trái (Left) 2 3 cuu duong than cong . com4 5 6 7 8 fb.com/goupee.vn Bộ Môn ĐT-KTMT - Viện ĐT-VT. Chương 11: Cấu trúc cây 14 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vn Cây nhị phân (binary tree) goupee.com • Các thao tác cơ bản – Cây nhị phân cũng có các thao tác cơ bản tương tự như của cây tổng quát.: • Khởi tạo: chuẩn bị CTLT để lưu trữ cấu trúc cây • Bổ sung một nút mới vào cây • Lấy ra một nút • Tìm cha mỗi đỉnh: Parent(x) • Tìm con bên trái của mỗi đỉnh: LeftChild(x) • Tìm con bên phải của mỗi đỉnh: RightChild(x) • Ghép cây • Cắt cây • Duyệt cây cuu duong than cong . com fb.com/goupee.vn Bộ Môn ĐT-KTMT - Viện ĐT-VT. Chương 11: Cấu trúc cây 15 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vnCây NP - Các trường hợp đặc biệtgoupee.com • Cây suy biến (degenerate binary tree) – Là cây nhị phân mà mỗi nút chỉ có tối đa một con. Nó đã bị suy biến về cấu trúc danh sách. – Như vậy, danh sách chỉ là dạng suy biến, trường hợp đặc biệt của cấu trúc cây, và nó vẫn giữa được tính chất đệ quy của cây 1 1 1 2 2 2 cuu duong than cong . com3 3 3 4 fb.com/goupee.vn Bộ Môn ĐT-KTMT - Viện ĐT-VT. Chương 11: Cấu trúc cây 16 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vnCây NP - Các trường hợp đặc biệtgoupee.com • Cây đầy đủ (full binary tree) – Là cây nhị phân có số nút tối đa ở tất cả các mức. Tức là ở mức i sẽ có đúng 2i-1 nút. Do đó, nếu cây nhị phân có chiều cao h thì kích thước của nó là: S(T) = 20+21+…+2h = 2h+1-1 ; 1 1 2 3 2 3 cuu duong than cong . com4 5 6 7 fb.com/goupee.vn Bộ Môn ĐT-KTMT - Viện ĐT-VT. Chương 11: Cấu trúc cây 17 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vnCây NP - Các trường hợp đặc biệtgoupee.com • Cây hoàn chỉnh (complete binary tree) – Gọi h là chiều cao của cây T. Ta gọi nó là cây hoàn chỉnh nếu: • T là cây đầy đủ đến chiều cao h-1 • Các nút có chiều cao h thì dồn hết về bên trái. 1 2 3 cuu duong than cong . com4 5 6 7 8 9 10 fb.com/goupee.vn Bộ Môn ĐT-KTMT - Viện ĐT-VT. Chương 11: Cấu trúc cây 18 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vnMột số tính chất của cây nhị phângoupee.com • Một số tính chất của cây nhị phân – Tính đệ quy: nếu ta chặt một nhánh bất kì của cây nhị phân thì ta sẽ thu được hai cây con cũng đều là cây nhị phân. – Gọi h và n lần lượt là chiều cao và kích thước của cây nhị phân thì ta luôn có: log (n+1) ≤ h+1 ≤ n 1 2 1 1 2 3 2 cuu duong than cong . com2 3 7 4 5 6 3 4 5 6 7 8 9 10 fb.com/goupee.vn Bộ Môn ĐT-KTMT - Viện ĐT-VT. Chương 11: Cấu trúc cây 19 CuuDuongThanCong.com https://fb.com/tailieudientucntt
goupee.vnMột số tính chất của cây nhị phângoupee.com • Một số tính chất của cây nhị phân – Đối với cây hoàn chỉnh và cây đầy đủ: nếu ta đánh số các nút lần lượt từ 1..N, với N là kích thước của cây theo thứ tự như hình vẽ thì ta có nhận xét sau: – Tại nút có số thứ tự i: 1 • nếu 2i>N: nút i là nút lá • nếu 2i=N: nút i là nút đơn 2 3 • nếu 2i<N: nút i là nút kép và có hai con trái, phải tương ứng là 2i và 2i+1 – Tại nút có số thứ tự j: 4 5 6 7 • nếu j=1: nút j là nút gốc (không có nút cha)cuu duong than cong . com • nếu j>1: nút j/2 (nếu j chẵn) hoặc 8 9 10 (j-1)/2 (nếu j lẻ) là nút cha của nút j. fb.com/goupee.vn Bộ Môn ĐT-KTMT - Viện ĐT-VT. Chương 11: Cấu trúc cây 20 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Affichage des 20 premières pages. Téléchargez le document pour le voir en entier.
Aucun commentaire pour le moment. Soyez le premier !
Commentaires (0)
Aucun commentaire pour le moment. Soyez le premier !