BÀI TẬP TỔNG HỢP VỀ CÂY
1. Viết chương trình tính chiều cao của cây
2. Cho m, n là hai node trên cây. Viết các thủ tục kiểm tra:
a. ON_LEFT(m, n)=true nếu m ở bên trái của n (=false nếu không)
b. ON_RIGHT(m,n)=true nếu m ở bên phải của n (=false nếu không)
c. P_ANCESTOR(m, n)=true nếu m là tổ tiên thực sự của n (=false nếu không)
d. P_DESCENDANT(m, n)=true nếu m là hậu duệ thực sự của n (=false nếu không)
3. Viết chương trình tìm tổ tiên chung gần nhất của hai node trên cây (tổ tiên chung gần nhất là node: là tổ tiên của cả hai node và mọi node là tổ tiên của cả hai node là tổ tiên của node này)
4. Duyệt theo mức một cây: đầu tiên liệt kê gốc, sau đến các node ở độ sâu 1, tiếp đó các node ở độ sâu 2 … Các node ở cùng độ sâu được liệt kê từ trái qua phải. Viết chương trình duyệt theo mức một cây.
5. Chuyển biểu thức ((a+b) + c*(d+e) + f)*(g+h) sang:
a. biểu thức prefix
b. biểu thức postfix
6. Cho cây T trong nó mỗi node trong đều có 2 con. Viết chương trình chuyển:
a. duyệt tiền tự của T sang duyệt hậu tự
b. duyệt hậu tự của T sang duyệt tiền tự
c. duyệt tiền tự của T sang duyệt trung tự
7. Bậc của một node là số con của nó. Chứng tỏ rằng trong cây nhị phân số node lá bằng số node bậc 2 cộng 1
8. Chứng tỏ rằng trong cây nhị phân chiều cao h của cây >=log(n+1)/2 trong đó n là số node của cây
9. Cho biết các duyệt tiền tự, trung tự và hậu tự của một cây. Mô tả một thuật toán xác định, với mọi cặp node (m, n), m có là tổ tiên của n hay không.
10. Có thể kiểm thử node m là tổ tiên thực sự của node n bằng cách kiểm thử m đứng trước n trong X-order và sau n trong Y-order (X, Y không thuộc {pre, in, post}). xác định tất cả các cặp X, Y mệnh đề trên là đúng.
( X=pre, Y= post)
11. Thực thi các hoạt động cây trong biểu diễn cây bởi:
a. các con trỏ về cha
b. danh sách các con
c. các con trỏ leftmost_child, right_sibling