Phân tích và thiết kế giải thuật - Chương 4: Cây nhị phân

1Chươ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 4.4. Bài tập 24.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 34.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 Nút gốc r1 r2 r T1 T2 ðị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 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 lá Nút nhánh
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 B C 5 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 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. ðịnh Nghĩa 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 ) 13 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. 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
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 Min Max 4.3.2 Các Tính Chất 21 4.3.3 Các Thao Tác Trên Cây NPTK  Dựng cây  Duyệt cây  Dựng cây từ kết quả duyệt cây  Xóa nút trên cây  Dựng cây  Nếu nút cần thêm < nút ñang xét thì thêm về bên trái  Ngược lại thì thêm về bên phải  Duyệt Cây 7 3 1 6 4 36 15 23 40 Duyệt theo thứ tự trước (NLR) - Thăm gốc - Duyệt câycon trái theo thứ trước - Duyệt cây con phải theo thư tự trước 1 3 4 6 7 15 23 36 40 Duyệt theo thứ tự giữa (LNR) - Duyệt câycon trái theo thứ giữa - Thăm gốc - Duyệt cây con phải theo thư tự giữa 1 4 6 3 23 15 40 36 7 Duyệt theo thứ tự sau (LRN) - Duyệt câycon trái theo thứ sau - Duyệt cây con phải theo thư tự sau - Thăm gốc  Dựng cây từ kết quả duyệt cây 7 3 1 6 4 36 15 23 40 Dựng cây từ kết quả Duyệt theo thứ tự trước (NLR) - Chọn giá trị ñầu tiên làm nút gốc - Lần lượt ñưa các giá trị còn lại từ trái sang phải vào cây theo nguyên tắc dựng cây 1 4 6 3 23 15 40 36 7 Dựng cây từ kết quả duyệt theo thứ tự sau (LRN) - Chọn giá trị cuối cùng làm nút gốc - Lần lượt ñưa các giá trị còn lại từ phải sang trái vào cây theo nguyên tắc dựng cây  Xóa nút trên cây Xóa nút có khóa là :1 Xóa tiếp nút có khóa là :23 Xóa nút lá. Xóa nút có khóa là :6 Xóa tiếp nút có khóa là :15 7 3 36 4015 23 6 4 1 7 3 36 4015 23 41 7 3 36 402341  Xóa nút có 1 cây con 73 36 4015 23 6 4 1 Tìm nút thế mạng Cách 1: Tìm nút trái nhất của cây con phải Cách 2: Tìm nút phải nhất của cây con trái  Xóa nút có 2 cây con. Cách 1: Tìm nút trái nhất của cây con phải Xóa nút 3 (Dùng nút 4 trhay thế) 7 3 36 4015 23 5 4 1 6 7 4 36 4015 23 51 6 Cách 2: Tìm nút trái phải của cây con trái Xóa nút 36 (Dùng nút 23 thay thế) 7 3 36 4015 23 5 4 1 6 7 3 23 40155 4 1 6 33 4.4. Cài ðặt Cây NPTK Cấu trúc chương trình Các lưu ý khi cài ñặt - Bước 1: Khai báo kiểu dữ liệu biểu diễn cây - Bước 2: Xây dựng hàm ñưa dữ liệu (nhập) vào cây - Bước 3: Xây dựng các thao tác: Duyệt, Tìm, Hủy . . . Các lưu ý khác - Trước khi tạo nút phải xin cấp phát vùng nhớ - Trước khi tạo cây phải khởi tạo cây rỗng - Trước khi kết thúc chương trình phải hủy cây (Giải phóng vùng nhớ)
Khai báo cây NPTK kiểu dữ liệu cho nút là số nguyên
Thêm nút vào cây
Duyệt cây theo thứ tự NLR Tại nút t ñang xét nếu khác rỗng thì In giá trị t Duyệt cây con bên trái của t theo thứ tự NLR Duyệt cây con bên phải củ t theo thứ tự NLR
Duyệt cây theo thứ tự LNR Tại nút t ñang xét nếu khác rỗng thì Duyệt cây con bên trái của t theo thứ tự LNR In giá trị t Duyệt cây con bên phải củ t theo thứ tự LNR
Duyệt cây theo thứ tự LRN Tại nút t ñang xét nếu khác rỗng thì Duyệt cây con bên trái của t theo thứ tự LRN Duyệt cây con bên phải củ t theo thứ tự LRN In giá trị t