Bài giảng Cấu trúc dữ liệu - Chương 3: Cây

Chia sẻ: Đinh Gấu | Ngày: | Loại File: PPT | Số trang:35

Thêm vào BST

Báo xấu

91
lượt xem 6
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 - Chương 3: Cây giới thiệu đến các bạn những nội dung về khái niệm cây, cây nhị phân, định nghĩa và tính chất, biểu diễn cây nhị phân, duyệt cây nhị phân. Mời các bạn tham khảo 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 - Chương 3: Cây

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 (chacon). – 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 Tí nh chấ t cua cây nhi phân: ̉ ̣ – Số lượng tố i đa cua mô ̉ ̃ i nú t ở mứ c i trên cây nhi phân la ̣ ̀ 2i1 (i ≥ 1). – Số lượng tố i đa cua mổ ̃ i nú t 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 đâ ̣ ̉ ̀ng 1 vector V ̀y đu bă theo nguyên tắc nút 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 ca ̣ ̉ ̣ ̉ ́c phần tử 15
3.2.2 BIỂU DIỄN CÂY NHỊ PHÂN BẰNG CÁCH 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 trúc mang la ̀ khó và mất thời gian trong viêc bô sung, loai bo ̣ ̉ ̣ ̉ các nút thường xuyên, đê khă ̉ ̣ ́c phuc ta ̉ ưu trữ bằng cách lưu trữ móc có thê l nối. Trường hợp này ta móc nối trực tiếp nút cha với nút 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