Đang chuẩn bị liên kết để tải về tài liệu:
Cấu trúc dữ liệu nâng cao P4

CÂY, CÂY NHỊ PHÂN, CÂY NHỊ PHÂN TÌM KIẾM | Bài 4 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á. 1.3. Một số ví dụ về đối tượng các cấu trúc dạng cây - Sơ đồ tổ chức của một doanh nghiệp - Sơ đồ tổ chức cây thư mục 1 2 2. CÂY NHỊ PHÂN 2.1 Định nghĩa Cây nhị phân là cây mà mỗi nút có tối đa 2 cây con Cây nhị phân có thể ứng dụng trong nhiều bài toán thông dụng. Ví dụ dưới đây cho ta hình ảnh của một biểu thức toán học