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 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. | CHƯƠNG 6 KIỂU CẤU TRÚC CÂY GV . Thiều Quang Trung Bộ môn Khoa học cơ bản Trường Cao đẳng Kinh tế Đối ngoại Nội dung 1 • Khái niệm cấu trúc cây - tree 2 • Đặc điểm cấu trúc cây 3 • Định nghĩa kiểu cấu trúc cây 4 • Các thao tác trên cấu trúc cây GV. Thiều Quang Trung 2 Khá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út củ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ời nhau 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ấp i+1. Quan hệ này gọi là quan hệ cha –con. GV. Thiều Quang Trung 3 Khá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ông có nút cha • 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à gốc 2 2 2 0 GV. Thiều Quang Trung 1 1 0 0 0 4 Khái niệm cấu trúc cây Mức 1 Mức 2 Mức 3 Mức 4 x • Chiều dài đường đi đến nút x: là số nhánh cần đi qua kể từ gốc đến x • Độ cao của cây: Độ sâu (mức) của nút lá thấp nhất GV. Thiều Quang .