TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu và giải thuật: Cây và cây nhị phân - Nguyễn Mạnh Hiển (HKI năm 2020-2021)

Bài giảng Cấu trúc dữ liệu và giải thuật: Cây và cây nhị phân cung cấp cho người học các kiến thức: Cây dữ liệu, cây nhị phân. Đây là một tài liệu hữu ích dành cho các bạn sinh viên ngành Công nghệ thông tin và những ai quan tâm dùng làm tài liệu học tập và nghiên cứu. | Cây và cây nhị phân Trees and Binary Trees Nguyễn Mạnh Hiển hiennm@ 2 Nội dung 1. Cây 2. Cây nhị phân 3 1. Cây 4 Định nghĩa cây Cây là một tập nút Nếu tập nút rỗng đó là cây rỗng. Nếu tập nút không rỗng Có một nút root được gọi là nút gốc. Có k cây con T1 T2 Tk k 0 sao cho nút gốc của mỗi cây con đó được nối với nút root bằng một cạnh. root được gọi là nút cha còn gốc của các cây con T1 T2 Tk được gọi là các nút con của root. 5 Ví dụ 1 Cấu trúc tổ chức của một công ty 6 Ví dụ 2 Cấu trúc hệ thống file 7 Các khái niệm về cây 1 Xét một cây có n nút Có một nút gốc Có n 1 cạnh vì mỗi nút trừ nút gốc có một cạnh liên kết nó với nút cha. 8 Các khái niệm về cây 2 Nút lá Nút không có con B C H . Nút anh em Các nút cùng cha K L M cùng cha là F . Nút ông E và nút cháu P Q . 9 Các khái niệm về cây 3 Đường đi từ nút n1 đến nút nk là dãy nút n1 n2 nk trong đó ni là cha của ni 1 1 i lt k . Chiều dài đường đi là số cạnh trên đường đi đó. Đường đi từ một nút tới chính nó có chiều dài bằng 0. 10 Các khái niệm về cây 4 Chiều sâu của nút ni là chiều dài đường đi từ nút gốc đến nút ni. Nút gốc có chiều sâu 0. Chiều sâu của cây bằng chiều sâu của nút lá sâu nhất. Chiều cao của nút ni là chiều dài của đường đi dài nhất từ nút ni đến một nút lá. Nút lá có chiều cao 0. Chiều cao của cây bằng chiều cao của nút gốc. Chiều cao của cây chiều sâu của cây. 11 Các khái niệm về cây 5 Nếu có đường đi từ nút n1 đến nút n2 Nút n1 được gọi là tổ tiên của nút n2 và nút n2 được gọi là hậu duệ của nút n1. Nếu n1 n2 thì ta có các khái niệm tổ tiên thực sự và hậu duệ thực sự. 12 Cài đặt cây Mỗi nút trong cây chứa Phần tử Con trỏ tới nút con đầu tiên Con trỏ tới nút anh em kế tiếp. Vì sao mỗi nút không struct TreeNode giữ con trỏ tới tất cả T elem các nút con của nó TreeNode firstChild TreeNode nextSibling 13 Ví dụ Biểu diễn con đầu tiên anh em kế tiếp 14 Duyệt cây Là cách đi qua tất cả các nút của cây sao cho mỗi nút chỉ được thăm xử lý đúng một lần. Thăm có thể là in giá trị trong nút đang xét

• Cơ sở dữ liệu
• Cấu trúc dữ liệu
• Cấu trúc dữ liệu và giải thuật
• Bài giảng Cấu trúc dữ liệu
• Cây và cây nhị phân
• Cây nhị phân
• 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 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
• Cơ sở dữ liệu
• 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