Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 6 - Trường ĐH Công nghệ Thông tin

Nối tiếp chương 5, Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 6 giới thiệu nội dung về cây và cây nhị phân: định nghĩa, khái niệm và ví dụ minh họa, một số tính chất của cây nhị phân, cấu trúc dữ liệu và duyêt cây nhị phân. Mời các bạn tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 6 - Trường ĐH Công nghệ Thông tinCẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1Cấu trúc dữ liệu 1 vá thuật giải Click To Edit1 NỘIMaster CÂY VÀ CÂY NHỊ PHÂN DUNGTitle Style Định Nghĩa Click ToCây Edit 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 những tập rời nhau T1, T2, …,Tn theo quan hệ Cấu trúc dữ liệu 1 vá thuật giảiCẤ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 MộtClick Số Khái ToNiệm Edit 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 Ví Dụ 1 TổTo Click Chức EditDạng Cây Master 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ảiCẤ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 CâyClick Nhị Phân To Edit Master Title Style • Mỗi nút có tối đa 2 cây con Caây Caây con con traùi Cấu trúc dữ liệu 1 vá thuật giải phaûiCẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 5 MộtClick Số Tính ToChất EditCủa Cây Nhị Master Phân Title Style • 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ảiCẤ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 CấuClick Trúc Dữ To Liệu EditCủa Cây Nhị Master Phân Title Style typedef struct tagTNode { Data Key; struct tagTNode *pLeft; Key ...