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: Định nghĩa và khái niệm cây, cây nhị phân, cây tổng quát, ứng dụng cây. nội dung chi tiết. | 1. Định nghĩa và khái niệm . Định nghĩa cây (tree) l Cây là một tập hợp hữu hạn các nút, trong đó có một nút đặc biệt gọi là gốc (root). Giữa các nút có một quan hệ phân cấp gọi là quan hệ cha con. l Một cây không có nút nào gọi là cây rỗng (null tree). l Các ví dụ về cây CHƯƠNG 4: CÂY (TREE) GV. Ngô Công Thắng Bộ môn Công nghệ phần mềm Khoa Công nghệ thông tin Website: Email: ncthang@ Ngô Công Thắng 1. Định nghĩa và khái niệm 2. Cây nhị phân 3. Cây tổng quát 4. Ứng dụng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04 Ví dụ 1: Mục lục của một chương được biểu diễn dạng cây Chương 4: Cây (Tree) Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04 Chương 6 Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04 Ví dụ 2: Biểu thức số học được biểu diễn dạng cây . Các khái niệm l x+y*(z-t)+u/v Gốc (Root): Gốc là nút đặc biệt không có nút cha. Ví dụ 3: A là gốc. A là cha của B, E, F. B, E, F là con của A. B, E, F cũng là gốc của các cây con của A l Cấp (Degree): Số con của một nút gọi là cấp của nút đó. Ví dụ 3: A có cấp là 3. E, F có cấp là 0. B có cấp là 2. Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04 Ngô Công Thắng Ví dụ 3: Các tập bao nhau được biểu diễn dạng cây l Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04 . Các khái niệm (tiếp) Có các tập bao nhau A, B, C, D, E, F l Lá (Leaf): Nút có cấp bằng không gọi là lá hay nút tận cùng. Ví dụ 3: C,D,E,F là lá. l Nút nhánh (Branch Node): Nút không là lá được gọi là nút nhánh hay nút trong. Ví dụ 3: B là nút nhánh. l Mức (Level): Gốc cây có mức là 1. Nếu nút cha có mức là i thì nút con có mức là i+1. Ví dụ 3: A có mức là 1. B, E, F có mức là 2. C, D có mức là 3. Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04 Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04 . Các khái niệm
