Đang chuẩn bị liên kết để tải về tài liệu:
Phần tích thiết kế giải thuật (phần 3)

Trong tài liệu này các bạn sẽ hiểu thêm về các cấu trúc cây, cách thể hiện nó thông qua các dữ liệu được cung cấp sẵn, đồng thời các bạn cũng học thêm về các tính chất căn bản nhất về cây, một kiến thức nền quan trọng trong lập trình | Chương 2. Cấu trúc Cay. CHƯƠNG 2. CẤU TRÚC CÂY. 2.1 ĐỊNH NGHĨA THÍ DỤ. 2.1.1 CAY. Cấy lấ một đồ thị không định hương liên thông vấ không có chu trình. THÍ DỤ. FIG. 2.1. Cấy. Chiêu dấi cúa đương nôi hai đỉnh lai vơi nhau đươc gội lấ khôấng cấch giưa hai đỉnh. TÍNH CHAT. Giưa hai đỉnh bất ky cua môt cay sê cô duy nhất môt day chuyên nôi chung lai vơi nhau. Môt cay n đỉnh sê cô n -1 canh. Công thêm vàô cay môt canh giưa hai đỉnh bất ky sê taô nên môt chu trình duy nhất. 2.1.2 RỪNG. La môt đô thị không định hương va không cô chu trình Không liên thông manh Môi thanh phấn liên thông cua môt rưng la môt cấy. Trương Mỹ Dung 18 Chương 2. Cấu trúc Cay. 2.1.3 CÂÚ TRÚC CÂY CÂY CO GOC . Là một đồ thị có định hướng sao cho moi đỉnh đều có một đỉnh trước trừ một phan tử duy nhất khóng có đước gội là GOC. Với moi đỉnh x thì có duy nhất một đướng từ góc đi đến x. Xềt một đỉnh x cua một cày T có góc là r Một đỉnh y bất ky nàm trến đướng hướng từ góc đến x đừớc gội là càc ĐINH TRƯỚC ANCETRE cuà x và x đước là ĐINH SÂÚ DESCENDANT cuà y. Nếu x y là một cạnh cuà T tà gội x là CHÂ cuà y và y là CON củà x. Hài đỉnh cung chà đước gội là ÂNH EM. Một đỉnh khóng có con đước gội là lA. Nhưng đỉnh khong là LA đước gội là ĐỈNH TRONG. Chiều dài cuà đướng tư gốc đến đỉnh đước gội là độ sâu cuà đỉnh đó. Mức Niveau cuà một đỉnh trong T là khóàng càch tư gốc đến x. Mưc cuà nut gốc 0. Mưc cuà nut khàc gốc Mưc cuà cày con nhó nhất chưà nó 1. Chieu câộ hây độ sâu Hàutềur profondeur cuà cày là già trị lớn nhất cuà mưc cuà càc đỉnh trong cày. Nếu mỗi đỉnh trong cấy có tôi đa hai con thì ta gọi đó lấ cây nhị phân. Bậc của nút bậc của cây Degree . Bậc cua nut là số cây con cua nut đó. Bậc của cày là bậc lớn nhất của càc nút của cày. Nếu cày có bậc là n ta gói là cày n-cành. THÍ DỤ . Cày 3 - cành có góc với 8 đỉnh và có đó cao là 4. Trương Mỹ Dung 19 Chương 2. Cấu truc Cay. Đôi khi ta có the bieu diễn một quan hệ bao hàm thức cua nhiều tập hợp bang một cấu truc cay. Thí dụ. Bao ham cua cac tạp hợp sau cô .