tailieunhanh - Bài giảng Cấu trúc dữ liệu 1: Chương 5 - Lương Trần Hy Hiến

Chương 5 của bài giảng Cấu trúc dữ liệu 1 giới thiệu về cây. Các nội dung cụ thể được trình bày trong chương này gồm có: Cây, cây nhị phân, cây nhị phân tìm kiếm, cây cân bằng. để tìm hiểu thêm các nội dung chi tiết. | Chương 5 CÂY Định nghĩa 1 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ó 1 nút đặc biệt được gọi là gốc - Các nút còn lại được chia thành những tập rời nhau Tl T2 Ị . Ị Tn theo quan hệ phân câ p trong đó Ti cũng là một 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 còn gọi là quan hệ cha-con. Nội dung 1. Cây 2. Cây nhị phân 3. Cây nhị phân tìm kiếm 4. Cây cân bằng A Ví dụ vê cây vn fpt hcmup ị a va linux tuoitre Một sô thuật ngữ Bậc của nút là số cây con của một nút Bậc của một cây là bậc lớn nhất 9 của các nút trên cây. r- Nút gốc là nút không co nut M. cha 5 4 3 2 Nút lá là nút có bậc bằng 0 Nút nhánh là nút có bậc khác 0 và không phải là nút gốc . Cây Định nghĩa 2 cấu trúc cây với kiểu cơ SỞT là - Một nút câ u trúc rỗng được gọi là cây rỗng NULL . - Một nút mà thông tin chính của nó có kiểu T nó liên kết với một số hữu hạn các câ u trúc cây khác cũng có kiểu cơ sở T. Các câ u trúc này được gọi là những cây con của cây đang xét. Một Số thuật ngữ Mức của một nút Nút gốc T 0 Gọi Tlz T2 . Tn là các cây con của To Muc Ti Múc T2 . Mức Tn F Một sô thuật ngữ Độ dài đường đi từ gốc đến nút x là sô nhánh cần ai qua kể từ gốc đến X. Độ dài đường đi tổng của cây KeT trong đó Px là độ dài đường đi từ gốc đến Đô dài đường đi trụng bình PI PT n n là so nut tren cay T . Rừng cây là tập hợp nhiều cây trong đó thư tự các cây là quan trọng. . Cây nhị phân . Cây nhị phân Định nghĩa cây nhị phân là cây mà mỗi nút có tôi đa 2 cây con Ví dụ vê ứng dụng của cây nhị .