Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4 - Ngô Công Thắng

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. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4 - Ngô Công Thắng1. Định nghĩa và khái niệm1.1. Đị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ọilà 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âyCHƯƠNG 4: CÂY (TREE)GV. Ngô Công ThắngBộ môn Công nghệ phần mềmKhoa Công nghệ thông tinWebsite: dse.hua.edu.vn/ncthangEmail: ncthang@vnua.edu.vnNgô Công Thắng1. Định nghĩa và khái niệm2. Cây nhị phân3. Cây tổng quát4. Ứng dụngBài giảng Cấu trúc dữ liệu và giải thuật - Chương 044.3Ví dụ 1: Mục lục của một chươngđược biểu diễn dạng câyChương 4: Cây (Tree)Ngô Công ThắngBài giảng Cấu trúc dữ liệu và giải thuật - Chương 04Chương 66.16.26.2.16.2.26.36.3.16.3.24.2Ngô Công ThắngBài giảng Cấu trúc dữ liệu và giải thuật - Chương 044.4Ví dụ 2: Biểu thức số học đượcbiểu diễn dạng cây1.2. Các khái niệmlx+y*(z-t)+u/vGố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 AlCấ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ắngBài giảng Cấu trúc dữ liệu và giải thuật - Chương 044.5Ngô Công ThắngVí dụ 3: Các tập bao nhau đượcbiểu diễn dạng câylBài giảng Cấu trúc dữ liệu và giải thuật - Chương 044.71.2. Các khái niệm (tiếp)Có các tập bao nhauA, B, C, D, E, FlLá (Leaf): Nút có cấp bằng không gọi là lá haynút tận cùng.Ví dụ 3: C,D,E,F là lá.lNút nhánh (Branch Node): Nút không là lá đượcgọi là nút nhánh hay nút trong.Ví dụ 3: B là nút nhánh.lMức (Level): Gốc cây có mức là 1. Nếu nút chacó 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ắngBài giảng Cấu trúc dữ liệu và giải thuật - Chương 044.6Ngô Công ThắngBài giảng Cấu trúc dữ liệu và giải thuật - Chương 044.81.2. Các khái niệm (tiếp)l1.2. Các khái niệm (tiếp)Chiều cao của cây (Height) hay chiều sâu củacây (Depth): Là số mức lớn nhất của nút có trêncây.Ví dụ 1: Cây có chiều cao là 3Ví dụ 2: Cây có chiều cao là 5Ví dụ 3: Cây có chiều cao là 3lĐường đi (Path): Nếu n1, n2, ..., nk là các dãy nútmà ni là cha của ni+1 (1≤i