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: Cây nhị phân (tt) - Nguyễn Tri Tuấn

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

Thêm vào BST
Báo xấu
27
lượt xem 2
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Phần tiếp theo bài giảng "Cấu trúc dữ liệu và giải thuật: Cây nhị phân" cung cấp cho các bạn các kiến thức: Cây nhị phân tìm kiếm – Binary search tree, hàng đợi ưu tiên – Priority queue. 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: Cây nhị phân (tt) - Nguyễn Tri Tuấn

  1. Cây nhị phân  Các khái niệm và thuật ngữ cơ bản  Cài đặt cấu trúc dữ liệu  Duyệt cây  Cây nhị phân tìm kiếm – Binary Search Tree  Hàng đợi ưu tiên – Priority Queue Winter 2017 85 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  2. Cây nhị phân tìm kiếm (BST)  Ý nghĩa của cây BST  Binary Search Tree ADT  Cài đặt cấu trúc dữ liệu BST  Đánh giá/So sánh  Bài tập Winter 2017 86 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  3. Ý nghĩa của cây BST (1)  Tìm 1 phần tử trong cây nhị phân ?  Thuật toán ?  Chi phí ? Winter 2017 87 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  4. Ý nghĩa của cây BST (2)  Điểm yếu và điểm mạnh của mảng ?  Điểm yếu và điểm mạnh của danh sách liên kết ?  Một cấu trúc dữ liệu có được cả điểm mạnh của mảng và danh sách liên kết ? Winter 2017 88 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  5. Binary Search Tree ADT (1)  Cây nhị phân tìm kiếm là:  Một cây nhị phân  Mỗi node có một khóa (key)  Mỗi node p của cây đều thỏa: • Tất cả các node thuộc cây con trái đều có khóa nhỏ hơn khóa của p q  p->left: q->key < p->key • Tất cả các node thuộc cây con phải đều có khóa lớn hơn khóa của p q  p->right: q->key > p->key Winter 2017 89 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  6. Binary Search Tree ADT (2) Winter 2017 90 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  7. Binary Search Tree ADT (3) Winter 2017 91 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  8. Binary Search Tree ADT (4)  Các thao tác cơ bản:  Khởi tạo cây rỗng  Xóa cây  Thêm một node  Xóa một node  Tìm một node  Duyệt cây  Kiểm tra cây rỗng  Đếm số node trong cây  Tính chiều cao của cây Winter 2017 92 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  9. Cài đặt cấu trúc dữ liệu BST (1) template class BSTNode { public: T key; // key of node BSTNode *left; // pointer to left child BSTNode *right; // pointer to right child BSTNode() { } BSTNode(T newItem) { key = newItem; left = right = NULL; } }; // end class Winter 2017 93/203 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  10. Cài đặt cấu trúc dữ liệu BST (2) template class BINARY_SEARCH_TREE { private: BSTNode *root; // pointer to root of tree bool insertNode(BSTNode *&p, T newItem); bool removeNode(BSTNode *&p, T key); int countNode(BSTNode *p); int height(BSTNode *p); void LNR(BSTNode *p); void NLR(BSTNode *p); void LRN(BSTNode *p); public: BINARY_SEARCH_TREE(); // default constructor BINARY_SEARCH_TREE(const BINARY_SEARCH_TREE &aTree);// copy constructor ~BINARY_SEARCH_TREE(); // destructor // operations bool insert(T newItem); // add new node with ‘newItem’ bool remove(T key); // find and remove node with ‘key’ BSTNode*findNode(T key); // find node with ‘key’ bool isEmpty(); int countNode(); // call countNode(root) int height(); // call height(root) void preorder(); // call NLR(root) void inorder(); // call LNR(root) void postorder(); // call LRN(root) }; // end class Winter 2017 94 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  11. Tìm một node (1) Tìm key = 20 Winter 2017 95 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  12. Tìm một node (2) Jane Bob Tom Alan Ellen Nancy Wendy Tìm key = “Nancy" Winter 2017 96 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  13. Tìm một node (3) right==NULL  không tìm thấy Tìm key = 21  not found ! Winter 2017 97 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  14. Tìm một node (4) template BSTNode* BINARY_SEARCH_TREE::findNode(T key) { if (root==NULL) return NULL; BSTNode *p = root; while (p) { if (p->key==key) return p; // Tìm thấy else if (p->key > key) p = p->left; // Tìm nhánh trái else p = p->right; // Tìm nhánh phải } return NULL; // Không tìm thấy } Winter 2017 98 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  15. Thêm một node (1) Thêm key = “Frank" Jane Bob Tom Alan Ellen Nancy Wendy right==NULL  ngừng tìm kiếm  thêm node mới ở đây Winter 2017 99 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  16. Thêm một node (2) left==NULL  ngừng tìm kiếm Thêm key = 18  thêm node mới ở đây Winter 2017 100 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  17. Thêm một node (3) key đã tồn tại  không thêm nữa Thêm key = 20 Winter 2017 101 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  18. Thêm một node (4) Thêm các key: e,b,d,f,a,g,c Winter 2017 102 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  19. Xóa một node (1)  Các trường hợp xảy ra:  Xóa node lá  Xóa node chỉ có 1 cây con  Xóa node có 2 cây con Winter 2017 103 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
  20. Xóa một node (2) Xóa key = 4 (node lá) Winter 2017 104 (C) Nguyen Tri Tuan - Truong DH.KHTN DHQG-HCM CuuDuongThanCong.com https://fb.com/tailieudientucntt
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