TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu 1: Chương 4A - Huỳnh Cao Thế Cường

Chương 2 cung cấp kiến thức về cấu trúc cây (trees). Chương này gồm có những nội dung chính sau: Các thuật ngữ cơ bản trên cây, kiểu dữ liệu trừu tượng cây, cài đặt cây, cây nhị phân, cây tìm kiếm nhị phân. Mời các bạn tham khảo. | CẤU TRÚC DỮ LIỆU 1 Giảng viên phụ trách: HUỲNH CAO THẾ CƯỜNG Bộ môn Tin học email: hctcuong@ TRƯỜNG ĐẠI HỌC AN GIANG KHOA KỸ THUẬT- CÔNG NGHỆ - MÔI TRƯỜNG CẤU TRÚC CÂY (TREES) Các thuật ngữ cơ bản trên cây Kiểu dữ liệu trừu tượng cây Cài đặt cây Cây nhị phân Cây tìm kiếm nhị phân CÁC THUẬT NGỮ CƠ BẢN TRÊN CÂY Cây là một tập hợp các phần tử gọi là nút (nodes), trong đó có một nút được phân biệt gọi là nút gốc (root). Mối quan hệ cha - con (parenthood): để xác định hệ thống cấu trúc trên các nút. Mỗi nút, trừ nút gốc, có duy nhất một nút cha. Một nút có thể có nhiều nút con hoặc không có nút con nào. Mỗi nút biểu diễn một phần tử trong tập hợp đang xét Mối quan hệ cha con được biểu diễn theo qui ước nút cha ở dòng trên nút con ở dòng dưới và được nối bởi một đoạn thẳng. Các thuật ngữ cơ bản Định nghĩa Một nút đơn độc là một cây. Nút này cũng chính là nút gốc của cây. Giả sử ta có n là một nút đơn độc và k cây T1,, Tk với các nút gốc tương ứng là n1,, nk thì có thể xây dựng một cây mới bằng cách cho nút n là cha của các nút n1,, nk. Cây mới này có nút gốc là nút n và các cây T1,, Tk được gọi là các cây con. Tập rỗng cũng được coi là một cây và gọi là cây rỗng kí hiệu . Các thuật ngữ cơ bản Các thuật ngữ cơ bản Nếu n1,, nk là một chuỗi các nút trên cây sao cho ni là nút cha của nút ni+1, với i=1k-1, thì chuỗi này gọi là một đường đi trên cây (hay ngắn gọn là đường đi ) từ n1 đến nk. Độ dài đường đi được định nghĩa bằng số nút trên đường đi trừ 1. Như vậy độ dài đường đi từ một nút đến chính nó bằng không. Các thuật ngữ cơ bản a là tiền bối (ancestor) của b, còn b gọi là hậu duệ (descendant) của nút a: Nếu có đường đi từ nút a đến nút b một nút vừa là tiền bối vừa là hậu duệ của chính nó. Tiền bối hoặc hậu duệ của một nút khác với chính nó gọi là tiền bối hoặc hậu duệ thực sự. Trên cây nút gốc không có tiền bối thực sự. nút lá (leaf): là nút không có hậu duệ thực sự. nút trung gian (interior): Là nút không phải là lá Cây con của một cây là một nút

• Cơ sở dữ liệu
• Cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu
• Giải thuật
• Cơ sở dữ liệu
• Cấu trúc cây
• Kiểu dữ liệu trừu tượng cây
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• giáo trình cấu trúc dữ liệu
• bài tập cấu trúc dữ liệu
• đề cương cấu trúc dữ liệu
• lập trình dữ liệu
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Kiểu dữ liệu trừu tượng
• Kiểu dữ liệu cây
• Phân loại cây
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• Tài liệu Cấu trúc dữ liệu
• Cấu trúc dữ liệu căn bản
• Khái niệm cấu trúc dữ liệu
• Độ phức tạp thuật toán
• tiếp cận lập trình
• thuật toán
• thuật toán trong cấu trúc dữ liệu
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp