CHƯƠNG 6
KIỂU CẤU TRÚC CÂY
GV Th.S. Thiều Quang Trung
Trường Cao đẳng Kinh tế Đối ngoại
•Khái niệm cấu trúc cây - tree
1
•Đặc điểm cấu trúc cây
2
•Định nghĩa kiểu cấu trúc cây
3
•Các thao tác trên cấu trúc cây
4
Nội dung
2GV. Thiều Quang Trung
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, …,Tntheo quan hệ phân cấp, trong đó
Ticũ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
4
2
2
2
110
0
0
0
GV. Thiều Quang Trung
Mức 4
Mức 3
Mức 2
Mức 1
Khái niệm cấu trúc cây
•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
5
x
GV. Thiều Quang Trung