Bài giảng 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.2.3. Duyệt cây nhị phân 4.3. Cây nhị phân tìm kiếm 4.3.1. Cây nhị phân tìm kiếm 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 Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 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 Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 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 Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 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 Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 4 4.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 Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 5
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 Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 6
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 Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 7
ðườ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 Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 8
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 Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 9 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.4. Duyệt cây nhị phân Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 10 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 Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 11 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: 2i (i ≥ 0)
Số nút lá tối ña trên cây có chiều cao h la: 2h
Số lượng nút tối ña của cây có chiều cao h: 2h+1-1(h≥1 ) Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 12 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. Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 14 Nếu cây nhị phân ñầy ñủ. Có thể lưu trữ cây này bằng mãng 1 chiều Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 15 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ớ. Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 16  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 Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 17 Khai báo cấu cây typedef struct TNODE { Key;// là kiêu dư liêu cho key struct NODE *pLeft, *pRight; } *TREE; typedef struct TNODE { int Key; struct NODE *pLeft, *pRight; } *TREE; Ví vụ khai báo cây NP biểu diễn các nút là số nguyên Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 18  Duyệt cây nhị phân Duyệt theo thứ tự trước (NLR) Tại nút t ñang xét nếu khác rỗng - 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 void NLR(TREE t) { if (t != NULL) { ; NLR(t->pleft); NLR(t->pright); } } Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 19 Duyệt theo thứ tự giữa (LNR) Tại nút t ñang xét nếu khác rỗng - Duyệt cây con trái theo thứ giữa - Thăm gốc - Duyệt cây con phải theo thư tự giữa void LNR(TREE t) { if (t != NULL) { NLR(t->pleft); ; NLR(t->pright); } } Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 20 Duyệt theo thứ tự sau (LRN) Tại nút t ñang xét nếu khác rỗng - Duyệt cây con trái theo thứ sau - Duyệt cây con phải theo thư tự sau - Thăm gốc void LRN(TREE t) { if (t != NULL) { NLR(t->pleft); NLR(t->pright); ; } } Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 21 4.3. Cây Nhị Phân Tìm Kiếm 4.3.1. Cây nhị phân tìm kiếm 4.3.2. Các thao tác trên cây nhị phân tìm kiếm Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 22 4.3.1 Cây Nhị Phân Tìm Kiếm 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 NPTK ñược sử dụng vào nhiều mục ñích khác nhau. Tuy nhiên việc sử dụng cây NPTK ñể lưu giữ và tìm kiếm thông tin vẫn là một trong những ứng dụng quan trọng nhất ðịnh Nghĩa Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 23
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 Các Tính Chất Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 24 25 4.3.2 Các Thao Tác Trên Cây NPTK  Khai báo cấu trúc cây  Dựng cây – Thêm nút vào cây  Duyệt cây  Dựng cây từ kết quả duyệt cây  Tìm kiếm nút có giá trị x  Xóa nút có giá trị x trên cây  Hủy cây Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 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ớ) Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 26 27 Khai báo cấu cây typedef struct TNODE { Key;// là kiêu dư liêu cho key struct NODE *pLeft, *pRight; } *TREE; typedef struct TNODE { int Key; struct NODE *pLeft, *pRight; } *TREE; Ví vụ khai báo cây NPTK biểu diễn các nút là số nguyên Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net  Dựng cây – Thêm nút vào 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 Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 28 Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 29  Duyệt Cây 7 3 1 6 4 36 15 23 40 Duyệt theo thứ tự trước (NLR) Tại nút t ñang xét nếu khác rỗng - In giá trị nút t - Duyệt câycon trái theo thứ trước - Duyệt cây con phải theo thư tự trước void NLR(TREE t) { if (t != NULL) { coutkey<<“\t”; NLR(t->pleft); NLR(t->pright); } } Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 30 1 3 4 6 7 15 23 36 40 Duyệt theo thứ tự giữa (LNR) Tại nút t ñang xét nếu khác rỗng - Duyệt cây con trái theo thứ giữa - In giá trị nút t - Duyệt cây con phải theo thư tự giữa void LNR(TREE t) { if (t != NULL) { NLR(t->pleft); coutkey<<“\t”; NLR(t->pright); } } Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 31 1 4 6 3 23 15 40 36 7 Duyệt theo thứ tự sau (LRN) Tại nút t ñang xét nếu khác rỗng - Duyệt cây con trái theo thứ sau - Duyệt cây con phải theo thư tự sau - In giá trị nút t void LRN(TREE t) { if (t != NULL) { NLR(t->pleft); NLR(t->pright); coutkey<<“\t”; } } Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 32 Chương trình chính gọi các thủ tục dựng và duyêt cây Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 33  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 Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 34 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 Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 35  Tìm kiếm Ví dụ: Tìm nút có giá trị x=23 Tìm nút có giá trị x Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 36 Tìm nút có giá trị nhỏ nhất Tương tự cho nút có giá trị lớn nhất, Nút nhỏ nhất của cây con trái, nút lớn nhất của cây con phải Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 37  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á. Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 38 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 Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 39 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. Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 40 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 Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 41 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 Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 42 Thủ tục tìm nút thế mạng (phải nhất trên cây con trái) Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 43 Thủ tục xóa nút có giá X trên cây NPTK Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 44  Hủy toàn bộ cây Việc hủy toàn bộ cây thực hiện thông qua thao tác duyệt cây theo thứ tự sau Nếu nút t khác rỗng - Hủy cây con trái - Hủy cây con phải - Hủy nút t void removeTree(TREE &t) { if(t) { removeTree(t->pLeft); removeTree(t->pRight); delete(t); } } Khoa KTCN Trường ðH KTKT B.Dương© Dương Thành Phết-www.thayphet.net 45