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

Chia sẻ: You You | Ngày: | Loại File: PDF | Số trang:40

Thêm vào BST

Báo xấu

113
lượt xem 15
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ếm 1 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ản 2
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ốc 3
ðị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ành bằ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 r2
5.1.2. Một số khái niệm cơ bản Bậ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ên 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 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 ñi nế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ếu cá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 8
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.2.1. ðịnh Nghĩa Cây nhị phân là cây mà mỗi nút có tối ña hai cây con. ðối với cây con của một nút có phân biệt cây con trái và cây con 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. 13
Nếu cây nhị phân ñầy ñủ. Có thể lưu trữ cây này bằng mãng 1 chiều
Nếu cây nhị phân không ñầy ñủ thì cách lưu trữ này khô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ải
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.3. Các thao tác trên cây nhị phân tìm kiếm
4.3.1 ðịnh Nghĩa Câ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ộc câ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ân
4.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