Phần 2 cuốn giáo trình "Cấu trúc dữ liệu và giải thuật" trình bày các nội dung: Giải quyết hai vấn đề rất quan trọng trong lập trình, đó là sắp xếp và tìm kiếm. Các giải thuật sắp xếp và tìm kiếm được đưa ra ở đây là các giải thuật đã được áp dụng rất nhiều trong thực tế, từ các giải thuật cơ bản với độ phức tạp cao, đến các giải thuật nâng cao. | Chương 6 - CẦY . Định nghĩa và các khái niệm Định nghĩa Cây là một tập hữu hạn các nút trong đó có một nút đặc biệt gọi là gốc. Giữa các nút có quan hệ phân cấp. - Quan hệ cha con và tuân theo một cách đệ quy như sau 1. Một nút là một cây nút đó đồng thời là gốc của cây 2. Nếu n là một nút và Tj T2 . T là các cây con với các gốc tương ứng là ni n2 n i c thì ta tạo ra các cây mới T bằng cách cho nút n l à c h a c ủ a c á c n ú t n i 112 11 . T a g ọ i c á c T i l à c á c c â y c o n c ủ a c â y T . Để thuận tiện người ta cho phép tồn tại cây rỗng không cỏ nút nào . Ví du 66 Biểu diễn biểu thức số học x y z-l u v Biểu diễn các tập bao nhau Đối với cây Một số khái niệm của cây - Số các con của một nút gọi là bậc của nút đó. Nếu nút mà có bậc bàng 0 thì gọi là lá. Nút không có lá là nút nhánh - Bậc cao nhất của nút có trên cây gọi là bậc của cây - G ố c c ủ a c â y c ó m ứ c là 1 c o n c ủ a n ó c ó m ứ c là i 1 c o n c ủ a n ú t có trên cây gọi là cấp của cây - Nếu cây có n nút cây nhị phân thì số mức sẽ là log2 n l lấy phần nguyên của log2 n - Chiêu cao chiều sâu của một cây là số mức lớn nhất của nút có trên cây - Nếu thứ tự các cây con của một nút được coi trọng thì cây đan xét được gọi là cây có thứ tự. Thông thường ta đánh thứ tự từ trái qua phải. Nhiều cây độc lậ với nhau gọi là rừng. . Cây nhị phân . Định nghĩa và các tính chất Định nghĩa cây nhị phân Là một cây mọi nút trên cây chi có tố đa hai nút con. Đối với cây con của mỗi nút người ta cũng phân biệi cây con trái và cây con phải. Cây nhị phân là cây có thứ tự. Tính chất Cây nhị phân suy biến có dạng của một danh sách tuyến tính Ví du Cây lệch trái Cây lệch phải Cây Zic-zắc 68 Cây nhị phân hoàn chinh cây nhị phân đầy đủ . Cây nhị phân hoàn chinh complete binary tree Các nút trừ mức cuối cùng đều đạt tối đa. Nhận xét Trong các cây có cùng số lượng nút Cây nhị phân suy biến có chiều cao lớn nhất Cây đầy đủ có chiều cao nhỏ nhất. Đối với cây nhị phân đầy đủ cần chú ý tới một số tính chất sau Bổ dề
