Xem mẫu
Chương 4. Cây nhị phân tìm kiếm
Trần Minh Thái
Email: minhthai@itc.edu.vn Website: www.minhthai.edu.vn
1
Nội dung
1. Khái niệm
2. Đặc điểm
3. Định nghĩa kiểu dữ liệu
4. Các lưu ý khi cài đặt
5. Các thao tác
2
Khái niệm
• Bậc của một nút: là số cây con của nút đó
2 • 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
2 2 • Nút nhánh: là nút có bậc khác 0 và không phải là gốc
0 1 1 0
0 0
3
Khái niệm
Mức 1
• 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
Mức 2 (mức) của nhất
cây: Độ sâu nút lá thấp
Mức 3
Mức 4 x
4
Đặc điểm cây nhị phân tìm kiếm
• Là cây nhị phân
•
7
Giá trị của một node bất kỳ luôn lớn hơn giá trị của tất cả các node bên trái và nhỏ hơn giá trị tất cả các node bên phải
3 36 Nút có giá trị nhỏ nhất nằm ở trái nhất của cây
1 6 15 40 Nút có giá trị lớn nhất nằm ở phải nhất của cây
4 23
5
...
- tailieumienphi.vn
nguon tai.lieu . vn