1.Khái niệm về cấu trúc cây

Định nghĩa : Cây là một cấu trúc dữ liệu đặc biệt, trong cây chứa tập hợp T các phần tử (hay còn gọi là nút của cây).

Một nút đặc biệt được gọi là gốc của cây. Nút gốc này là nút duy nhất không có nút cha.

Các nút còn lại được chia thành những tập rời nhau T1,T2 , … , Tn theo quan hệ phân cấp trong đó Ti (với i = 1,2,3….n) cũng là một cây.

Mỗi nút ở cấp i sẽ quản lý một số nút ở cấp i+1. Quan hệ này người ta còn gọi là quan hệ cha-con.

Một ví dụ về cây (nguồn Wikipedia)

2. Một số tính chất cơ bản của cây

Một số tính chất quan trong của cấu trúc dữ liệu cây sẽ được nêu ra ở dưới đây:

Minh họa về cây với các thành phần chính

  • Bậc của một nút: là số cây con của nút đó
  • Bậc của một cây : là bậc lớn nhất của các nút trong cây (số cây con tối đa của một nút thuộc cây ). Cây có bậc n thì gọi là cây n-phân. Ví dụ như cây có tối ta 2 nút thuộc cây ta sẽ gọi cây này là cây nhị phân.
  • Nút gốc : là nút không có nút cha.
  • Nút lá : là nút có bậc bằng 0 .
  • Nút nhánh : là nút có bậc khác 0 và không phải là gốc .
  • Mức của một nút :
    • Mức (gốc (T) ) = 0.
    • Gọi T1, T2, T3, … , Tn là các cây con của T0
    • Mức (T1) = Mức (T2) = … = Mức (Tn) = Mức (T0) + 1.
  • Độ dài đường đi từ gốc đến nút x : là số nhánh cần đi qua kể từ gốc đến x
  • Độ dài đường đi tổng của cây là:
    • trong đó Px là độ dài đường đi từ gốc đến X.
  • Rừng cây: là tập hợp nhiều cây trong đó thứ tự các cây là quan trọng.

3.Nhận xét về cấu trúc cây

Trong cấu trúc cây sẽ không tồn tại chu trình.

Tổ chức 1 cấu trúc cây sẽ cho phép truy cập nhanh đến các phần tử của nó.

Để thực hiện duyệt cây ta sẽ duyệt theo các cách như sau:

  • Duyệt tiền thứ tự
  • Duyệt trung thứ tự
  • Duyệt hậu thứ tự

Trong những bài sau, chúng ta sẽ tập chung chủ yếu vào cây nhị phân và cây nhị phân tìm kiếm, tuy nhiên các khái niệm trên là cần thiết để áp dụng cho việc sử dụng và cài đặt cây nhị phân tìm kiếm.