Câu 1

* khái niệm cây nhị phân: (0.5 đ)

Cây nhị phân là một cây, trong đó số con tại mỗi đỉnh trên cây tối đa là 2 con và được sắp thành cây con trái và cây con phải

* Có hai phương pháp cơ bản để cài đặt cây nhị phân:

a) Cài đặt cây nhị phân bằng mảng: (0.5 đ)

Const n = <số đỉnh tối đa trên cây> ;

Type Nut = Record

Infor: Integer;

Left, Right: 0 .. n;

End;

TreeBina = array[1..n] of Nut;

Var T : TreeBina;

b) Cài đặt cây nhị phân bởi con trỏ: (0.5 đ)

Type TreeBina = ^ Nut;

Nut = Record

Infor: Integer;

Left, Right: TreeBina;

End;

Var T : TreeBina;

* Ưu nhược điểm của từng dạng cài đặt: (0.5 đ)

a) Cài đặt bởi mảng:

Ưu điểm: - Các phép toán thực hiện tương đối dễ dàng

- việc truy cập đến các đỉnh trên cây là trực tiếp, tốc độ truy cập là nhanh và đồng đều đối với mọi phần tử

Hạn chế: - Khi cài đặt gây hiện tựợng dư thừa bộ nhớ.....

b) Cài đặt bởi con trỏ

Ưu điểm: - Không có hiện tượng dư thừa bộ nhớ

Hạn chế: - Truy cập đến các phần tử trên cây là truy cập tuần tự, bao giờ cũng xuất phát từ gốc, nên tốc đọ truy cập là chậm

- .....

Câu 2

+ Dạng cài đặt cây NPTK sử dụng con trỏ: (0.5 đ)

Type TreeBSearch = ^Nut;

Nut = Record

Infor: Integer;

Left, Right: TreeBSearch;

End;

Var R : TreeBSearch;

+ Tạo cây nhị phân tìm kiếm: (1 đ)

- 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

- Trong khi điều kiện nhập chưa thỏa mãn tính dừng (x<>0):

• Nhập dữ liệu mới cần thêm x,

• Liên tiếp gọi thủ tục thêm đỉnh mới vào cây: Insert(x,R);

+ Tìm xem trên cây có đỉnh nào có thông tin = x không? (1 đ)

- Nhập x

- Sử dụng con trỏ phụ p duyệt bắt đầu từ gốc đến khi p = nil hoặc tìm thấy thì dừng: Nếu p^.info = x => thông báo tìm thấy và dừng giải thuật, Nếu x< P^.Infor: Tìm nhánh trái p => p := p^.left, ngược lại tìm nhánh phải P => p := p^.right

(Có thể viết giải thuật dưới dạng đệ quy)

+ Loại bỏ đỉnh có khóa x trên cây: (1 đ)

Cách làm:

- Tìm x, p là con trỏ trỏ tới đỉnh có khóa x trên cây

- Nếu đỉnh loại bỏ là lá ( p^.left = nil; p^.right = nil): Dispose(p)

- Nếu đỉnh loại bỏ có một con khác rỗng, một con = rỗng: Treo cây con khác rỗng vào vị trí loại bỏ, giải phóng p

- Nếu đỉnh loại bỏ có cả hai cây con đều khác rỗng: Treo cây con trái vào vị trí loại bỏ, Treo cây con phải và vị trí trái nhất của cây con trái, giải phóng p

+ Đếm số đỉnh hiện có trên cây: (0.5 đ)

Cách làm: Có thể sử dụng một trong các phương pháp duyệt cây để đếm số đỉnh

Câu 3

a) Cây biểu thức: (1 đ)

+ Duyệt cây biểu thức theo thứ tự trước => Kết quả là biểu thức tiền tố: *+*2xy**-*5ab-*5ab-*5ab (0.5 đ)

+ Duyệt cây biểu thức theo thứ tự sau = > Kết quả là biểu thức hậu tố: 2x*y+*5a+-b5a*-b*5a*-b** (0.5 đ)