Cây như là một kiểu đặc biệt của đồ thị

2.1 Các thành phần chính của cây

Cây — là một kiểu đặc biệt của đồ thị, là đồ thị không chu kỳ và kết nối. Trong cây, có duy nhất một đường đi giữa bất kỳ cặp nút nào, điều này tạo nên cấu trúc phân cấp.

Các thành phần chính của cây:

1. Nút:

• Các phần tử chính của cây, chứa dữ liệu.
• Ví dụ, mỗi vòng tròn trong biểu đồ đại diện cho một nút.

2. Gốc:

• Nút không có nút cha. Nó là điểm bắt đầu của cây.
• Ví dụ, nút trên cùng trong biểu đồ.

3. Lá:

• Các nút không có nút con. Chúng nằm ở "cuối" của cây.
• Ví dụ, các nút ở dưới cùng biểu đồ.

4. Cạnh:

• Các kết nối giữa các nút. Xác định quan hệ cha con giữa các nút.
• Ví dụ, các đường nối các nút trong biểu đồ.

5. Cây con:

• Bất kỳ tập hợp con nào của cây, bao gồm một nút và tất cả các hậu duệ của nó.
• Ví dụ, nhánh của cây xuất phát từ một nút.

Những đặc điểm quan trọng của cây:

1. Chiều cao của cây:

• Độ dài của đường đi từ gốc đến lá xa nhất.
• Ví dụ, số lượng mức trong biểu đồ.

2. Độ sâu của nút:

• Độ dài của đường đi từ gốc đến nút đó.
• Ví dụ, số lượng mức từ gốc đến nút cụ thể.

2.2 Cây nhị phân

Có thể phân biệt các loại cây khác nhau. Hãy bắt đầu với loại đơn giản nhất.

Cây nhị phân — là cây mà mỗi nút có không quá hai nút con, được gọi là con trái và con phải.

Ví dụ về cây nhị phân:

Các loại đặc biệt của cây nhị phân:

Cây nhị phân đầy đủ:

Tất cả các mức của cây, trừ mức cuối cùng, đều đầy đủ, và tất cả các nút của mức cuối cùng được sắp xếp trái nhất có thể.

Cây nhị phân hoàn hảo:

Tất cả các nút bên trong đều có chính xác hai nút con, và tất cả các lá đều nằm ở cùng một mức.

Cây nhị phân cân bằng:

Chênh lệch chiều cao của các cây con bất kỳ của nút nào không vượt quá 1.

Cây nhị phân tìm kiếm:

Đối với bất kỳ nút nào, cây con trái chỉ chứa các nút với giá trị nhỏ hơn, và cây con phải chỉ chứa các nút với giá trị lớn hơn.

2.3 Cây n-ary

Cây n-ary – là cây trong đó mỗi nút có thể có không quá n nút con.

Các loại đặc biệt của cây n-ary:

1. Cây ternary (Ternary Tree):

Mỗi nút có không quá ba nút con.

2. Cây k-ary (k-ary Tree):

Mỗi nút có không quá k nút con.

Ví dụ về cây 3-ary (mỗi nút có không quá ba nút con):

2.4 Ví dụ về việc ứng dụng cây

1. Hệ thống file

Ứng dụng của cây: Đại diện cho cấu trúc phân cấp của các tệp và thư mục trong hệ điều hành.

Nút gốc đại diện cho thư mục gốc, các nút bên trong — là thư mục, và các lá — là tệp. Các thao tác bao gồm tạo, xóa và di chuyển tệp và thư mục.

2. Cây quyết định

Ứng dụng của cây: Phân tích và học máy để đưa ra quyết định.

Các nút bên trong đại diện cho câu hỏi hoặc điều kiện, các nhánh — cho các câu trả lời có thể, và các lá — là quyết định hoặc hành động cuối cùng. Ví dụ, chẩn đoán bệnh tật trong y học dựa trên triệu chứng.

3. Tài liệu XML/HTML

Ứng dụng của cây: Đại diện cấu trúc cho dữ liệu ở định dạng XML hoặc HTML.

Nút gốc đại diện cho toàn bộ tài liệu, các nút bên trong — là các thẻ và phần tử, và các lá — là các nút văn bản và thuộc tính. Điều này giúp trong việc phân tích và thao tác nội dung tài liệu.

4. Cấu trúc tổ chức

Ứng dụng của cây: Đại diện cho cấu trúc phân cấp trong các tổ chức và công ty.

Nút gốc đại diện cho giám đốc điều hành, các nút bên trong — là các quản lý và phòng ban, và các lá — là các nhân viên. Điều này giúp hình dung và quản lý cấu trúc tổ chức.

5. Trò chơi cờ vua

Ứng dụng của cây: Đại diện cho các nước có thể đi trong trò chơi.

Nút gốc đại diện cho trạng thái bắt đầu của trò chơi, các nút bên trong — là các nước có thể đi, và các lá — là các trạng thái kết thúc của trò chơi. Điều này giúp trong việc lập kế hoạch chiến lược và đưa ra quyết định trong các chương trình cờ vua.