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

[mrszerono12]

CÂY, CÂY NHỊ PHÂN, CÂY NHỊ PHÂN TÌM KIẾM

1. Cấu trúc cây

1.1. Định nghĩa 1:

Cây là một tập hợp T các phần tử (nút trên cây) trong đó có 1 nút đặc biệt T0 được gọi là gốc, các nút còn khác được chia thành những tập rời nhau T1, T2 , . , Tn theo quan hệ phân cấp trong đó Ti cũng là một cây.
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.
1.2. Một số khái niệm cơ bản

- 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. Cây có bậc n thì gọi là cây n-phân.
- Nút gốc: nút không có nút cha.
- Nút lá: nút có bậc bằng 0 .
- Nút nhánh: 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 (T0 ) = 1.
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.
- Chiều cao h của cây: mức lớn nhất của các nút lá.Trích từ: http://www.kilobooks.com