Có nhiều lý thuyết về cây nhị phân, nhưng ở đây chỉ đề cập tới cây nhi phân phục vụ cho đi thi thôi. Tức là phạm vi và tính chất được bó hẹp trong phạm vi đơn giản, chưa mở rộng. Cách tiếp cận này, chưa phải là tiên tiến nhất, nhưng nó làm cho người đi thi dễ hiểu, dễ thuộc và dễ... bắt chước nhất → dễ kiếm điểm nhất.
Có 2 cách hiểu chính về cây nhị phân tuỳ thuộc vào tính chất của dữ liệu.
1) Về trực quan: Cây là đồ thị liên thông, không chu trình. Ngoài ra có một nút đặc biệt chọn ra phụ thuộc vào bài toán cụ thể: Gốc. Trình tự từ gốc vô cùng quan trọng. Trình tự từ đỉnh đặc biệt này đến các đỉnh khác cho ta biết về cấp 0, chiều cao 0, nút 0. Đối với các đỉnh khác tính tới gốc có các giá trị 1, 2... ngoài ra còn có lá (không có nút con) hay các nút trong giúp hình dung cây dễ dàng hơn.
2) Về toán học: Cây dược định nghĩa theo kiểu đệ quy, một nút con là một cây dùng theo dạng đệ quy có nút con, nút cha lúc này thứ tự đặt vấn đề sẽ khác với thứ tự ở 1) → chỉ ra cay có thứ tự rõ ràng, cha trước, con sau. Trong phạm vi nghiên cứu cây đối với đề thi thì cây hị phân không quá 2 nút con, đối với mỗi nút. Ngầm định khi làm việc với cây nhị phân sẽ là trái trước, phải sau. Trái bé, phải to. Nếu khong theo ngầm định phải tuyên bố rằng, bài thi của tôi sẽ coi như là... để người chấm biết. Nếu không tuyên bố mà không làm theo ngầm định, coi như làm sai và không được điểm.
Về biểu diễn cây thường sử dụng danh sách liên kết là chủ yếu. Thông thường biểu diễn cây qua cấu trúc dữ liệu sau, cấu trúc này sử dụng cho các bài tập và bài thi đó nha, Admin cần chú ý mà nắm cho rõ đừng cố tình nhầm lẫn:
List = Cây
Cây = Record;
          d: Data;
          L, R: List;
end.
Bài tập ứng dụng cây trong đề thi mật độ lớn. Thường là câu 2 trong đề thi.
Có 3 dạng bài tập trong đề thi đối với cây gồm:
1) Duyệt cây: Giống như duyệt đồ thị, có thể đem thuật toán duyệt đồ thị sang duyệt cây, nhưng phải chuyển đổi cho phù hợp với dạng dữ liệu. Thường đề thi yêu cầu duyệt cây thì Output các đỉnh ra theo đúng thứ tự cây.
2) Sử dụng cây phục vụ bài toán tìm kiếm
3) Sử dụng cây để mã hoá dữ liệu ở 2 mức đơn giản: Mã tiền tố và mã Huffman.

Ta làm một vài câu súc miệng để biết cách thức làm nó trong đề thi.
1. Bài toán duyệt cây nhị phân:
Về nguyên tắc:
- Cần đặt tên của nút vừa là tên nút, vừa là giá trị mang để tránh ghi nhiều tên gây rối thuật toán.
- Đề yêu cầu duyệt cây, thì phải viết ra được cây (Các nút của nó)
Một cây đơn giản như thế này

[You must be registered and logged in to see this image.]

Có 3 phương pháp duyệt: Tiền, trung và hậu a) Duyệt tiền: Thứ tự u → P → x b) Duyệt trung: Thứ tự P → u → x c) Duyệt hậu: Thứ tự P → x → u

a)

Viết thủ tục duyệt tiền thứ thự đối với một cây T cho trước:

b)

Viết thủ tục duyệt trung thứ thự đối với một cây T cho trước:

c)

Viết thủ tục duyệt hậu thứ thự đối với một cây T cho trước:

Các bài tập sát đề thi phần này (Đề nghị làm thành thạo, kiểu gì cũng có câu trúng đúng dạng đề thi)
1)

Biểu thức M cho ở dạng trung tố đầy đủ dấu ngoặc, chuyển M vào cây nhị phân T có cấu trúc List:

2)

Biểu thức M chứa trong cây nhị phân T, viết thủ tục tính giá trị của M:

3)

Chuyển biểu thức M ở dạng hậu tố vào cây T có cấu trúc List:

4)

Biểu thức M cho ở dạng trung tố không dấu ngoặc, chuyển M vào cây nhị phân T có cấu trúc List:

Chuyển biểu thức trung tố M không đủ dấu ngoặc vào cây nhị phân T
Trước khi đọc lời giải, hãy xem bài [You must be registered and logged in to see this link.]
Ý tưởng:
- Duyệt từng phần tử trong M cho đến hết.
- Nếu Mi là toán hạng: tống nó thêm vào stack Sh.
- Nếu là dấu mở ngoặc “(“: cho vào stack St
- Nếu là dấu đóng ngoặc “)”: Lặp công việc: lấy 1 phần tử trong stack St ra:
* Là toán tử: lấy tiếp 02 phần tử trong Stack Sh ra, tạo lập một cây có 3 thành phần trên, xong tống cả cái cây đó vào trong Sh như một phần tử
* Là dấu mở ngoặc: Thôi không lặp nữa.
- Nếu là toán tử xét các trường hợp:

• Chừng nào ở đỉnh stack St là toán tử và toán tử đó có độ ưu tiên lớn hơn hoặc bằng toán tử hiện tại thì lấy toán tử trong St ra, đồng thời lấy tiếp 02 phần tử trong Stack Sh ra, tạo lập một cây có 3 thành phần trên, xong tống cả cái cây đó vào trong Sh như một phần tử. Đưa toán tử hiện tại vào stack St
  
• Không thoả mãn cũng đưa toán tử hiện tại vào stack St
  

Khi duyệt xong chuỗi M, nếu St còn chưa rỗng thì lấy lần lượt cứ 1 phần tử trong St ra và 2 phần tử trong Sh ra, tạo cây, tống cả cây vào trong Sh.
Cuối cùng đưa cây trong Sh ra và viết.

Giải thuật:

Sửa theo góp ý của LĐS. Phần Stack chỉ lưu một loại dữ liệu.

Nhiều bài không có điểm (đấy là quan điểm của thầy), bởi vì nhầm lẫn khi gán:
BT.^L = đT; BT^.R = đS;

Nhớ rằng, thằng nằm bên trái - Vào trước - Ra sau.

Admin: OK. Đã sửa.

Chuyển biểu thức trung tố không đầy đủ dấu ngoặc:
1. Nếu là toán tử:
- Chừng nào chưa gặp dấu ngoặc mở (một cách viết khác của "vẫn là toán tử") và độ ưu tiên của toán tử ở đỉnh St ≥ độ ưu tiên của Mi, lấy ra tính
- Sau khi kết thúc vòng lặp, đẩy Mi vào St

2. Anh Admin vẫn chưa sửa nhận xét của a Mr Phuong
1) Pop(sh, b); Pop(sh, c); Pop(St, a);
2) New(X); X.d = a; X^.L = b; X^.R = c;
nên là:
2) New(X); X.d = a; X^.L = c; X^.R = b;

Admin: OK. Đã sửa.

Một số thủ tục cần trong các bài thi
Cấu trúc cây nhị phân trong các ví dụ:
Type Link
          Link = ^Node;
          Node = Record
                    K: Data;
                    L, R: Link;
          End;

1.

Thêm nút lá vào cây nhị phân:

2.

Thêm một nút vào cây nhị phân:

Viết thủ tục đệ quy thực hiện việc trao đổi con trái với con phải tại mọi nút.
Proc DOI (Var T: Next)
1) IF T ≠ Nil THEN
2) IF (T^.L ≠ Nil) & (T^.R ≠ Nil) THEN
          a) W : = T^.L;
                    T^.L = T^.R;
                    T^.R = W
          b) DOI (T^.L); DOI (T^.R)

Cây nhị phân trước ta vẫn làm theo 4 phép tính cộng trừ nhân chia. Các hàm mũ, căn logarit hay hàm lượng giác chắc ít đề cập. Hãy google để tham khảo các trình nâng cao khác. Ở đây chỉ giải quyết đến mức độ đi thi có thôi. Tức là bài thi cùng lắm là cho đến hàm mũ và căn (để người đi thi còn làm kịp thời gian), còn các hàm khác đưa vào thì đánh đố thí sinh, có lẽ nếu để nghiên cứu thì được, còn cho vào bài thi sẽ bị pass 100%, vì chẳng có đứa nào điên mà đâm đầu vào làm có thể coi là vô ích.
Một số công thức cần nhớ để áp dụng:
a^b để chuyển thành cấu trúc cho vào cây thì phải viết là a^b, trong đó dấu ^ là toán tử, còn a và b là toán hạng.
[You must be registered and logged in to see this image.] để chuyển thành cấu trúc cho vào cây thì phải viết là A^(1/n), trong đó dấu ^ là toán tử, còn A và 1/n là toán hạng.

Bây giờ giả sử đề thi đánh đố như thế này:
Xây dựng cây nhị phân biểu diễn biểu thức và chuyển nó thành dạng hậu tố:
[You must be registered and logged in to see this image.]
Khách viếng thăm căn cứ vào các bài mẫu để làm. Kết quả phải như sau:
[You must be registered and logged in to see this image.]

Dạng hậu tố của biểu thức là:
a 2 ^ b 2 ^ + 2 ^ a 3 ^ - 2 ^ - a * 3 /

1. Cho dãy có n số nguyên {A₁,...,A_n} đôi một khác nhau.
a. Mô tả thủ tục xây dựng cây nhị phân tìm kiếm có khoá là các phần tử trong dãy.

b. Vẽ sơ đồ khối mô tả thuật toán.

c. Áp dụng vẽ cây nhị phân tìm kiếm cho danh sách

19, 25, 21, 22, 18, 16, 45, 32, 11, 14, 37

Ban QT: [You must be registered and logged in to see this link.]