TAILIEUCHUNG - Kỹ thuật lập trình - Chapter 6

Tài liệu tham khảo giáo trình kỹ thuật lập trình gồm 6 chương - Chương 6 các thuật toán trên cấu trúc câY (Tree) | Kỳ thuật lập trì nh 105 CHƯƠNG 6 CÁC THUẬT TOÁN TRÊN CÂU TRÚC CÂY Tree Câ y là một cấu trúc dữ liệ u rất thông dụng và quan trọng trong nhiề u phạ m vi khá c nhau củ a kỹ thuạ t má y tí nh. Ví dụ Tổ chức cá c quan hệ họ hàng trong một gia phả mục lục của một cuốn sách xây dựng cấu trúc về cú pháp trong các trì nh biên dịch. Trong ch-ơng trì nh này chúng ta khảo sát các khái niệm cơ bản về cây các phép toá n trê n câ y nhị phâ n cũng nh- cá c phép toá n trê n cây nhị phâ n câ n bằ ng AVL tree và ứng dụng củ a hai loạ i câ y nhị phâ n tì m kiếm BST câ y nhị phâ n cân bằng AVL tree . I. PHÂN LOAI CÂY . Mô t số khái niê m cơ bản 1. Cây Cây là tạp hợp các phần tử gọi là nút một nút t-ơng tự nh- một phần tử của dã y có thể có kiểu bất kỳ. Các nút đ - ợc biểu diễn bởi 1 ký tự chữ một chuỗi một số ghi trong một vòng tròn. Một số định nghĩ a theo đệ quy Một nút đơn cũng chí nh là một cây. Các nút đ - ợc gọi là ở cùng một cây khi có đ - ờng đi giữa các nút này. Một cây sẽ bao gồm một nút gốc Root và m cây con trong mỗi cây con lại có một nút gốc và ml cây con nhỏ hơn . Một cây không có một nút nào cả gọi là cây rỗng. Ví dụ 1 Hì nh . Cây với nút gốc là A - A là nút gốc với 3 cây con lần l- ợt có 3 nút gốc riêng làứ B C D - Nút cha ancestor Nút con descendent A là nút cha của B C D G H là nút con của C G H không quan hệ cha con với A Kỳ thuật lập trì nh 106 VÝ du 2 Với đề cương một môn học T ta có thể biểu diễn dạng cây như sau CHƯƠNGI I. 2 CHƯƠNG II II. 1 H1 nh CHƯƠNG III 2. Nút cha Ancestor Nứt đứng trên của một nứt được gọi là nứt cha C là nứt cha của G H Nút con descendent Nứt đứng sau một nứt khác được gọi là nứt con của nứt đó. Nứt I J K là nứt con của nứt E 3. Bâc degree - Bạc của nứt là số cây con của nứt đó. C có bạc là 2 E có bạc là 3 H1 nh - Bạc của cây là bạc lớn nhất của các nứt trong cây. Cây trong h1 nh có bạc là 3. Cây bạc n đ ư ợc gọi là cây n phân như cây nhị phân cây tam phân. 4. Nút lá và nút trung gian - Nứt

• Kỹ thuật lập trình
• lập trình java
• lập trình hướng đối tượng
• ngôn ngữ lập trình
• java căn bản
• giáo trình java
• kinh nghiệm lập trình java
• kỹ thuật lập trình java
• hướng dẫn lập trình java
• tài liệu lập trình java
• lý thuyết lập trình java