Cách Vẽ Cây Nhị Phân Tìm Kiếm Từ Kết Quả Duyệt

Cách vẽ cây nhị phân tìm kiếm là một kỹ năng quan trọng trong khoa học máy tính, giúp tái cấu trúc cấu trúc dữ liệu gốc từ các biểu diễn tuyến tính của nó. Việc hiểu rõ các phương pháp duyệt và nguyên tắc xây dựng lại cây không chỉ nâng cao kiến thức về cấu trúc dữ liệu mà còn mở ra khả năng giải quyết nhiều bài toán thực tế. Bài viết này sẽ đi sâu vào cách bạn có thể vẽ lại cây nhị phân tìm kiếm một cách hiệu quả, tập trung vào các phương pháp duyệt phổ biến và cung cấp các bước chi tiết, dễ hiểu để tái tạo lại cấu trúc cây ban đầu.

Các Phương Pháp Duyệt Cây Nhị Phân Tìm Kiếm

Cây nhị phân tìm kiếm (BST) là một cấu trúc dữ liệu đặc biệt, nơi mỗi nút có một giá trị và tuân theo các quy tắc nhất định: tất cả các nút trong cây con bên trái của một nút đều có giá trị nhỏ hơn giá trị của nút đó, và tất cả các nút trong cây con bên phải đều có giá trị lớn hơn. Có ba cách duyệt cơ bản để đi qua tất cả các nút của cây:

• Duyệt Tiền Thứ Tự (Pre-order Traversal – NLR): Duyệt nút gốc trước, sau đó là cây con bên trái và cuối cùng là cây con bên phải.
• Duyệt Trung Thứ Tự (In-order Traversal – LNR): Duyệt cây con bên trái trước, sau đó là nút gốc và cuối cùng là cây con bên phải.
• Duyệt Hậu Thứ Tự (Post-order Traversal – LRN): Duyệt cây con bên trái trước, sau đó là cây con bên phải và cuối cùng là nút gốc.

Mỗi phương pháp duyệt cung cấp một góc nhìn khác nhau về cấu trúc cây. Trong đó, duyệt Trung Thứ Tự (LNR) là phương pháp duy nhất cho phép ta tái tạo lại cây nhị phân tìm kiếm một cách dễ dàng nhờ tính chất sắp xếp của nó.

Nguyên Tắc Chung Để Vẽ Lại Cây Nhị Phân Tìm Kiếm

Để tái cấu trúc một cây nhị phân tìm kiếm từ kết quả duyệt, chúng ta cần tuân theo một nguyên tắc cốt lõi dựa trên thuộc tính của BST.

Xác Định Nút Gốc

Nguyên tắc cơ bản nhất để vẽ lại cây là xác định được nút gốc của cây hoặc cây con hiện tại.

• Từ kết quả duyệt Trung Thứ Tự (LNR): Nếu bạn có kết quả duyệt LNR, nút gốc sẽ là nút có giá trị nằm ở vị trí giữa, hoặc có thể được xác định qua các thuật toán đệ quy dựa trên việc chia mảng. Tuy nhiên, như đã nêu, LNR không cho phép ta tìm node gốc ban đầu nếu chỉ có duy nhất kết quả LNR.
• Từ kết quả duyệt Tiền Thứ Tự (NLR): Nút đầu tiên trong dãy kết quả duyệt NLR luôn là nút gốc của cây hoặc cây con đó.
• Từ kết quả duyệt Hậu Thứ Tự (LRN): Nút cuối cùng trong dãy kết quả duyệt LRN luôn là nút gốc của cây hoặc cây con đó.

Phân Chia Nhánh Trái và Phải

Sau khi đã xác định được nút gốc, chúng ta có thể phân chia các phần tử còn lại trong dãy kết quả duyệt thành hai nhóm: các phần tử nhỏ hơn nút gốc sẽ thuộc về cây con bên trái, và các phần tử lớn hơn nút gốc sẽ thuộc về cây con bên phải.

1. Tìm Node gốc: Xác định nút gốc của cây hoặc cây con hiện tại.
2. Phân chia nhánh:
   • Các phần tử xuất hiện trước nút gốc trong dãy duyệt NLR sẽ thuộc về nhánh trái (nếu nhỏ hơn gốc) và nhánh phải (nếu lớn hơn gốc). Tuy nhiên, điều này yêu cầu phải có cả kết quả NLR và LNR hoặc LRN.
   • Quan trọng hơn, dựa trên thuộc tính của BST: Một phần tử trong dãy kết quả duyệt (ví dụ NLR hoặc LRN) là gốc. Tất cả các phần tử nhỏ hơn gốc trong dãy duyệt đó sẽ tạo thành cây con bên trái. Tất cả các phần tử lớn hơn gốc trong dãy duyệt đó sẽ tạo thành cây con bên phải.
3. Đệ quy: Với mỗi đoạn (nhánh trái hoặc nhánh phải) vừa tìm được, lặp lại quy trình trên để xác định nút gốc mới cho đoạn đó và tiếp tục phân chia.

Cách tiếp cận này cho phép chúng ta xây dựng lại cây một cách có hệ thống.

Ví Dụ Minh Họa Chi Tiết

Hãy cùng xem xét một ví dụ cụ thể để làm rõ quy trình này. Giả sử chúng ta có kết quả duyệt Hậu Thứ Tự (LRN): 5 3 7 9 8 11 6 20 19 37 25 21 15 12.

Bước 1: Xác Định Nút Gốc Toàn Cục

Dựa trên nguyên tắc duyệt LRN, nút cuối cùng trong dãy (12) chính là nút gốc của toàn bộ cây.

Bước 2: Phân Chia Nhánh Trái và Phải

Bây giờ, chúng ta xem xét các phần tử trước số 12 trong dãy LRN: 5 3 7 9 8 11 6 20 19 37 25 21 15.

• Các phần tử nhỏ hơn 12 (5 3 7 9 8 11 6) sẽ tạo thành cây con bên trái của nút 12.
• Các phần tử lớn hơn 12 (20 19 37 25 21 15) sẽ tạo thành cây con bên phải của nút 12.

Bước 3: Xây Dựng Cây Con Bên Trái

Ta xét đoạn trái 5 3 7 9 8 11 6. Với đoạn này, theo nguyên tắc duyệt LRN, số 6 (phần tử cuối cùng của đoạn con) sẽ là nút gốc của cây con bên trái.

Tiếp tục áp dụng nguyên tắc cho các phần tử trước số 6 trong đoạn con này (5 3 7 9 8 11):

• Các phần tử nhỏ hơn 6 (5 3) sẽ là cây con bên trái của 6.
• Các phần tử lớn hơn 6 (7 9 8 11) sẽ là cây con bên phải của 6.

Ta lại tiếp tục xét đoạn con bên trái của 6 là 5 3. Nút gốc ở đây là 3.

• Phần tử nhỏ hơn 3 trong 5 3 là 5. Do 5 đứng trước 3 trong dãy LRN, nên 5 sẽ là cây con bên phải của 3 (vì 5 > 3). Điều này có vẻ mâu thuẫn nếu chỉ nhìn LRN.

Lưu ý quan trọng: Để vẽ lại cây một cách chính xác và đơn giản, ta thường kết hợp duyệt Tiền Thứ Tự (NLR) và duyệt Trung Thứ Tự (LNR), hoặc duyệt Hậu Thứ Tự (LRN) và duyệt Trung Thứ Tự (LNR).

• Nếu có NLR và LNR:

  • Phần tử đầu tiên của NLR là gốc.
  • Trong LNR, tìm gốc đó. Tất cả các phần tử trước nó là cây con trái, sau nó là cây con phải.
  • Áp dụng đệ quy cho các mảng con tương ứng của NLR và LNR.

• Nếu chỉ có LRN (như ví dụ ban đầu của bạn):

  • Phần tử cuối cùng của LRN là gốc.
  • Tất cả các phần tử nhỏ hơn gốc trong dãy LRN sẽ thuộc về cây con trái.
  • Tất cả các phần tử lớn hơn gốc trong dãy LRN sẽ thuộc về cây con phải.
  • Thứ tự của các phần tử bên trái hoặc bên phải trong dãy LRN không phản ánh vị trí tương đối của chúng trong cây con đó một cách trực tiếp như trong NLR. Ta cần xác định lại gốc cho từng đoạn con.

Cập Nhật Ví Dụ Với NLR & LRN

Giả sử chúng ta có kết quả NLR: 12 6 3 5 9 8 11 15 13 14 30 25 21 37 và LRN: 5 3 7 9 8 11 6 20 19 37 25 21 15 12.

1. Gốc: Phần tử đầu tiên của NLR là 12.

2. Phân Chia LNR: Trong LNR 5 3 7 9 8 11 6 20 19 37 25 21 15 12, tìm thấy 12 ở cuối.

   • Các phần tử trước 12 trong LNR: 5 3 7 9 8 11 6 20 19 37 25 21 15 sẽ thuộc về cây con trái hoặc phải của 12.
   • Các phần tử nhỏ hơn 12: 5 3 7 9 8 11 6 15 → Nhánh trái.
   • Các phần tử lớn hơn 12: 20 19 37 25 21 → Nhánh phải.

   Cách dễ nhất là:

   • Gốc = phần tử đầu tiên của NLR (12).
   • Tìm gốc (12) trong LNR.
   • Các phần tử trước 12 trong LNR: 5 3 7 9 8 11 6 20 19 37 25 21 15 là tất cả các nút của cây.
   • Các phần tử nhỏ hơn 12 từ LRN: 5 3 7 9 8 11 6 15 sẽ là các nút thuộc cây con trái.
   • Các phần tử lớn hơn 12 từ LRN: 20 19 37 25 21 sẽ là các nút thuộc cây con phải.

   Ta cần tìm phần tử đầu tiên của NLR (12) trong LNR, đó là cuối cùng. Các phần tử đứng trước 12 trong LNR là toàn bộ nút. Vậy các nút nhỏ hơn 12 sẽ thuộc cây con trái, các nút lớn hơn 12 sẽ thuộc cây con phải.

   • Dãy con cho cây con trái (nhỏ hơn 12): 5 3 7 9 8 11 6 15
   • Dãy con cho cây con phải (lớn hơn 12): 20 19 37 25 21

   Dựa trên LRN ví dụ gốc: 5 3 7 9 8 11 6 20 19 37 25 21 15 12

   • Gốc là 12.
   • Nhánh trái: các số < 12 -> 5 3 7 9 8 11 6.
   • Nhánh phải: các số > 12 -> 20 19 37 25 21 15.

   Tiếp tục với nhánh trái 5 3 7 9 8 11 6: Gốc là 6 (cuối cùng).

   • Nhánh trái của 6 (số < 6): 5 3.
   • Nhánh phải của 6 (số > 6): 7 9 8 11.

   Tiếp tục với nhánh trái của 6 là 5 3: Gốc là 3 (cuối cùng).

   • Nhánh trái của 3 (số < 3): Không có.
   • Nhánh phải của 3 (số > 3): 5.
   • Ta có cây con: 3 -> phải 5.

   Tiếp tục với nhánh phải của 6 là 7 9 8 11: Gốc là 11 (cuối cùng).

   • Nhánh trái của 11 (số < 11): 7 9 8.
   • Nhánh phải của 11 (số > 11): Không có.

   Tiếp tục với nhánh trái của 11 là 7 9 8: Gốc là 8 (cuối cùng).

   • Nhánh trái của 8 (số < 8): 7.
   • Nhánh phải của 8 (số > 8): 9.
   • Cây con: 8 -> trái 7, phải 9.

   Tập hợp lại cây con trái của 12:

   • Gốc 6
     • Trái 3
       • Phải 5
     • Phải 11
       • Trái 8
         • Trái 7
         • Phải 9

   Tương tự, xây dựng cây con phải của 12: 20 19 37 25 21 15. Gốc là 15.

   • Nhánh trái của 15 (số < 15): 20 19 (chú ý thứ tự trong LRN không quyết định vị trí tương đối trực tiếp). Ta cần xác định gốc tiếp theo trong dãy con này.
   • Nhánh phải của 15 (số > 15): 37 25 21.

   Nếu chỉ dùng LRN, ta cần kết hợp thông tin về giá trị để phân chia.

   • Dãy LRN gốc: 5 3 7 9 8 11 6 20 19 37 25 21 15 12
   • Gốc: 12
   • Phần tử < 12: 5 3 7 9 8 11 6. Đây là nút của cây con trái.
   • Phần tử > 12: 20 19 37 25 21 15. Đây là nút của cây con phải.

   Xét tập con 5 3 7 9 8 11 6. Số cuối cùng là gốc: 6.

   • Số < 6: 5 3.
   • Số > 6: 7 9 8 11.

   Xét tập con 5 3. Số cuối cùng là gốc: 3.

   • Số < 3: Không có.
   • Số > 3: 5.
   • => Cây con: 3 -> phải 5.

   Xét tập con 7 9 8 11. Số cuối cùng là gốc: 11.

   • Số < 11: 7 9 8.
   • Số > 11: Không có.
   • Xét tập con 7 9 8. Số cuối cùng là gốc: 8.
     • Số < 8: 7.
     • Số > 8: 9.
     • => Cây con: 8 -> trái 7, phải 9.
   • => Cây con 11: trái 8 (với các nút con của nó), phải null.

   Kết nối lại: Gốc 6 -> trái 3 (với 5), phải 11 (với 8, 9, 7).

   Tiếp tục với tập con cho nhánh phải của 12: 20 19 37 25 21 15. Số cuối cùng là gốc: 15.

   • Số < 15: 20 19.
   • Số > 15: 37 25 21.

   Xét tập con 20 19. Số cuối cùng là gốc: 19.

   • Số < 19: 20.
   • Số > 19: Không có.
   • => Cây con: 19 -> trái 20.

   Xét tập con 37 25 21. Số cuối cùng là gốc: 21.

   • Số < 21: 25. (Đáng lẽ là 25, nhưng 25 đứng trước 21 trong LRN, vậy nó thuộc về cây con trái của 21).
   • Số > 21: 37.
   • => Cây con: 21 -> trái 25, phải 37.

   Kết nối lại nhánh phải của 12: Gốc 15 -> trái 19 (với 20), phải 21 (với 25, 37).

Hình Ảnh Minh Họa

Sau khi xác định nút gốc, chúng ta phân chia mảng dữ liệu thành các đoạn tương ứng với cây con trái và cây con phải. Tiếp tục quy trình này cho từng đoạn con cho đến khi toàn bộ cây được tái cấu trúc.

<img src="https://giatheficoco.com/wp-content/uploads/2.webp" alt="Các bước xây dựng cây nhị phân tìm kiếm từ duyệt LRN - phần nhánh trái" width="336" height="400">

Quá trình này lặp lại cho đến khi chúng ta vẽ được toàn bộ cấu trúc cây, bao gồm cả nhánh trái và nhánh phải, từ kết quả duyệt ban đầu.

<img src="https://giatheficoco.com/wp-content/uploads/3.webp" alt="Các bước xây dựng cây nhị phân tìm kiếm từ duyệt LRN - phần nhánh phải" width="647" height="450">

Tóm Tắt Cách Vẽ Cây Nhị Phân Tìm Kiếm

Để vẽ lại cây nhị phân tìm kiếm, bạn cần kết hợp ít nhất hai loại kết quả duyệt, thường là Tiền Thứ Tự (NLR) và Trung Thứ Tự (LNR), hoặc Hậu Thứ Tự (LRN) và Trung Thứ Tự (LNR). Sử dụng phần tử đầu tiên của NLR hoặc cuối cùng của LRN làm gốc, sau đó dùng LNR để xác định ranh giới giữa cây con trái và cây con phải.

Câu Hỏi Thường Gặp Về Vẽ Cây Nhị Phân Tìm Kiếm

1. Tại sao lại cần vẽ lại cây nhị phân tìm kiếm?

Việc vẽ lại cây giúp kiểm tra sự hiểu biết về cấu trúc dữ liệu, xác minh tính đúng đắn của thuật toán duyệt, hoặc tái cấu trúc dữ liệu khi chỉ có thông tin duyệt.

2. Tôi có thể vẽ lại cây chỉ với một loại kết quả duyệt không?

Không. Chỉ riêng kết quả duyệt LNR thì không đủ để xác định gốc. Nếu chỉ có NLR hoặc LRN, ta vẫn cần thêm thông tin (như LNR) hoặc phải dựa vào các ràng buộc khác về giá trị để xây dựng lại cây.

3. Ý nghĩa của việc sắp xếp trong cây nhị phân tìm kiếm là gì?

Tính chất sắp xếp (giá trị nút con trái nhỏ hơn, nút con phải lớn hơn) là chìa khóa cho phép chúng ta phân chia các phần tử và tái cấu trúc cây một cách logic từ các kết quả duyệt.

4. Có cách nào tự động hóa việc vẽ lại cây không?

Có. Dựa trên các nguyên tắc đã trình bày, bạn có thể viết mã chương trình để tự động hóa quá trình này cho các bộ dữ liệu lớn.

5. Nếu kết quả duyệt chứa các phần tử trùng lặp thì sao?

Cây nhị phân tìm kiếm chuẩn thường không cho phép các phần tử trùng lặp. Nếu có, bạn cần làm rõ quy tắc xử lý trùng lặp (ví dụ: cho phép lưu vào cây con trái hoặc phải) để áp dụng khi vẽ lại cây.

Lời Kết

Nắm vững nguyên tắc và quy trình vẽ cây nhị phân tìm kiếm từ kết quả duyệt là một bước tiến quan trọng trong việc hiểu sâu về cấu trúc dữ liệu này. Bằng cách kết hợp các phương pháp duyệt và áp dụng logic phân chia, bạn có thể tự tin tái cấu trúc cây từ các biểu diễn tuyến tính, mở ra nhiều ứng dụng hữu ích trong lập trình và khoa học máy tính.

Ngày cập nhật gần nhất 07/01/2026 bởi Minh Anh