Câu 1

+ Khái niệm cây: Cây là một đồ thị vô hướng liên thông phi chu trình

+ Đường đi trên cây từ a1-> an là một dãy các đỉnh a1, a2, a3, .....an-1, an, sao cho ai có quan hệ với ai+1, i: 1->n-1

+ Chiều cao của cây bằng số mức lớn nhất của đỉnh có trên cây

Ví dụ:

+ Dạng cài đặt cây bằng danh sách các con của mỗi đỉnh:

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

Type Pointer = ^ Member;

Member = Record

Id: 1..n;

Next : Pointer; // trỏ tới em liền kề

End;

Node = Record

Info: Integer;

Child: Pointer;

End;

Tree = Array [1..n ] of Node;

Var T: Tree;

Câu 2

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

Type TreeBSearch = ^Nut;

Nut = Record

Infor: Integer;

Left, Right: TreeBSearch;

End;

Var R : TreeBSearch;

2)

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

- 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 (số phần tử <n):

• 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,T);

+ Thủ tục loại bỏ đỉnh x ra khỏi cây sao cho cây sau khi laọi bỏ vẫn là cây NPTK:

- Tìm xem x có trên cây không:?

- Nếu không có thì thông báo và thoát khỏi chương trình

- Nếu x có trên cây:

• Di con trỏ P đến vị trí loại bỏ

• Nếu p không có con: giải phóng p

• Nếu p có 1 cây con khác rỗng: treo cây con khác rỗng vào vị trí loại bỏ, giải phóng p

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

+ 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

3) Nêu cách tìm kiếm theo tên sv: Tìm kiếm tuần tự trên cây theo tên sv đã biết

Câu 3

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

b) + 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

+ 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**