Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 4: Cây nhị phân

Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 4 trình bày các kiến thức liên quan đến cây nhị phân. Các nội dung chính trong chương này gồm có: Cấu trúc cây, cây nhị phân, cây nhị phân tìm kiếm. Mời các bạn cùng tham khảo để nắm bắt các nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 4: Cây nhị phân Chương 4 CÂY NHỊ PHÂN 4.1. Cấu trúc cây 4.1.1. ðịnh nghĩa 4.1.2. Một số khái niệm cơ bản 4.2. Cây nhị phân 4.2.1. ðịnh nghĩa 4.2.2. Một số tính chất của cây nhị phân 4.2.3. Biểu diễn cây nhị phân 4.3. Cây nhị phân tìm kiếm 4.3.1. ðịnh nghĩa 4.3.2 Các tính chất 4.3.2. Các thao tác trên cây nhị phân tìm kiếm1 4.4. Bài tập 4.1 Cấu Trúc Cây 4.1.1. ðịnh nghĩa cây 4.1.2. Một số khái niệm cơ bản2 4.1.1. ðịnh nghĩa cây ðịnh nghĩa 1: Một cây là tập hợp hữu hạn các nút trong ñó có một nút ñặc biệt gọi là gốc (root). Giữa các nút có một quan hệ phân cấp gọi là quan hệ cha con. Nút gốc3ðịnh nghĩa 2: Cây ñược ñịnh nghĩa ñệ qui như sau 1. Một nút là một cây và nút này cũng là gốc của cây. 2. Giả sử T1, T2, …,Tn (n ≥ 1) là các cây có gốc tươngứng r1, r2,…, rn. Khi ñó cây T với gốc r ñược hình thànhbằng cách cho r trở thành nút cha của các nút r1, r2,…, rn Nút gốc r T2 T1 r1 r25.1.2. Một số khái niệm cơ bảnBậc của một nút: Là số 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 có trêncâ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 Cây bậc 2 hay còn gọi là cây nhị phân Nút gốc: Là nút có 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à nút gốc Nút gốc Nút nhánh Nút lá Mức của một nút Mức (gốc (T0)) =0 Gọi T1, T2,..., Tn là các cây con của T0. Khi ñó Mức (T1) = Mức (T2) = ... = Mức (Tn) = Mức (T0) +1 Chiều cao của cây: Là số mức lớn nhất có trên cây ñó Cây có chiều cao là 3 ðường ñi: Dãy các ñỉnh n1,n2, ...,nk gọi là ñường ñinếu ni là cha của ni+1 (1 ≤ i ≤ k-1 ðộ dài của ñường ñi: Là số nút trên ñường ñi -1 ðộ dài ñường ñi là 3 Cây ñược sắp – Cây có thứ tự: Trong một cây, nếucác cây con của mỗi ñỉnh ñược sắp theo một thứ nhấtñịnh, thì cây ñược gọi là cây ñược sắp (cây có thứ tự). A 5 B C 3 84.2. Cây Nhị Phân 4.2.1. ðịnh nghĩa 4.2.2. Một số tính chất của cây nhị phân 4.2.3. Biểu diễn cây nhị phân4.2.1. ðịnh NghĩaCây nhị phân là cây mà mỗi nút có tối ña hai cây con. ðốivới cây con của một nút có phân biệt cây con trái và câycon phải.4.2.1. Một Số Tính Chất Của Cây Nhị Phân Số lượng tối ña các nút có ở mức i trên cây nhị phân là 2i -1 (i ≥ 1) Số lượng nút tối ña trên 1 cây nhị phân có chiều cao h là 2h-1(h ≥ 1 ) 4.2.3 Biễu Diễn Cây Nhị Phân Lưu trữ kế tiếp Phương pháp tự nhiên nhất ñể biểu diễn cây nhị phân là chỉ ra ñỉnh con trái và ñỉnh con phải của mỗi ñỉnh. Ta có thể sử dụng một mảng ñể lưu trữ các ñỉnh của cây nhị phân. Mỗi ñỉnh của cây ñược biểu gồm ba giá trị Infor: Mô tả thông tin gắn với mỗi ñỉnh Letf : Chỉ ñỉnh con trái Right: Chỉ ñỉnh con phải.13Nếu cây nhị phân ñầy ñủ. Có thể lưu trữ cây nàybằng mãng 1 chiềuNếu cây nhị phân không ñầy ñủ thì cách lưu trữ nàykhông thích hợp vì phí nhiều bộ nhớ. Lưu trữ móc nối Cách lưu trữ này khắc phục nhược ñiểm của cách lưu trữ kế tiếp ñồng thời phản ánh ñược dạng tự nhiên của cây. Cách lưu trữ này một phần tử có qui tắc sau: Infor: Mô tả thông tin gắn với mỗi ñỉnh Letf : Con trỏ trỏ tới cây con trái Right: Con trỏ trỏ tới cây con phải4.3. Cây Nhị Phân Tìm Kiếm 4.3.1. ðịnh nghĩa 4.3.2 Các tính chất 4.3.3. Các thao tác trên cây nhị phân tìm kiếm4.3.1 ðịnh NghĩaCây nhị phân tìm kiếm (CNPTK) là cây nhị phân thoả mãnñồng thời các ñiều kiện: Khoá các ñỉnh thuộc cây con trái nhỏ hơn khoá nút gốc Khoá nút gốc nhỏ hơn (hoặc bằng) khoá các ñỉnh thuộccây con phải Cây con trái và cây con phải của gốc cũng là CNPTK Cây nhị phân ñược sử dụng vào nhiều mục ñích khác nhau. Tuy nhiên việc sử dụng cây nhị phân ñể lưu giữ và tìm kiếm thông tin vẫn là một trong những áp dụng quan trọng nhất của cây nhị phân4.3.2 Các Tính Chất Nút có giá trị nhỏ nhất nằm ở trái nhất của cây Nút có giá trị lớn nhất nẳm ở phải nấht của cây Max Min ...