Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4 - Đỗ Ngọc Như Loan

Chia sẻ: Dien_vi10 Dien_vi10 | Ngày: | Loại File: PPTX | Số trang:71

Thêm vào BST

Báo xấu

50
lượt xem 2
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 và giải thuật - Chương 4: Cây (Tree)" cung cấp cho người học các kiến thức: Khái niệm, cây nhị phân (binary tree), các thao tác tìm kiếm, duyệt cây nhị phân,... Mời các bạn cùng 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 và giải thuật: Chương 4 - Đỗ Ngọc Như Loan

GV: Đỗ Ngọc Như Loan
Khái niệm  Cây là một tập hữu hạn các nút (đỉnh) trong đó có một nút đặc biệt gọi là gốc (root)  Giữa các nút có quan hệ phân cấp gọi là “quan hệ cha con” và được biểu diễn bởi một cung (cạnh) từ cha đến con
A (Hình 1) (Hình 2) X Y Z (Hình 3) (Hình 4)
KHÁI NIỆM Cây được định nghĩa một cách đệ qui:  Một nút là một cây, nút đó cũng là gốc của cây  Nếu r là một nút và T1, T2, …, Tk là các cây với x1, x2, …, xk lần lượt là các gốc thì một cây mới T sẽ được tạo lập bằng cách cho r trở thành cha của các nút x1, x2, …, xk  Lúc này r là gốc còn T1, T2, …, Tk là các cây con (subtrees) của gốc (x1, x2, …, xk là con của nút r)
KHÁI NIỆM  Qui ước cho phép tồn tại cây không có nút nào và gọi đó là cây rỗng (null tree)  Nút gốc không có cha, các nút không có con gọi là các nút lá (leaf node), các nút có ít nhất 1 con là các nút trong (internal node)  Số con của một nút x trong cây T gọi là bậc (degree) của x  Độ dài đường đi (số cạnh) từ nút gốc r đến một nút x gọi là độ sâu (depth) của x trong T. Mức (level) của x = Độ sâu + 1.  Độ sâu lớn nhất của các nút trong T gọi là
Ví dụ
CÂY NHỊ PHÂN (BINARY TREE)  Cây mà mỗi nút chỉ có tối đa hai con gọi là cây nhị phân  Ví dụ:
(Hình 1) (Hình 2) (Hình 3) (Hình 4) X Y Z
Khái niệm  Một cây được gọi là mphân nếu số con nhiều nhất của một nút của cây là m.  Một cây được gọi là mphân đầy đủ nếu mọi nút trong có đúng m con.  Một cây nhị phân là cân bằng nếu tại mọi nút của cây, độ cao của cây con trái và cây con phải chênh lệch nhau không quá 1.  Nếu h là chiều cao của cây nhị phân cân bằng có n nút thì h
(Hình 1) (Hình 2) (Hình 3) (Hình 4) X Y Z
Biểu diễn cây nhị phân  Mỗi nút x, (ngoài thông tin dữ liệu được biểu diễn như một khóa), có hai con trỏ left và right chỉ đến con trái và con phải của nó trong cây nhị phân T  Nếu left[x] = NULL thì x không có con trái  Nếu right[x] = NULL thì x không có con phải  Nút gốc của cây T được trỏ bởi root[T]  Nếu root[T] = NULL thì cây T là rỗng
Biểu diễn cây nhị phân Nếu mỗi nút của cây biểu diễn một đối tượng có khóa là một số nguyên, có thể định nghĩa CTDL cây nhị phân trong C++ như sau: typedef struct CELL *TREE; struct CELL { int key; //trong thực tế có thêm nhiều dữ liệu khác TREE left, right; }; TREE T;
Duyệt cây nhị phân Có ba thứ tự duyệt cơ bản  Duyệt theo trung thứ tự (inorder tree walk LNR)  Duyệt theo tiền thứ tự (preorder tree walk NLR)  Duyệt theo hậu thứ tự (postorder tree walk LRN)
Inorder tree walk void InorderTreeWalk(TREE x) { if(x!=NULL) { InorderTreeWalk(x>left); cout
Cây nhị phân tìm kiếm (Binary search tree BST)  Là mô hình dữ liệu có nhiều ứng dụng trong thực tế  Khoá của các phần tử được lưu trữ thỏa mãn tính chất cây nhị phân tìm kiếm (binary search tree property) vNếu y là một nút trong cây con trái của nút x thì key[y] key[x]
Các thao tác trên bst  Khởi tạo cây  Các thao tác tìm kiếm  Chèn một nút vào cây  Xóa một núy trên cây
treeinitialize void TreeInitialize(TREE &T) { T=NULL; }
Các thao tác tìm kiếm  TreeSearch: Tìm một phần tử theo khoá cho trước  TreeMinimum: Tìm phần tử có khoá nhỏ nhất  TreeMaximum: Tìm phần tử có khoá lớn nhất
treesearch  Đầu vào là một pointer x chỉ đến gốc của cây nhị phân tìm kiếm và khoá k của phần tử cần tìm  Thủ tục trả về pointer chỉ đến nút có khoá k hoặc NULL  Dựa vào tính chất của cây nhị phân tìm kiếm để xác định nút nào phải tìm kế tiếp trong các con trái và phải của x v Nếu k
treesearch TREE TreeSearch(TREE x,int k) { if(x==NULL||k==x>key) return x; if(kkey) return TreeSearch(x>left,k); else return TreeSearch(x>right,k); }