TAILIEUCHUNG - Cấu trúc dữ liệu : CÂY, CÂY NHỊ PHÂN, CÂY NHỊ PHÂN TÌM KIẾM) part 1

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 . Đị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. . Một số khái niệm cơ. | 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 . Đị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. . 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á. . 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. CÂY NHỊ PHÂN Đị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 2 . Một số tính chất của cây nhị phân - Số nút ở mức I 2I-1. - Số nút ở mức lá 2h-1 với h là chiều cao của cây. - Chiều cao của cây h log2N N - số nút trên trong cây . . Biểu diễn cây nhị phân T Cây nhị phân là một cấu trúc bao gồm các phần tử nút được kết nối với nhau theo quan hệ cha-con với mỗi cha có tối đa 2 con. Để biểu diễn cây nhị phân ta chọn phương pháp cấp phát liên kết. Ứng với một nút ta dùng một biến động lưu trữ các thông tin Thông tin lưu trữ tại nút. Địa chỉ nút gốc của cây con trái trong bộ nhớ. Địa chỉ nút gốc của cây con phải trong bộ nhớ. Khai báo như sau typedef struct tagTNODE Data Key Data là kiểu dữ liệu ứng với thông tin lưu tại nút struct tagNODE pLeft pRight

• Cơ sở dữ liệu
• Cấu trúc dữ liệu
• tài liệu Cấu trúc dữ liệu
• đề cương Cấu trúc dữ liệu
• giáo trình Cấu trúc dữ liệu
• bài giảng Cấu trúc dữ liệu
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• bài tập cấu trúc dữ liệu
• lập trình dữ liệu
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Cơ sở dữ liệu
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Kiểu dữ liệu trừu tượng
• Kiểu dữ liệu cây
• Phân loại cây
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• Cấu trúc dữ liệu căn bản
• Khái niệm cấu trúc dữ liệu
• Độ phức tạp thuật toán
• tiếp cận lập trình
• thuật toán
• thuật toán trong cấu trúc dữ liệu
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp