Cây nhị phân (Binary Trees) và các tính chất trong cấu trúc dữ liệu

Phần này trình bày các tính chất quan trọng của cây nhị phân. Giả sử ta có cây nhị phân như sau:

Các tính chất chính

• Số nút tối đa tại cấp độ 'l': 2^l-1. Ở đây cấp độ là số nút trên đường đi từ gốc đến nút, tính cả gốc. Cấp độ gốc = 1.
• Số nút tối đa của cây nhị phân chiều cao h: 2^h - 1. Chiều cao là số nút tối đa trên đường gốc-đáy. Cây 1 nút có chiều cao = 1.
• Chiều cao tối thiểu của cây nhị phân n nút: log₂(n+1). Nếu coi chiều cao lá = 0, công thức: log₂(n+1) - 1.
• Cây nhị phân có L lá: có ít nhất log₂(L+1) cấp độ.
• Nếu mỗi nút có 0 hoặc 2 con: số nút lá luôn lớn hơn số nút có 2 con đúng 1 đơn vị.

Lưu ý: Vì cây nhị phân là một loại cây, nó có tất cả tính chất của cây trong lý thuyết đồ thị.