TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - Trần Minh Thái (Trường Đại học Hồng Bàng )

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" trình bày các khái niệm về cây nhị phân tìm kiếm, đặc điểm, định nghĩa kiểu dữ liệu, các lưu ý khi cài đặt, các thao tác. . | Chương 4. Cây nhị phân tìm kiếm Trần Minh Thái Email: minhthai@ Website: 1 Nội dung Khái niệm Đặc điểm Định nghĩa kiểu dữ liệu Các lưu ý khi cài đặt Các thao tác 2 2 Khái niệm Bậc của một nút: là số cây con của nút đó Nút gốc: là nút không có nút cha 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 2 2 2 1 1 0 0 0 0 3 Mức 4 Mức 3 Mức 2 Mức 1 Khái niệm Chiều dài đường đi đến nút x: là số nhánh cần đi qua kể từ gốc đến x Độ cao của cây: Độ sâu (mức) của nút lá thấp nhất 4 x Đặc điểm cây nhị phân tìm kiếm Là cây nhị phân Giá trị của một node bất kỳ luôn lớn hơn giá trị của tất cả các node bên trái và nhỏ hơn giá trị tất cả các node bên phải Nút có giá trị nhỏ nhất nằm ở trái nhất của cây Nút có giá trị lớn nhất nằm ở phải nhất của cây 5 7 3 36 1 6 15 40 23 4 Định nghĩa kiểu dữ liệu 6 typedef struct TNODE { Key; struct TNODE *pLeft, *pRight; } *TREE; Nút Giá trị Trỏ trái Trỏ phải TNODE Key pLeft pRight Ví dụ khai báo typedef struct TNODE { int Key; struct TNODE *pLeft, *pRight; } *TREE; 7 Các lưu ý khi cài đặt Bước 1: Khai báo kiễu dữ liệu biểu diễn cây Bước 2: Xây dựng hàm đưa dữ liệu (nhập) vào cây Bước 3: Xây dựng các thao tác duyệt, tìm kiếm, huỷ, 8 Cấu trúc chương trình 9 Khai báo cấu trúc cây Khởi tạo cây rỗng Xây dựng cây Các thao tác Hủy cây Các thao tác 1. Tạo cây 2. Duyệt cây 3. Cho biết các thông tin của cây 4. Tìm kiếm 5. Xoá node trên cây 10 Tạo cây 11 40 15 4 6 1 36 3 7 36 3 1 6 4 15 40 7 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 Hàm tạo cây 12 int ThemNut (TREE & t, int x) { if(t!=NULL) { if(x==t->Key) return 0; else { if(xKey) ThemNut(t->pLeft, x); else ThemNut(t->pRight, x); } } else { t=new TNODE; if(t==NULL) return -1; t->Key=x; t->pLeft=t->pRight=NULL; return 1; } } Duyệt cây Thứ tự trước (NLR) Thứ tự giữa (LNR) Thứ tự sau (LRN) 13 14 Bước Kết quả duyệt theo thứ tự NLR 1 7 L7 R7 2 3 L3 R3 R7 3 1 R3 R7 4 6 L6 R7 5 4 R7

• Cơ sở dữ liệu
• Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu
• Cây nhị phân tìm kiếm
• Định nghĩa kiểu dữ liệu
• Cài đặt dữ liệu
• Thao tác dữ liệu
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• tài liệu Cấu trúc dữ liệu và giải thuật
• giáo trình Cấu trúc dữ liệu và giải thuật
• bài giảng Cấu trúc dữ liệu và giải thuật
• bài tập Cấu trúc dữ liệu và giải thuật
• Ngôn ngữ diễn đạt giải thuật
• Thiết kế và phân tích giải thuật
• Giải thuật đệ quy
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Cơ sở dữ liệu
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Tổng quan về giải thuật
• Kiểu dữ liệu
• Các tiêu chuẩn đánh giá dữ liệu
• phân tích thiết kế
• thiết kế hướng đối tượng
• Cách diễn đạt giải thuật
• Phân tích giải thuật
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp