Đọc và thảo luận nhóm để tìm hiểu phân loại cây nhị phân và một số cách biểu diễn cây nhị phân bằng mảng 1 chiều hoặc bằng nút liên kết.

Vẽ sơ đồ cây cho các biểu thức toán học sau:

a) (x + y)*(x – (y + z)/t).

b) x + (y + (z + t)/(u – v)).

Cây nào là cây hoàn hảo? Cây nào là cây hoàn chỉnh? Cây nào không là hoàn hảo và hoàn chỉnh?

Cây nhị phân gọi là đầy đủ nếu mỗi nút của nó hoặc là nút lá hoặc có đúng hai nút con. Khẳng định "Cây nhị phân đầy đủ sẽ luôn là hoàn chỉnh hoặc hoàn hảo" là đúng hay sai?

Cho mảng [A, B, C, D, E, F, G, H, I, J] biểu diễn một cây nhị phân. Em hãy cho biết thứ tự duyệt các nút của cây này theo phép duyệt trước (gốc-trái-phải). 

Cho mảng A có 14 phần tử, biểu diễn cây nhị phân hoàn chỉnh. Tính chiều cao của cây nhị phân này. 

Lưu ý: Cây nhị phân tổng quát cũng có thể được biểu diễn bằng mảng một chiều bằng cách bổ sung các nút rỗng có giá trị None để tạo thành cây hoàn chỉnh, sau đó biểu diễn mảng như đã nêu trên. Ví dụ sau minh hoạ cho ý tưởng này.

Cho mảng một chiều A biểu diễn cây nhị phân hoàn chỉnh T. Viết hàm 1eve1(k) trả về mức của nút tương ứng với phần tử A[k] của cây T. 

Tính chiều cao của các cây trong Hình 6.3.