Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 6 - Th.S Thiều Quang Trung

Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 6 Kiểu cấu trúc cây do Th.S Thiều Quang Trung biên soạn có nội dung chính được trình bày như: Khái niệm cấu trúc cây - tree, đặc điểm cấu trúc cây, định nghĩa kiểu cấu trúc cây, các thao tác trên cấu trúc cây.
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 - Th.S Thiều Quang TrungCHƯƠNG 6KIỂU CẤU TRÚC CÂYGV Th.S. Thiều Quang TrungBộ môn Khoa học cơ bảnTrường Cao đẳng Kinh tế Đối ngoạiNội dung1 • Khái niệm cấu trúc cây - tree2 • Đặc điểm cấu trúc cây3 • Định nghĩa kiểu cấu trúc cây4 • Các thao tác trên cấu trúc câyGV. Thiều Quang Trung2Khái niệm cấu trúc cây• Cây là một tập hợp T các phần tử (gọi là nútcủa cây), gồm 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ờinhau T1, 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ấpi+1. Quan hệ này gọi là quan hệ cha –con.GV. Thiều Quang Trung3Khái niệm cấu trúc cây• Bậc của một nút: là sốcây con của nút đó• Nút gốc: là nút khôngcó nút cha• Nút lá: là nút có bậcbằng 0• Nút nhánh: là nút cóbậc khác 0 và khôngphải là gốc2220GV. Thiều Quang Trung110004Khái niệm cấu trúc câyMức 1Mức 2Mức 3Mức 4x• Chiều dài đường đi đến nút x: là số nhánh cần đi quakể từ gốc đến x• Độ cao của cây: Độ sâu (mức) của nút lá thấp nhấtGV. Thiều Quang Trung5