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

1. Định nghĩa và khái niệm<br /> 1.1. Định nghĩa cây (tree)<br /> l Cây là một tập hợp hữu hạn các nút, trong<br /> đó có một nút đặc biệt gọi là gốc (root).<br /> Giữa các nút có một quan hệ phân cấp gọi<br /> là quan hệ cha con.<br /> l Một cây không có nút nào gọi là cây rỗng<br /> (null tree).<br /> l Các ví dụ về cây<br /> <br /> CHƯƠNG 4: CÂY (TREE)<br /> GV. Ngô Công Thắng<br /> Bộ môn Công nghệ phần mềm<br /> Khoa Công nghệ thông tin<br /> Website: dse.hua.edu.vn/ncthang<br /> Email: ncthang@vnua.edu.vn<br /> <br /> Ngô Công Thắng<br /> <br /> 1. Định nghĩa và khái niệm<br /> 2. Cây nhị phân<br /> 3. Cây tổng quát<br /> 4. Ứng dụng<br /> <br /> Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04<br /> <br /> 4.3<br /> <br /> Ví dụ 1: Mục lục của một chương<br /> được biểu diễn dạng cây<br /> <br /> Chương 4: Cây (Tree)<br /> <br /> Ngô Công Thắng<br /> <br /> Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04<br /> <br /> Chương 6<br /> 6.1<br /> 6.2<br /> 6.2.1<br /> 6.2.2<br /> 6.3<br /> 6.3.1<br /> 6.3.2<br /> <br /> 4.2<br /> <br /> Ngô Công Thắng<br /> <br /> Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04<br /> <br /> 4.4<br /> <br /> Ví dụ 2: Biểu thức số học được<br /> biểu diễn dạng cây<br /> <br /> 1.2. Các khái niệm<br /> l<br /> <br /> x+y*(z-t)+u/v<br /> <br /> Gốc (Root): Gốc là nút đặc biệt không có<br /> nút cha.<br /> Ví dụ 3: A là gốc. A là cha của B, E, F.<br /> B, E, F là con của A.<br /> B, E, F cũng là gốc của các cây con của A<br /> <br /> l<br /> <br /> Cấp (Degree): Số con của một nút gọi là<br /> cấp của nút đó.<br /> Ví dụ 3: A có cấp là 3. E, F có cấp là 0.<br /> B có cấp là 2.<br /> <br /> Ngô Công Thắng<br /> <br /> Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04<br /> <br /> 4.5<br /> <br /> Ngô Công Thắng<br /> <br /> Ví dụ 3: Các tập bao nhau được<br /> biểu diễn dạng cây<br /> l<br /> <br /> Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04<br /> <br /> 4.7<br /> <br /> 1.2. Các khái niệm (tiếp)<br /> <br /> Có các tập bao nhau<br /> A, B, C, D, E, F<br /> <br /> l<br /> <br /> Lá (Leaf): Nút có cấp bằng không gọi là lá hay<br /> nút tận cùng.<br /> Ví dụ 3: C,D,E,F là lá.<br /> <br /> l<br /> <br /> Nút nhánh (Branch Node): Nút không là lá được<br /> gọi là nút nhánh hay nút trong.<br /> Ví dụ 3: B là nút nhánh.<br /> <br /> l<br /> <br /> Mức (Level): Gốc cây có mức là 1. Nếu nút cha<br /> có mức là i thì nút con có mức là i+1.<br /> Ví dụ 3: A có mức là 1. B, E, F có mức là 2.<br /> C, D có mức là 3.<br /> <br /> Ngô Công Thắng<br /> <br /> Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04<br /> <br /> 4.6<br /> <br /> Ngô Công Thắng<br /> <br /> Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 04<br /> <br /> 4.8<br /> <br /> 1.2. Các khái niệm (tiếp)<br /> l<br /> <br /> 1.2. Các khái niệm (tiếp)<br /> <br /> Chiều cao của cây (Height) hay chiều sâu của<br /> cây (Depth): Là số mức lớn nhất của nút có trên<br /> cây.<br /> Ví dụ 1: Cây có chiều cao là 3<br /> Ví dụ 2: Cây có chiều cao là 5<br /> Ví dụ 3: Cây có chiều cao là 3<br /> <br /> l<br /> <br /> Đường đi (Path): Nếu n1, n2, ..., nk là các dãy nút<br /> mà ni là cha của ni+1 (1≤i