Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 8: Cây - Đào Nam Anh

Data Structure and Algorithm 1 DATA STRUCTURE AND ALGORITHM Trees CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Cây Dr. Dao Nam Anh Data Structure and Algorithm 2 Resource - Reference Slides adapted from James B D Joshi, edit by Dao Nam Anh. Major Reference: • Robert Sedgewick, and Kevin Wayne, “Algorithms” Princeton University, 2011, Addison Wesley • Algorithm in C (Parts 1-5 Bundle)- Third Edition by Robert Sedgewick, Addison-Wesley • Cấu trúc dữ liệu và giải thuật, Đinh Mạnh Tường. • Giải thuật và lập trình, Lê Minh Hoàng, Đại Học Sư Phạm, 2002 Data Structure and Algorithm 3 Tree - Cây A B E C D F I G H Data Structure and Algorithm 4 Tree - Cây • Cây là một cấu trúc dữ liệu gồm một tập hữu hạn các nút, giữa các nút có một quan hệ phân cấp gọi là quan hệ "cha - con". • Có một nút đặc biệt gọi là gốc (root). A B E C D F I G H Data Structure and Algorithm 5 Tree - Cây • Có thể định nghĩa cây bằng các đệ quy như sau: Mỗi nút là một cây, nút đó cũng là gốc của cây ấy A B E C D F I G H Data Structure and Algorithm 6 Tree - Cây • Đỉnh • Cha –con • Ngang hàng • Lá • Cây nhị phân: mọi nút trên cây chỉ có tối đa hai nhánh con. Với một nút thì người ta cũng phân biệt cây con trái và cây con phải của nút đó. A B E C D F I G H root sibling childparent Binary tree Leaves/terminal nodes Data Structure and Algorithm 7 Tree - Cây • Chiều cao (height) hay chiều sâu (depth) của một cây là số mức lớn nhất của nút có trên cây đó. • Một tập hợp các cây phân biệt được gọi là rừng (forest), một cây cũng là một rừng. Nếu bỏ nút gốc trên cây thì sẽ tạo thành một rừng các cây con. A B E C D F I G H Data Structure and Algorithm 8 Tree - Cây Ví dụ: • Mục lục của một cuốn sách với phần, chương, bài, mục • Cấu trúc thư mục trên đĩa • Gia phả của một họ tộc cũng có cấu trúc cây. • Một biểu thức số học gồm các phép toán cộng, trừ, nhân, chia A B E C D F I G H Data Structure and Algorithm 9 Biểu diễn cây Biểu diễn bằng mảng: • Nếu có một cây nhị phân đầy đủ, ta có thể đánh số cho các nút trên cây đó theo thứ tự lần lượt từ mức 1 trở đi, hết mức này đến mức khác và từ trái sang phải đối với các nút ở mỗi mức. • Trong trường hợp cây nhị phân không đầy đủ, ta có thể thêm vào một số nút giả để được cây nhị phân đầy đủ, và gán những giá trị đặc biệt cho những phần tử trong mảng T tương ứng với những nút này. Hoặc dùng thêm một mảng phụ để đánh dấu những nút nào là nút giả tự ta thêm vào. • Gặp phải sự lãng phí bộ nhớ vì có thể sẽ phải thêm rất nhiều nút giả vào thì mới được cây nhị phân đầy đủ. Data Structure and Algorithm 10 Biểu diễn cây bằng cấu trúc liên kết Data Structure and Algorithm 11 Biểu diễn cây bằng cấu trúc liên kết Data Structure and Algorithm 12 Biểu diễn cây bằng cấu trúc liên kết Data Structure and Algorithm 13 Biểu diễn cây bằng cấu trúc liên kết Data Structure and Algorithm 14 Biểu diễn cây bằng cấu trúc liên kết Data Structure and Algorithm 15 Biểu diễn cây bằng cấu trúc liên kết Data Structure and Algorithm 16 Binary tree – Cây nhị phân • Cây nhị phân suy biến (degenerate binary tree), các nút không phải là lá chỉ có một nhánh con. • Trong các cây nhị phân có cùng số lượng nút như nhau thì cây nhị phân suy biến có chiều cao lớn nhất, còn cây nhị phân hoàn chỉnh thì có chiều cao nhỏ nhất. • Số lượng tối đa các nút trên mức i của cây nhị phân là 2i-1, tối thiểu là 1 (i ≥ 1). • Số lượng tối đa các nút trên một cây nhị phân có chiều cao h là 2h-1, tối thiểu là h (h ≥ 1). • Cây nhị phân hoàn chỉnh có n nút thì chiều cao là h = [lg(n)] + 1. Data Structure and Algorithm 17 Duyệt cây nhị phân • Preorder  Visit a node,  Visit left subtree,  Visit right subtree • Inorder  Visit left subtree,  Visit a node,  Visit right subtree • Postorder  Visit left subtree,  Visit right subtree  Visit a node A B E C D F I G H Data Structure and Algorithm 18 Duyệt cây nhị phân Duyệt theo thứ tự trước: • giá trị trong mỗi nút bất kỳ sẽ được liệt kê trước giá trị lưu trong hai nút con của nó Preorder • Visit a node, • Visit left subtree, • Visit right subtree A B C D E F G H I A B E C D F I G H Data Structure and Algorithm 19 Duyệt cây nhị phân Duyệt theo thứ tự giữa: • giá trị trong mỗi nút bất kỳ sẽ được liệt kê sau giá trị lưu ở nút con trái và được liệt kê trước giá trị lưu ở nút con phải của nút đó • Inorder  Visit left subtree,  Visit a node,  Visit right subtree C B D A G F H E I A B E C D F I G H Data Structure and Algorithm 20 Duyệt cây nhị phân Duyệt theo thứ tự sau: giá trị trong mỗi nút bất kỳ sẽ được liệt kê sau giá trị lưu ở hai nút con của nút đó • Postorder  Visit left subtree,  Visit right subtree  Visit a node C D B G H F I E A A B E C D F I G H Data Structure and Algorithm 21 Discussion – Câu hỏi • https://sites.google.com/site/daonamanhedu/data- structure-algorithm