Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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,. nội dung chi tiết. | 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 X Y Z (Hình 1) (Hình 2) (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à chiều cao (height) của T. Cây rỗng có chiều cao là -1. 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à m-phâ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à m-phâ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 X Y Z (Hình 1) (Hình 2) (Hình 3) (Hình 4) 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 | 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 X Y Z (Hình 1) (Hình 2) (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
