Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5.1 - Trần Minh Thái (2016)

Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 5: Cây nhị phân tìm kiếm – Cây cân bằng" cung cấp cho người học các khái niệm cây nhị phân tìm kiếm – Cây cân bằng, đặc điểm, định nghĩa cấu trúc dữ liệu, các lưu ý khi cài đặt, các thao tác xử lý. Mời các bạn cùng tham khảo.
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 5.1 - Trần Minh Thái (2016)Chương 5. Cây nhị phân tìm kiếm – Phần 1TrầnMinhTháiEmail:minhthai@huflit.edu.vnWebsite:www.minhthai.edu.vn 1Nội dung1. Khái niệm2. Đặc điểm3. Định nghĩa cấu trúc dữ liệu4. Các lưu ý khi cài đặt5. Các thao tác xử lý 2Khái niệm • Bậc của một nút: là số cây con của nút đó 2 • Bậc của cây: là bậc lớn nhất của các nút trong cây. Cây 2 2 có bậc n thì gọi là cây n- phân0 1 1 0 • Nút gốc: là nút không có nút cha 0 0 • Nút lá: là nút có bậc bằng 0 • Nút nhánh: là nút có bậc khác 0 và không phải là gốc 3 Khái niệm • Chiều dài đường đi đến nút x: là số nhánh cần điMức1 qua kể từ gốc đến x • Chiều cao h của cây:Mức2 Mức lớn nhất của các nút láMức3Mức4 x 4Đặc điểm của cây nhị phân• Số nút ở mức I 2I-1• Số nút ở mức lá 2h-1, với h là chiều cao của cây• Chiều cao của cây h log2N, với N là số nút trong cây 5Biểu diễn cây nhị phân• Cây nhị phân là một cấu trúc bao gồm các phần tử (node) được kết nối với nhau theo quan hệ “cha-con” với mỗi cha có tối đa 2 con.• Mỗi nút gồm các thông tin: • Dữ liệu lưu trữ: data • Liên kết tới cây con trái của nút: pLeft • Liên kết tới cây con phải của nút: pRight 6Cấu trúc của một node Giátrị dataNút TNode Trỏtrái Trỏphải pLeft pRight public class CMyTNode { T data; CMyTNode pLeft = null; CMyTNode pRight = null; //Các phương thức } 7Ví dụ khai báo node chứa giá trị nguyênpublic class CMyIntTNode{ int data; CMyIntTNode pLeft = null; CMyIntTNode pRight = null; //Các phương thức} 8 Cây nhị phân tìm kiếm • Là 1 cây nhị phân 7 • Giá trị của một node luôn lớn hơn giá trị của các 3 36 node nhánh trái và nhỏ1 6 15 40 hơn giá trị các node nhánh phải 4 23 Nút có giá trị nhỏ nhất nằm ở nút trái nhất của cây 9Các thao tác cơ bản1. Tạo cây2. Duyệt cây3. Cho biết các thông tin của cây4. Tìm kiếm5. Xoá node trên cây 10Tạo cây 7 36 3 1 6 4 15 40 317466 40 15 Ø Nếu node cần thêm nhỏ hơn node đang xét thì thêm về bên trái Ø Ngược lại thì thêm về bên phải 11Khai báo cấu trúc cây nhị phânpublic class CMyBinaryTree { CMyTNode root = null; //Nút gốc //Các phương thức} 12Chèn một phần tử có giá trị x vào cây:TNode(x)B1.Nếurootlànullthì root=TNode(x):KếtthúcB2.TrongkhirootkhácnullthựchiệnNếudatacủarootxthì chènTNode(x)vàobêntráiroot +Ngượclại:TrùnggiátrịKếtthúc 13Tạo TNode có giá trị xpublic class CMyTNode{ T data; CMyTNode pLeft = null; CMyTNode pRight = null; public CMyTNode(T x) { data = x; pLeft = null; pRight = null; }} 14public class CMyTNode{ … public bool InsertData(T x){ if (x.CompareTo(data) == 0) return false; if (x.CompareTo(data ...