Chương 3 Cây - Phần 1

Cây gồm một tập hợp hữu hạn các nút-nodeCó một quan hệ thứ tự bộ phận (cha-con) giữa các nút.Có một nút đặc biệt, không là con của bất cứ nút nào và là tổ tiên của mọi nút trong cây, gọi là nút gốc (root).Cây không có nút nào gọi là cây rỗng.
Nội dung trích xuất từ tài liệu:
Chương 3 Cây - Phần 1CHƯƠNG 3- CÂY 1 Chương 3: Cây3.1 Các khái niệm cơ bản3.2 Cây nhị phân 3.2.1 Định nghĩa và tính chất 3.2.2 Biểu diễn cây nhị phân 3.2.3 Duyệt cây nhị phân 23.1 CÁC KHÁI NIỆM CƠBẢNKhái niệm cây: – Cây gồm một tập hợp hữu hạn các nút- node – Có một quan hệ thứ tự bộ phận (cha-con) giữa các nút. – Có một nút đặc biệt, không là con của bất cứ nút nào và là tổ tiên của mọi nút trong cây, gọi là nút gốc (root). – Cây không có nút nào gọi là cây rỗng. 33.1 CÁC KHÁI NIỆM CƠBẢNBậc – degree – của một nút là số con của nó.Nút lá (leaf) –terminal node – là nút không có con, bậc của nút lá bằng 0.Ngược với nút lá là các nút có con, gọi là nút phân nhánh hay nút trung gian (internal node).Bậc của cây là bậc cao nhất của các nút trong cây.Cây nhị phân là cây bậc 2. Nếu cây có bậc cao hơn 2 ta gọi là cây nhiều nhánh. 43.1 CÁC KHÁI NIỆM CƠBẢNMức – level – là đẳng cấp của nút trong mô hình phân cấp. Quy ước nút gốc có mức 1, nếu nút cha có mức i thì nút con có mức i + 1.Chiều cao – height – hay con gọi là chiều sâu – depth – là mức lớn nhất của nút trên cây.Đường đi – path – từ nút p đến nút q trên một cây là dãy nút p = n1,n2,…,nk = q sao cho ni là cha của ni+1. 53.1 CÁC KHÁI NIỆM CƠBẢNĐộ dài đường đi – path length – là số cung nối từng cặp hai nút trên đường đi, nó chính là số nút trừ 1.Cây có thứ tự - ordered tree – là cây mà có xét đến thứ tự giữa các con của một nút. Nói nôm na là có xét đến quan hệ “anh em”.Con trưởng hay con cực trái là một nút là con thứ nhất trong quan hệ thứ tự giữa các nút cùng cha.Em liền kề của một nút là nút đứng ngay sau trong quan hệ thứ tự giữa các nút cùng cha.Rừng – forest- là danh sách hữu hạn cây. 63.2 CÂY NHỊ PHÂN3.2.1 Định nghĩa và tính chất.3.2.2 Biểu diễn cây nhị phân.3.2.3 Duyệt cây nhị phân 73.2.1 ĐỊNH NGHĨA VÀ TÍNH CHẤTCây nhị phân là cây bậc 2, một nút có nhiều nhất là hai con.Cây nhị phân là cây có xét đến thứ tự, phân biệt con thứ nhất, con thứ hai gọi là con trái và con phải. Ba cây nhị phân này có cùng số nút nhưng có cấu trúc khác nhau 83.2.1 ĐỊNH NGHĨA VÀ TÍNH CHẤTTinh chât cua cây nhị phân: ́ ́ ̉ – Số lượng tôi đa cua môi nut ở mức i trên ́ ̉ ̃ ́ cây nhị phân là 2i-1 (i ≥ 1). – Số lượng tôi đa cua môi nut trên cây nhị ́ ̉ ̃ ́ phân có chiêu cao h là 2h -1 (h ≥ 1). ̀ ( Chứng minh) 93.2.1 BIỂU DIỄN CÂY NHỊ PHÂNBiểu diễn cây nhị phân bằng cấu trúc mảng.Biểu diễn cây nhị phân bằng danh sách các nút.Biểu diễn cây nhị phân bằng móc nối các nút. 103.2.1 BIỂU DIỄN CÂY NHỊ PHÂNBẰNG CẤU TRÚC MẢNG Với cây nhị phân hoàn chỉnh hoặc đầy đủ trái ta có thể dùng cấu trúc mảng để thể hiện một cây: Xếp liên tiếp các nút của cây vào mảng theo thứ tự từ trên xuống dưới, từ trái sang phải. Trường hợp một nút bị khuyết thì thay bằng giá trị đặc biệt ví dụ giá trị Null. 11 3.2.1 BIỂU DIỄN CÂY NHỊ PHÂN BẰNG CẤU TRÚC MẢNG Ví du: ̣ A 1 C 3 B 2 D E F G 4 5 6 7Ta lưu trữ cây nhị phân đây đủ băng 1 vector V theo ̀ ̀ nguyên tăc nut thứ i cua cây được lưu trữ ở V[i] ́ ́ ̉ 123.2.1 BIỂU DIỄN CÂY NHỊ PHÂNBẰNG CẤU TRÚC MẢNGVí du: ̣ A B C D E F G V[1] V[2] V[3] V[4] V[5] V[6] V[7] 133.2.1 BIỂU DIỄN CÂY NHỊ PHÂNBẰNG CẤU TRÚC MẢNGPhép xác định nút con trái và con phải: nút tại chỉ số mảng i có con trái tại chỉ số 2i và con phải tại chỉ số 2i+1.Phép xác định nút cha: nút tại chỉ số mảng j có cha tại chỉ số [j/2].Phép duyệt: là phép duyệt mảng. 143.2.1 BIỂU DIỄN CÂY NHỊ PHÂNBẰNG CẤU TRÚC MẢNGƯu điểm: – Triển khi nhanh. – Truy cập nhanh chóng vào bất kỳ nút nào, chi phí truy cập là đồng đều cho mọi nút.Nhược điểm: – Rất phí chỗ nếu cây “gầy”, khuyết nhiều nút – Khó khăn trong viêc bổ sung, loai bỏ cac phân ̣ ̣ ́ ̀ tử 153.2.2 BIỂU DIỄN CÂY NHỊ PHÂNBẰNG CACH LƯU TRỮ MÓC NỐI ́Nhược điêm cua viêc lưu trữ cây nhị phân ̉ ̉ ̣ băng câu truc mang là khó và mât thời ̀ ́ ́ ̉ ́ gian trong viêc bổ sung, loai bỏ cac nut ̣ ̣ ́ ́ thường xuyên, để khăc phuc ta có thể lưu ́ ̣ trữ băng cach lưu trữ moc nôi. ̀ ́ ́ ́Trường hợp nay ta moc nôi trực tiêp nut ̀ ́ ́ ́ ́ cha với nut con băng con tro. ́ ̀ ̉ 16BIỂU DIỄN CÂY NHỊ PHÂN BẰNGMÓC NỐI CÁC NÚTCấu trúc của một nút gồm 3 trường: – Data: chứa dữ liệu; – Left: trỏ đến nút con trái – Right: trỏ đến nút con phải typedef int element_type; ...