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

Chia sẻ: Nguoibakhong01 Nguoibakhong01 | Ngày: | Loại File: PPTX | Số trang:70

Thêm vào BST

Báo xấu

55
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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" cung cấp cho người học các kiến thức: Khái niệm, đặ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 chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 – Trần Minh Thái (2017)

Chương 5. Cây nhị phân tìm kiếm Trần Minh Thái Email: minhthai@huflit.edu.vn Website: www.minhthai.edu.vn 1
Nội dung 1. Khái niệm 2. Đặc điểm 3. Định nghĩa cấu trúc dữ liệu 4. Các lưu ý khi cài đặt 5. Các thao tác xử lý 2
Khá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ân 0 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 đi Mức 1 qua kể từ gốc đến x • Chiều cao h của cây: Mức 2 Mức lớn nhất của các nút lá Mức 3 Mức 4 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 5
Biể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 6
Định nghĩa kiểu dữ liệu dùng C Giá trị data Nút TNODE Trỏ trái Trỏ phải pLeft pRight typedef struct TNode { DataType data; TNode *pLeft, *pRight; } *Tree; 7
Ví dụ khai báo node chứa giá trị nguyên typedef struct TNode { int data; TNode *pLeft, *pRight; } *Tree; 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 9
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ỷ, … 10
Cấu trúc chương trình 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 11
Các thao tác cơ bản 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 12
Tạ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 13
Hàm thêm một phần tử vào cây int InsertNode (Tree & t, int x) { if(t!=NULL) { if(x==t>data) return 0; //Có giá trị trùng else { if(xdata) InsertNode(t>pLeft, x); else InsertNode(t>pRight, x); } } else { t=new TNode; if(t==NULL) return 1; //Thiếu bộ nhớ t>data=x; t>pLeft=t>pRight=NULL; return 1; //Thêm thành công } 14 }
Bài tập 1. Viết hàm tạo cây nhị phân số nguyên từ các giá trị nhập vào từ bàn phím. Quá trình nhập cho đến khi gặp giá trị trùng hoặc hết bộ nhớ 2. Viết hàm tạo cây nhị phân số nguyên từ dãy số nguyên cho trước 15
Duyệt cây Thứ tự trước (NLR) Thứ tự giữa (LNR) Thứ tự sau (LRN) 16
7 Bước Kết quả duyệt theo thứ tự NLR 1 7 L7 R7 3 36 2 3 L3 R3 R7 1 6 15 40 3 1 R3 R7 4 6 L6 R7 4 23 5 4 R7 6 36 L36 R36 7 15 R15 R36 8 23 R36 9 40 KQ 7 3 1 6 4 36 15 23 40 17
Hàm duyệt NLR Tại node t đang xét, nếu khác void NLR (Tree t) rỗng thì { • In giá trị của t if(t!=NULL) • Duyệt cây con bên trái của t { theo thứ tự NLR cout
Bài tập Vẽ cây nhị phân tìm kiếm theo thứ tự nhập từ trái sang phải và duyệt cây theo thứ tự trước: • 27; 19; 10; 21; 35; 25; 41; 12; 46; 7 • H; B; C; A; E; D; Z; M; P; T • Huế; Đà Nẵng; Hà Nội; Vĩnh Long; Cần Thơ; Sóc Trăng; Nha Trang; Đồng Nai; Vũng Tàu; An Giang; Tiền Giang; Bình Dương; Hải Dương 19
Bước Kết quả duyệt theo thứ tự LNR 7 1 L7 7 R7 2 L3 3 R3 7 R7 3 36 3 1 3 R3 7 R7 4 3 R3 7 R7 1 6 15 40 5 L6 6 7 R7 6 4 6 7 R7 4 23 7 6 7 R7 8 7 R7 9 L36 36 R36 10 15 R15 36 R36 11 23 36 R36 12 36 R36 13 40 KQ 1 3 4 6 7 15 23 36 20 40