Cây và cây nhị phân

Cây gồm các nút nối với nhau theo quan hệ cha–con. Một cây không rỗng có một gốc không có cha; mỗi nút còn lại có đúng một cha. Nút không có con là lá; nút có con là nút trong hay nút nhánh. Các nút cùng cha là anh em. Một nút cùng toàn bộ các nút phía dưới nó tạo thành cây con. **Cây nhị phân** có nhiều nhất hai con tại mỗi nút, phân biệt con trái và con phải. Không phải nút nào cũng có đủ hai con. Sơ đồ dưới đây là cây mẫu dùng trong chuyên đề; các số chỉ là dữ liệu chứa ở nút.

|Tên gọi|Điều kiện| |---|---| |Hoàn hảo (perfect)|Mọi nút trong có hai con và mọi lá cùng mức| |Hoàn chỉnh (complete)|Các mức trước mức cuối đều đầy; mức cuối điền liên tục từ trái| |Đầy đủ (full)|Mỗi nút có 0 hoặc 2 con; lá không nhất thiết cùng mức| Cây mẫu là hoàn hảo và cũng hoàn chỉnh. Nếu bỏ lá 14, cây còn hoàn chỉnh nhưng không hoàn hảo. Nếu giữ 14 mà bỏ lá 2, xuất hiện chỗ trống bên trái mức cuối nên không hoàn chỉnh. Cây hoàn hảo cao h có $2^k$ nút ở mức k và tổng $2^{h+1}-1$ nút. Với h=2, có 1+2+4=7 nút. Một cây đầy đủ chưa chắc hoàn chỉnh: gốc có hai con, con trái là lá, con phải có hai con lá thì mức cuối bị khuyết phía trái.