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

CHƯƠNG 6<br /> KIỂU CẤU TRÚC CÂY<br /> GV Th.S. Thiều Quang Trung<br /> Bộ môn Khoa học cơ bản<br /> Trường Cao đẳng Kinh tế Đối ngoại<br /> <br /> Nội dung<br /> <br /> 1 • Khái niệm cấu trúc cây - tree<br /> <br /> 2 • Đặc điểm cấu trúc cây<br /> 3 • Định nghĩa kiểu cấu trúc cây<br /> <br /> 4 • Các thao tác trên cấu trúc cây<br /> GV. Thiều Quang Trung<br /> <br /> 2<br /> <br /> Khái niệm cấu trúc cây<br /> • Cây là một tập hợp T các phần tử (gọi là nút<br /> của cây), gồm có:<br /> – một nút đặc biệt gọi là nút gốc,<br /> – các nút còn lại được chia thành những tập rời<br /> nhau T1, T2, …,Tn theo quan hệ phân cấp, trong đó<br /> Ti cũng là một cây.<br /> <br /> • Mỗi nút ở cấp i sẽ quản lý một số nút ở cấp<br /> i+1. Quan hệ này gọi là quan hệ cha –con.<br /> GV. Thiều Quang Trung<br /> <br /> 3<br /> <br /> Khái niệm cấu trúc cây<br /> • Bậc của một nút: là số<br /> cây con của nút đó<br /> • Nút gốc: là nút không<br /> có nút cha<br /> • Nút lá: là nút có bậc<br /> bằng 0<br /> • Nút nhánh: là nút có<br /> bậc khác 0 và không<br /> phải là gốc<br /> <br /> 2<br /> <br /> 2<br /> <br /> 2<br /> <br /> 0<br /> <br /> GV. Thiều Quang Trung<br /> <br /> 1<br /> <br /> 1<br /> <br /> 0<br /> <br /> 0<br /> <br /> 0<br /> <br /> 4<br /> <br /> Khái niệm cấu trúc cây<br /> Mức 1<br /> Mức 2<br /> Mức 3<br /> Mức 4<br /> <br /> x<br /> <br /> • Chiều dài đường đi đến nút x: là số nhánh cần đi qua<br /> kể từ gốc đến x<br /> • Độ cao của cây: Độ sâu (mức) của nút lá thấp nhất<br /> GV. Thiều Quang Trung<br /> <br /> 5<br /> <br />