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

Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 3: Cây. Chương này có nội dung trình bày về: định nghĩa và khái niệm cơ bản; một số phép toán trên cây; cài đặt cây; cây nhị phân; cây tìm kiếm nhị phân; cây cân bằng; . Mời các bạn cùng tham khảo! | 8 4 2020 Cài đặt bởi mảng Ưu điểm Truy cập nhanh ngẫu nhiên và như nhau đối với mọi phần tử nhờ vào chỉ số Thao tác tìm kiếm dễ dàng Nhược điểm Kích thước mảng trong mọi ngôn ngữ lập trình đều cố định Hạn chế độ dài của danh sách trong khi danh sách thường xuyên thêm bớt không cố định độ dài Việc thêm bớt khó khăn do phải dịch chuyển nhiều phần tử thời gian chạy là O n Cấu trúc dữ liệu và giải thuật 79 CHƯƠNG 3 CÂY 9t ĐỊnh nghĩa và khái niệm cơ bản Một số phép toán trên cây Cài đặt cây Cây nhị phân Cây tìm kiếm nhị phân Cây cân bằng Chương 3. Cây 80 40 8 4 2020 Định nghĩa và khái niệm cơ bản Định nghĩa Các khái niệm cơ bản về cây Chương 3. Cây 81 Định nghĩa Cây Tree Cây T là một bộ trong đó V Tập hữu hạn các phần tử nút E Tập hữu hạn cung thể hiện mối quan hệ phân cấp là quan hệ cha con . Kí hiệu T Nút gốc root là nút không phải là con của bất cứ nút nào Cây rỗng null tree là cây không có nút nào Chương 3. Cây 82 41 8 4 2020 Định nghĩa Các ví dụ về cấu trúc cây Mục lục của một cuốn sách Cấu trúc thư mục trên đĩa máy tính. Sơ đồ nhân sự của tổ chức Cây phả hệ Dùng cây để biểu diễn biểu thức số học chẳng hạn a b x c-d e Chương 3. Cây 83 Định nghĩa x - c a b d e Chương 3. Cây 84 42 8 4 2020 Các khái niệm cơ bản về cây Số các con của một nút gọi là cấp bậc degree của nút đó Nút có bậc bằng 0 gọi là nút lá leaf Các nút không phải nút lá gọi là nút nhánh branch Bậc cao nhất có trong các nút của một cây gọi là bậc của cây đó. Mức-Level Gốc của cây có mức 1 nếu một nút có mức i thì các nút con của nút đó có mức i 1. Chiều cao height của cây là số mức lớn nhất của các nút có trên cây đó Chương 3. Cây 85 Các khái niệm cơ bản về cây Cây có thứ tự là cây mà có xét đến thứ tự giữa các con của một nút Con trưởng con cực trái của 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 Cây có nhãn mỗi nút của