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)
lượt xem 4
download
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.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: 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 1 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
- Cấu trúc của một node Giá trị data Nú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 } 7
- Ví dụ khai báo node chứa giá trị nguyên public 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 9
- 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 10
- 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 11
- Khai báo cấu trúc cây nhị phân public class CMyBinaryTree { CMyTNode root = null; //Nút gốc //Các phương thức } 12
- Chèn một phần tử có giá trị x vào cây: TNode(x) B1. Nếu root là null thì root = TNode(x) : Kết thúc B2. Trong khi root khác null thực hiện Nếu data của root x thì chèn TNode(x) vào bên trái root + Ngược lại: Trùng giá trị Kết thúc 13
- Tạo TNode có giá trị x public class CMyTNode { T data; CMyTNode pLeft = null; CMyTNode pRight = null; public CMyTNode(T x) { data = x; pLeft = null; pRight = null; } } 14
- public class CMyTNode { … public bool InsertData(T x){ if (x.CompareTo(data) == 0) return false; if (x.CompareTo(data) < 0) { if (pLeft == null) pLeft = new CMyTNode(x); else return pLeft.InsertData(x); } else { if (pRight == null) pRight = new CMyTNode(x); else return pRight.InsertData(x); } return true; } } 15
- public class CMyBinaryTree { CMyTNode root = null; public bool Insert(T x) { if (root == null) { root = new CMyTNode(x); return true; } else { if (root.InsertData(x)) return true; } return false; } }
- Bài tập 1. Viết phương thức 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 2. Viết phương thức tạo cây nhị phân số nguyên từ dãy số nguyên cho trước 17
- Duyệt cây Thứ tự trước (PreOrder) (NLR) Thứ tự giữa (InOrder) (LNR) Thứ tự sau (PostOrder) (LRN) 18
- 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 19
- Hàm duyệt NLR Tại node t đang xét, nếu khác rỗng thì public void NLR() { • In giá trị của t Xuất data; if(pLeft!=null) pLeft.NLR(); • Duyệt cây con bên trái if (pRight != null) của t theo thứ tự NLR pRight.NLR(); } • Duyệt cây con bên phải của t theo thứ tự NLR 20
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Cấu trúc dữ liệu - Bài 1:Tổng quan về cấu trúc dữ liệu và giải thuật
47 p | 175 | 17
-
Bài giảng Cấu trúc dữ liệu 1: Chương 1 - Lương Trần Hy Hiến
7 p | 162 | 9
-
Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài 8: Cấu trúc dữ liệu ngăn xếp
28 p | 77 | 9
-
Bài giảng Cấu trúc dữ liệu giải thuật: Các kiểu dữ liệu trừu tượng cơ bản - Cấu trúc dữ liệu tuyến tính
92 p | 116 | 9
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây đỏ đen - Bùi Tiến Lên
25 p | 81 | 8
-
Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 17: Cấu trúc dữ liệu dạng cây
21 p | 77 | 8
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu
193 p | 58 | 7
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (2016)
62 p | 94 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (Trường Đại học Hồng Bàng )
62 p | 159 | 6
-
Bài giảng Cấu trúc dữ liệu - Chương 3: Cấu trúc cây
65 p | 58 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây AA - Bùi Tiến Lên
30 p | 35 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 – Trần Minh Thái (2017)
67 p | 106 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây - Bùi Tiến Lên
68 p | 40 | 4
-
Bài giảng Cấu trúc dữ liệu: Chương 1 - ThS. Thiều Quang Trung (2018)
44 p | 43 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây AVL - Bùi Tiến Lên
38 p | 47 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - Ngô Quang Thạch
24 p | 58 | 3
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - Th.S Thiều Quang Trung
41 p | 68 | 3
-
Bài giảng Cấu trúc dữ liệu giải thuật: Cấu trúc dữ liệu
17 p | 50 | 2
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn