Cây (tree) trong java

Trong học lập trình java cấu trúc phi tuyến mà chúng ta xét ở đây là cấu trúc cây, rất phổ biến trong đời sống.

1.Định nghĩa và các khái niệm:

Khái niệm: Cây là tập hợp của một số hữu hạn các nút mà có một nút đặc biệt gọi là gốc( root) các nút có quan hệ phân cấp gọi là "Cha-con".
Ta có thể thấy:

• Một nút cũng là một cây và là gốc của cây đấy.

• T1,T2,T3...Ti là csác cây với r1,r2,r3...ri là các gôc tương ứng. r là một nút và r có quan hệ cha con với các nut(gốc) r1,r2,,r3...ri thì một cây mới T được tao thành Với gốc là r, các cây T1,T2,T3...Ti là các cây con của T (substrees)

• Một cây không có nút nào thì gọi là một cây rỗng.

- Số các con của một nút là cấp(degree) của nút đó:

Như trên hình ta thấy, cấp của J là 2, cấp của B là 3 cấp của Z là 2
- Nút có cấp bằng 0 được gọi là lá (leaf) như trên hình hoặc là nút tận cùng (terminal node) nút không là lá được gọi là nút nhánh.
- Cấp cao nhất của nút cũng là cấp của cây đó. Ví dụ cây trên cấp cao nhất là 3
- Gốc của cả cây đó Có level là 1, level của một nút là i thì nút con của nó có level i+1 VD: J có level là 1

- Chiều cao hay chiều sâu của một cây là số mức lớn nhất có trên cây đó.- nếu n1,n2...nk có quan hệ cha con: ni là cha ni+1 thì dãy đó là đường đi từ n1 đến nk, độ dài của đường đi bằng số nút trên đường đi trừ 1.- Cấu trúc cây không tồn tại chu trình, tổ chức cấu trúc cây giúp ta tru cập nhanh vào các phần tử của nó.

2.Cây nhị phân(binary tree):

-Cây nhị phân lafc cây mà mỗi nút chỉ gồm tối đa là 2 nút con, đối với cây con của một nút, ta phân biệt ra là cây con trái và cây con phải.

Một số dạng đặc biệt của cây nhị phân:

* Các tính chất của một cây nhị phân :

Số lượng tối đa các nut ở mức i của một cây nhị phân là (i >=1)
Số lượng tối đa của cây nhị phân có chiều cao h là: 2^h-1

* Biểu diễn cây nhị phân:

Để lưu trữ cây nhị phân trong bộ nhớ:
- Lưu trữ kế tiếp: Cách lưu trữ này thích hợp với cây nhị phân đầy đủ, hoàn chỉnh, nhưng nếu như những cây lệch trái cây lệch phải sẽ tạo ra sự lãng phí rất lớn, vì vậy mình sẽ không đi sâu vào phần này.
- Lưu trữ móc nối: Lưu trữu móc nối với một cây nhị phân sẽ rất thích hợp và nó phản ánh đc dạng tự nhiên của cây:
Mỗi nút của cây nhị phân tương ứng với mooth phần tử và ta chia mỗi nút ấy ra thành 3 phần chính lf con trỏ trái, con trỏ phải và phần thông tin dữ liệu của phần tử đó giống như lưu trữ móc nối kép của danh sách đã học ở bài trước:

1. LPTR con trỏ trái.
2. RPTR con trỏ phải.
3. INFO biểu diễn thông tin

* Duyệt cây nhị phân:
- có 3 cách duyệt cây nhị phân chính:

• Duyệt cây theo thứ tự trước(tức là phép xử lý gốc sẽ để lên trước)- Bước 1: Xử lý gốc(root)- Bước 2: Duyệt cây con trái theo thứ tự trước (KHi xử lý cây con này thì lại gồm 3 bước lắp lại)- Bước 3: Duyệt cây con phải theo thứ tự trước
• Duyệt cây theo thứ tự giữa- Bước 1 uyệt cây con trái theo thứ tự giữa
  - Bước 2: Xử lý gốc(root)- Bước 3: Duyệt cây con phải theo thứ tự giữa
• Duyệt cây theo thứ tự sau.- Bước 1: Duyệt cây con trái theo thứ tự sau.- Bước 2: Duyệt cây con phải theo thứ tự sau.- Bước 3: Xử lý gốc(root).

- Những cách duyệt trên đây là viết theo đệ quy với trường hợp suy biến là cây sẽ rỗng, khi cây rỗng thì ta không thực hiên gì cả. Để giúp các bạn hiểu rõ hơn cái ý nghĩa đệ quy ở đây thì mình sẽ nói hoàn toàn bằng ngôn ngữ bình thường diễn đạt tiến trình máy thực hiện khi dùng phương pháp duyệt cây theo thứ tự trước để duyệt cây sau:

1. Xử lý gốc ta được J
2. Duyệt cây con trái J
3. Xử lý gốc ta đc Z
4. Duyệt cây con bên trái của Z
5. Xử lý gốc ta được B
6. duyệt cây con trái B
7. Xử lý gốc ta được Q
8. Duyệt cây con bên trai Q: không có cây con bên trai Q vậy là rỗng, chuyển sang duyệt cây con bên phải Q: Rỗng, không làm thao tác gì cả.
9. Chuyển sang duyệt cây con bên phải B
10. Xử lý gốc: ta được K
11. DUyệt cây con bên trái K: Rỗng, Duyệt cây con bên phải K: Rỗng.
12. Chuyển sang duyệt cây con bên phải Z
13. Xử lý gốc ta được R
14. Duyệt Cây con bên trái R: Rỗng, Duyệt cây con bên phải R: Rỗng
15. Duyệt cây con bên phải J
16. Xử lý gốc ta được A
17. DUyệt cây con Bên trái A: Rỗng, không làm gì cả
18. Duyệt cây con bên phải A
19. Xử lý Gốc ta được D
20. duyệt cây con bên trái D
21. Xử lý gốc được F
22. duyệt cây con bên trái F: Rỗng, Cây con bên phải F: Rỗng
23. Duyệ cây con bên phải D
24. xử lý gốc ta được L
25. Duyệt cây con bên trái L: Rỗng, Duyệt cây con bên phải L: Rỗng
26. Kết thúc sau quá trình duyệt ta có:J Z B Q K R A D F L

-Quá trình sẽ được viết ngắn gọn như sau:
- Procedure TBT(P) (P là con trỏ trỏ tới góc cây đã cho dưới dạng lưu trữ móc nối)
If P # null then
call TBT(LPTR(P)) (LPTR(P) chỉ cây con bên trái của P)
call TBT(RPTR(P)) (RPTR(P) chỉ cây con bên phải của P)
end
(Cứ mỗi lần call là lời gọi lại hàm TPT )