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
Hiển thị 20 trang đầu. Tải tài liệu để xem đầy đủ.
Chưa có bình luận nào. Hãy là người đầu tiên!
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!