Cây nhị phân nối vòng, Biểu diễn cây tổng quát qua cây nhị phân.

1. Cây nhị phân nối vòng:

Ở bài học java trước mình đã đề cập đến việc lưu trữ kiểu móc nối với cây nhị phân, nếu lưu trữ cây nhị phân dưới dạng móc nối chúng ta nhận thấy có rất nhiều mối nối không: với cây có n nút thì có tới n+1 mối nối không.
- Với một nút M nào đó bất kì trên cây nếu LPTR(M) = null thì ta sẽ chuyển con trỏ LPTR(M) chỉ về nút đướng trước P trong thứ tự giữa, Nếu RPTR(M) bằng null thì ta chuyển con trỏ về chỉ vào nút đứng sau P ở thứ tự giữa (duyệt theo thứ tự giữa mời các bạn đọc lại bài 5 Cây (tree) ).
- Ở đây có một một câu hỏi, thế nào là nút đứng trước, thế nào là nút đứng sau? nút đứng trước là nút được xử lý trước trong thứ tự giữa, nút đứng sao là nút được xử lý sau trong thứ tự giữa.
- Dưới đây là hình ảnh minh họa, các đường màu đỏ là biểu diễn mối nối vòng:
- Ta thấy còn 2 đường nối lên của 2 nút tận cùng vì không có nút được xử lý ngay trước nút tận cùng trái, và không có nút được xử lý sau nút tận cùng phải vì vậy 2 mối nối này sẽ không đi tới đích nào cả. Vậy ta có ta sẽ thêm vào đầu của cây 1 nút gọi là HEAd và coi cả cây này là cây con bên trái của cây mới có gốc là HEAD.
- Con trỏ phải của Head sẽ chỉ vào chính nó. với cấu trúc cây như này thì việc tìm kiếm là khá đơn giản.

• Chú ý: Trong mỗi nút ta phải thêm 2 trường bit nữa để đánh dâu qui cách mối nối vòng cho máy hiểu: Lb và Rb, khi con trỏ trái = null thì Lb = 1, con trỏ trái LPTR # null thì Lb =0. với con trỏ phải RPTR cũng vậy.

2.Cây tổng quát.

- Cây tổng quát thường có rât nhiều mối nối không, vì vậy người ta sẽ đưa thành cây nhị phân.
- Nguyên tắc để đưa cây tổng quát thành cây nhị phân ta có:

Mỗi nút của cây nhị phân tổng quát sẽ chia làm 3 phần: 1 phần là con trỏ chỉ vào nút con trái, một phần là con trỏ chỉ vào nút con kế cạnh:

• Duyệt cây tổng quát cũng duyệt giống cây nhị phân.

Bài hôm nay sẽ kết thúc tại đây, như mình đã nói ở phần này gồm có ngăn xếp(Stack) và hàng đợi(Queue) do hai loại cấu trúc dữ liệu này mình gặp ít trong thực tế nên mình không nói về 2 loại này, các bạn muốn tìm hiểu thì google nhé. (Mình không dùng nhưng cũng không biết lĩnh vực khác có hay dùng không)