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

Chia sẻ: Lelong Bao | Ngày: | Loại File: PPT | Số trang:35

Thêm vào BST

Báo xấu

68
lượt xem 5
download

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

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.

Chủ đề:

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

Lưu

Nội dung Text: Chương 3 Cây - Phần 2

CHƯƠNG 3- CÂY 1
Chương 3: Cây 3.1 Các khái niệm cơ bản 3.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 2
3.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 – Giữa các nút có một quan hệ thứ tự bộ phận (cha-con). – 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. 3
3.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 (branch 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. 4
3.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. 5
3.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. 6
3.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 7
3.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 8
3.2.1 ĐỊNH NGHĨA VÀ TÍNH CHẤT Tinh chât cua cây nhị phân: ́ ́ ̉ – Số lượng tôi đa cua môi nut ở mức i trên ́ ̉ ̃ ́ cây nhị phân là 2i-1 (i ≥ 1). – Số lượng tôi đa cua môi nut trên cây nhị ́ ̉ ̃ ́ phân có chiêu cao h là 2h -1 (h ≥ 1). ̀ ( Chứng minh) 9
3.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. 10
3.2.1 BIỂU DIỄN CÂY NHỊ PHÂN BẰ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 Ví du: ̣ A 1 C 3 B 2 D E F G 4 5 6 7 Ta lưu trữ cây nhị phân đây đủ băng 1 vector V theo ̀ ̀ nguyên tăc nut thứ i cua cây được lưu trữ ở V[i] ́ ́ ̉ 12
3.2.1 BIỂU DIỄN CÂY NHỊ PHÂN BẰNG CẤU TRÚC MẢNG Ví du: ̣ A B C D E F G V[1] V[2] V[3] V[4] V[5] V[6] V[7] 13
3.2.1 BIỂU DIỄN CÂY NHỊ PHÂN BẰ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. 14
3.2.1 BIỂU DIỄN CÂY NHỊ PHÂN BẰ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 – Khó khăn trong viêc bổ sung, loai bỏ cac phân ̣ ̣ ́ ̀ tử 15
3.2.2 BIỂU DIỄN CÂY NHỊ PHÂN BẰNG CACH LƯU TRỮ MÓC NỐI ́ Nhược điêm cua viêc lưu trữ cây nhị phân ̉ ̉ ̣ băng câu truc mang là khó và mât thời ̀ ́ ́ ̉ ́ gian trong viêc bổ sung, loai bỏ cac nut ̣ ̣ ́ ́ thường xuyên, để khăc phuc ta có 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. ́ ̀ ̉ 16
BIỂU DIỄN CÂY NHỊ PHÂN BẰNG MÓ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; typedef struct node { element_type element; struct node *left, *right; } NODE; 17
BIỂU DIỄN CÂY NHỊ PHÂN BẰNG MÓC NỐI CÁC NÚT Cây sẽ được trỏ bằng một con trỏ đến nút gốc cây. Kiểu Ref là kiểu con trỏ đến 1 nút; 18
Khai bao cây typedef int TData; typedef struct TNode{TData Data;  TNode* left;  TNode* right;  }; typedef TNode* TTree; 19
Khởi tạo cây rỗng void MakeNullTree(TTree *T) {  (*T)=NULL; } 20