intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 21: Cây nhị phân tìm kiếm

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:14

Thêm vào BST
Báo xấu
43
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 – Bài 21: Cây nhị phân tìm kiếm" thông tin đến các bạn những kiến thức về khái niệm cây nhị phân tìm kiếm, các thao tác trên cây nhị phân tìm kiếm, một vài ví dụ sử dụng cây nhị phân tìm kiếm.

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 – Bài 21: Cây nhị phân tìm kiếm

  1. Cấu trúc dữ liệu và giải thuật Bài 21. Cây nhị phân tìm kiếm Giảng viên: TS. Ngo Huu Phuc Tel: 0438 326 077 Mob: 098 5696 580 Email: ngohuuphuc76@gmail.com 1 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  2. Bài 21: Cây nhị phân tìm kiếm Nội dung: 21.1. Khái niệm cây nhị phân tìm kiếm. 21.2. Các thao tác trên cây nhị phân tìm kiếm. 21.3. Một vài ví dụ sử dụng cây nhị phân tìm kiếm. Tham khảo: 1. Deshpande Kakde: C and Data structures.chm, Chapter 20: Linked Lists 2. Elliz Horowitz – Fundamentals of Data Structures.chm, Chapter 4: Linked Lists 3. Kyle Loudon: Mastering Algorithms with C.chm, Chapter 5 Linked Lists. 4. Bài giảng TS Nguyễn Nam Hồng 2 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  3. 21.1. Khái niệm về cây nhị phân tìm kiếm (1/4) Khái niệm:  Cây nhị phân tìm kiếm là cây rỗng hoặc cây mà node có chứa các khóa.  Các khóa của node trên cây con bên trái nhỏ hơn khóa của root, khóa của các node trên cây con bên phải lớn hơn khóa của root.  Cây con bên trái và phải cũng là cây nhị phân tìm kiếm.  Việc quản lý cây nhị phân thông qua node root. 3 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  4. 21.1. Khái niệm về cây NPTK (2/4) 50 30 60 25 40 70 35 65 Ví dụ về cây nhị phân tìm kiếm 4 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  5. 21.1. Khái niệm về cây NPTK (3/4) Một số tính chất của cây NPTK:  Cây nhị phân tìm kiếm là tập con của cây nhị phân, nên nó cũng có các cách duyệt LNR, LRN, NLR.  Với cây nhị phân tìm kiếm, nếu duyệt cây theo kiểu inorder ta sẽ được một dãy đã sắp theo chiều tăng dần.  Cây nhị phân tìm kiếm là cấu trúc tìm kiếm hiệu quả. Việc tìm kiếm trên cây nhị phân tìm kiếm nhanh hơn tìm kiếm tuần tự. Tuy nhiên, việc biểu diễn cây dạng mảng sẽ gây khó khăn cho việc thêm, bớt...  Với việc biểu diễn dạng liên kết, ta có độ phức tạp của việc tìm kiếm là O( logn). 5 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  6. 21.1. Khái niệm về cây NPTK (4/4) Cấu trúc cây nhị phân tìm kiếm: template struct tbnode { TreeEntry data; struct tbnode *lchild, *rchild; }; 6 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  7. 21.2. Các thao tác trên cây NPTK (1/) Một số thao tác trên cây nhị phân tìm kiếm: 1. Khởi tạo cây NPTK. 2. TBInsert: Thêm một node vào cây NPTK. 3. TBCount: đếm số node trên cây NPTK. 4. TBRInorder: duyệt cây dạng inorder. 5. TBRPostorder: duyệt cây dạng postorder. 6. TBRPreorder: duyệt cây dạng preorder. 7. TBLevelorder: duyệt cây dạng levelorder. 8. TBDelete: xóa node trên cây NPTK. 9. TBGetptr: định vị một node và node cha của nó. 7 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  8. 21.2. Các thao tác trên cây NPTK (2/) Khai báo lớp cây nhị phân tìm kiếm: template class TBTree { public: TBTree(); int TBInsert(TreeEntry value); int TBCount(); void TBRInorder(tbnode* treenode, QueueClassC *q); void TBRPostorder(tbnode* treenode, QueueClassC *q); void TBRPreorder(tbnode* treenode, QueueClassC *q); void TBInorder(QueueClassC* q); void TBPostorder(QueueClassC* q); void TBPreorder(QueueClassC* q); void TBLevelorder(QueueClassC* q); void TBGetptr(tbnode **father, tbnode **curr, TreeEntry value); int TBDelete(TreeEntry value); template friend void TreePrint(TBTree tree, int type); private: tbnode * root; }; 8 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  9. 21.2. Các thao tác trên cây NPTK (3/) Khởi tạo cây NPTK: template TBTree::TBTree() { root root=NULL; } NULL 9 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  10. 21.2. Các thao tác trên cây NPTK (4/) Thêm một node vào cây NPTK: root 1  Nếu cây rỗng, cấp phát ô nhớ cho con trỏ root. 50  Nếu cây không rỗng:  Sử dụng 2 con trỏ temp và temp1 để xác định vị trí cần thêm (con trỏ temp1 NULL NULL sẽ trỏ vào NULL, con trỏ temp sẽ trỏ vào node là cha của node mới).  Tùy thuộc vào giá trị mới được thêm 2 vào sẽ cấp phát ô nhớ cho temp->left 50 hay temp->right. 30 temp 60 25 40 Thêm node 70 có giá trị 35 NULL 45 65 45 vào cây NULL NULL 10 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  11. 21.2. Các thao tác trên cây NPTK (5/) temp1=temp1->lchild; Thêm một node vào cây NPTK else temp1=temp1->rchild; } if(temp->data>value) { template temp->lchild = (tbnode *) int TBTree::TBInsert(TreeEntry value) malloc(sizeof(tbnode)); { int kt=0; if(temp->lchild==NULL) { tbnode * temp, *temp1; printf("Khong du bo nho"); if(root==NULL) { return kt; } root = (tbnode *) kt=1; temp=temp->lchild; malloc(sizeof(tbnode)); temp->data=value; if (root==NULL) { temp->lchild=temp->rchild=NULL; printf("Khong du bo nho"); } return kt; } else { kt=1; temp->rchild = (tbnode *) root->data=value; malloc(sizeof(tbnode)); root->lchild=root->rchild=NULL; if(temp->rchild==NULL) { printf("Khong du bo nho"); } return kt; } else kt=1; { temp1=root; temp=temp->rchild; while(temp1!=NULL) { temp->data=value; temp=temp1; temp->lchild=temp->rchild=NULL; } if(temp1->data>value) } return kt; } 11 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University Tháng 09 năm 2009
  12. 21.2. Các thao tác trên cây NPTK (6/) Xóa một node trên cây NPTK: Xóa node không có con 12 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  13. 21.2. Các thao tác trên cây NPTK (7/) Xóa một node trên cây NPTK: Xóa node có 1 con 13 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
  14. 21.2. Các thao tác trên cây NPTK (8/) Xóa một node trên cây NPTK: Xóa node có 2 con 14 @copyright by PhD Ngo Huu Phuc, Le Quy Don Technical University
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

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

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2