Câu 1

1) (1đ)

* khái niệm cây nhị phân tìm kiếm: Cây NPTK là một cây nhị phân thỏa mản 3 điều kiện:

Điều kiện 1: Khóa tại các đỉnh của cây con trái nhỏ hơn khóa tại gốc

Điều kiện 2: Khóa tại gốc > khóa tại các đỉnh của cây con bên phải

Điều kiện 3: Cây con bên trái và cây con bên phải đều là cây NPTK

* Cây nhị phân đã cho là cây NPTK vì nó thỏa mãn các điều kiện được nêu trong khái niệm cây NPTK

2) Dạng cài đặt cây bằng con trỏ(0.5đ)

Type BinaSearchTree = ^ Nut;

Nut = Record

Key: integer;

Left, Right: BinaSearchTree;;

End;

Var T : BinaSearchTree;

3) Thêm đỉnh có khóa x = 30 vào cây: (1.5đ)

* Hình ảnh cây sau khi thêm x:

* Viết thủ tục thêm một đỉnh x vào cây R: Insert(x, R):

- Sử dụng con trỏ phụ M chứa địa chỉ của nút cần thêm

- Xin MT cấp phát ô nhớ cho M

- Đổ dữ liệu cần thêm vào ô nhớ có địa chỉ M

- Gắn M vào cây:

Nếu Cây rỗng (R = nil): R := M

Nếu cây không rỗng: Xác định vị trí thêm M:

If (x<R^.info) then Insert (x, R^.Left)

Else if (x>R^.info) then Insert(x, R^.right);

else thông báo x đã có trên cây

Câu 2:( 2đ)

Duyệt danh sách để hiển thị các nút trong danh sách theo hình dạng cây thư mục

Câu 3: Tương tự câu 2 đề 26