tailieunhanh - Chương 4 CẤU TRÚC CÂY

Định nghĩa cây Cây là 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 của cây(root). Các nút có mối quan hệ phân cấp gọi là quan hệ ‘’cha-con’’ | Chương 4 CẤU TRÚC CÂY NỘI DUNG Các khái niệm cơ bản Cây nhị phân Cây tổng quát /54 CÁC KHÁI NIỆM CƠ BẢN Định nghĩa cây Cấp của cây Mức của cây Đường đi và độ dài đường đi trong cây Độ cao, độ sâu của nút trong cây Thứ tự các nút trong cây Phép duyệt cây Cây gán nhãn và cây biểu thức /54 Định nghĩa cây Cây là 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 của cây(root). Các nút có mối quan hệ phân cấp gọi là quan hệ ‘’cha-con’’ Định nghĩa đệ qui về cây Một nút là một cây gốc của cây chính là nút đó. Giả sử T1, T2, , Tn (n 1) là các cây có gốc tương ứng r1, r2, , rn. Khi đó cây T với gốc r được hình thành bằng cách cho r trở thành nút cha của các nút r1, r2, , rn /54 Định nghĩa cây T T1 T2 Tn r r2 rn r1 /54 Cấp của cây Cấp của nút trong cây là số con của nút Cấp của cây: Là cấp cao nhất của nút có trong cây. Cây có cấp n thì gọi là cây n - phân /54 Mức của cây Gốc của cây có mức là 1 Cha có mức là i thì con có mức | Chương 4 CẤU TRÚC CÂY NỘI DUNG Các khái niệm cơ bản Cây nhị phân Cây tổng quát /54 CÁC KHÁI NIỆM CƠ BẢN Định nghĩa cây Cấp của cây Mức của cây Đường đi và độ dài đường đi trong cây Độ cao, độ sâu của nút trong cây Thứ tự các nút trong cây Phép duyệt cây Cây gán nhãn và cây biểu thức /54 Định nghĩa cây Cây là 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 của cây(root). Các nút có mối quan hệ phân cấp gọi là quan hệ ‘’cha-con’’ Định nghĩa đệ qui về cây Một nút là một cây gốc của cây chính là nút đó. Giả sử T1, T2, , Tn (n 1) là các cây có gốc tương ứng r1, r2, , rn. Khi đó cây T với gốc r được hình thành bằng cách cho r trở thành nút cha của các nút r1, r2, , rn /54 Định nghĩa cây T T1 T2 Tn r r2 rn r1 /54 Cấp của cây Cấp của nút trong cây là số con của nút Cấp của cây: Là cấp cao nhất của nút có trong cây. Cây có cấp n thì gọi là cây n - phân /54 Mức của cây Gốc của cây có mức là 1 Cha có mức là i thì con có mức là i+1 Mức của cây là mức cao nhất của nút có trong cây /54 Đường đi và độ dài đường đi Dãy các nút n1, n2, ., nk được gọi là một đường đi trong cây T nếu ni là cha của ni+1 (1 i /54 Độ cao và độ sâu của nút Độ cao của một nút trong cây là số nút trong đường đi dài nhất từ nút đó tới lá Độ cao của cây là độ cao của nút gốc Độ sâu của một nút trong cây là số nút trong đường đi từ gốc tới nút đó /54 Thứ tự các nút trong cây Trong cây nếu nút n có các con là n1, n2,., nk thì ni (1 /54 Thứ tự các nút trong cây Trong cây nếu không tính tới thứ tự của các .