Giáo trình Cấu trúc dữ liệu và giải thuật: Phần 2 - ĐH Sư phạm kỹ thuật Nam Định
➤ Gửi thông báo lỗi ⚠️ Báo cáo tài liệu vi phạmNội dung chi tiết: Giáo trình Cấu trúc dữ liệu và giải thuật: Phần 2 - ĐH Sư phạm kỹ thuật Nam Định
Giáo trình Cấu trúc dữ liệu và giải thuật: Phần 2 - ĐH Sư phạm kỹ thuật Nam Định
CHƯƠNG 6:CÂY6.1.ĐỊNH NGHĨA VÀ KHÁI NIỆMа.Định nghĩaMột cày lã một tập hừu hạn các nút trong dó có một nút dặc biệt gọi là gốc (root). Giừa các nút có Giáo trình Cấu trúc dữ liệu và giải thuật: Phần 2 - ĐH Sư phạm kỹ thuật Nam Định một quan hệ phàn cấp gọi là "quan hệ cha conCó thê định nghía cây là một cách đệ quỵ như sau :1 Một nút là một cây. Nút dó cùng lã gốc cùa cây ấy5Nút n lá một nút và T|, T;,Tk là các cây VỚI Iij. n2,... nk lần lượt lã các gốc. thi một cây mới T sè dược tạo lập bang cách cho nút n trơ thành cha cúa Giáo trình Cấu trúc dữ liệu và giải thuật: Phần 2 - ĐH Sư phạm kỹ thuật Nam Định nút nj . n2,... nk; nghĩa là trên gôc lúc đó ni . n2, nk là con của nút n.Dê lien , ngưìn la cho phép tồn lại mội cây không có núl nào. mà la gọi là cGiáo trình Cấu trúc dữ liệu và giải thuật: Phần 2 - ĐH Sư phạm kỹ thuật Nam Định
ậy rỗng (null tree)Vi dụ: Mục lục cùa một cuôn sách của một chưong trong sách có càu trúc cúa một cây. (’hàng hạn. mục lục cùa chưomg 6 này:Chương ố :CHƯƠNG 6:CÂY6.1.ĐỊNH NGHĨA VÀ KHÁI NIỆMа.Định nghĩaMột cày lã một tập hừu hạn các nút trong dó có một nút dặc biệt gọi là gốc (root). Giừa các nút có Giáo trình Cấu trúc dữ liệu và giải thuật: Phần 2 - ĐH Sư phạm kỹ thuật Nam Định phân nối vòng6.3Cây tồng quát6.3.1Biếu diễn cây tồng quát6.3.2Phép duyệt cây tồng quát6.4áp dụng6.4.1c ây biểu d iền biểu thức6.4.2Cây biểu diều các tập6.4.3c ác quyết d Ị1111* Biếu thức số học X + y * (z-1 ) + u V có thể biểu diễn dưới dạng cây như hình6.2b. Các khái niệm* Sò các con của nút gọi l Giáo trình Cấu trúc dữ liệu và giải thuật: Phần 2 - ĐH Sư phạm kỹ thuật Nam Định à cap (degree) của nút đó. Vi dụ càp cùa A là .3, càp cùa H lã 2* Nút có cấp bang không gọi lã lá (deaf) hay nút tận củng (dermimal noder ). Vi dụ nútGiáo trình Cấu trúc dữ liệu và giải thuật: Phần 2 - ĐH Sư phạm kỹ thuật Nam Định
E, c, K. L V V ... Nút không là lá dược gọi lã nút nhánh ( branch node) Cap cao nhất của nút trên cày gọi là cấp cùa cây dỏ. Cây ở hình 6.4 lã cây cấCHƯƠNG 6:CÂY6.1.ĐỊNH NGHĨA VÀ KHÁI NIỆMа.Định nghĩaMột cày lã một tập hừu hạn các nút trong dó có một nút dặc biệt gọi là gốc (root). Giừa các nút có Giáo trình Cấu trúc dữ liệu và giải thuật: Phần 2 - ĐH Sư phạm kỹ thuật Nam Định múc Là 3J có sổ mức là 4*Chiêu cao (height) hay chiêu sâu (depth) của một cây là sò mức lớn nhâl của nút có trên cầy đó.Cầy chiêu hình 6.2 có chicu cao là 5Cây chiều hình 6.4 có chiều cao là 4Nếu ni. n2.....ni;là dày các nút mã Hi là cha cũa ni -1 với 1 Giáo trình Cấu trúc dữ liệu và giải thuật: Phần 2 - ĐH Sư phạm kỹ thuật Nam Định , tới nk . Độ dãi cua dường di (path length) bằng các nút trên dường di trừ di 1 . Vi dụ trên cây hình 6.4 dộ dài dường di từ A tới G là 2, từ A tới KGiáo trình Cấu trúc dữ liệu và giải thuật: Phần 2 - ĐH Sư phạm kỹ thuật Nam Định
lã 3CHƯƠNG 6:CÂY6.1.ĐỊNH NGHĨA VÀ KHÁI NIỆMа.Định nghĩaMột cày lã một tập hừu hạn các nút trong dó có một nút dặc biệt gọi là gốc (root). Giừa các nút có CHƯƠNG 6:CÂY6.1.ĐỊNH NGHĨA VÀ KHÁI NIỆMа.Định nghĩaMột cày lã một tập hừu hạn các nút trong dó có một nút dặc biệt gọi là gốc (root). Giừa các nút cóGọi ngay
Chat zalo
Facebook