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

CẤU TRÚC DỮ LIỆU CÂY (TREE)

Chia sẻ: Jenny Pham | Ngày: | Loại File: PPT | Số trang:34

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

Cây là một tập hợp các phần tử (các nút) được tổ chức và có các đặc điểm sau:

Chủ đề:

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

Lưu

Nội dung Text: CẤU TRÚC DỮ LIỆU CÂY (TREE)

  1. CẤU TRÚC DỮ LIỆU CÂY (TREE) Thạc sĩ: HUỲNH PHƯỚC DANH Email: danhhp@sonadezi.edu.vn
  2. KHÁI NIỆM CÂY Cây là một tập hợp các phần tử (các nút) được tổ chức và có các đặc điểm sau:  Hoặc là một tập hợp rỗng (cây rỗng).  Hoặc là một tập hợp khác rỗng trong đó có một nút duy nhất được làm nút gốc (Root’s Node), các nút còn lại được phân thành các nhóm trong đó mỗi nhóm lại là một cây gọi là cây con (Sub-Tree). Như vậy, một cây con có thể là một tập rỗng các nút và cũng có thể là một tập hợp khác rỗng trong đó có một nút làm nút gốc cây con. ThS. Huỳnh Phước Danh -2- Cấu trúc dữ liệu và giải thuật
  3. CÁC KHÁI NIỆM  Bậc của một nút: là số 2 cây con của nút đó.  Nút gốc: là nút không có 2 2 nút cha.  Nút lá: là nút có bậc bằng 0 1 1 0 0.  Nút nhánh: là nút có bậc 0 0 khác 0 và không phải là gốc. ThS. Huỳnh Phước Danh -3- Cấu trúc dữ liệu và giải thuật
  4. CÁC KHÁI NIỆM  Độ dài đường đi từ Mức 0 gốc đến nút x: là số nhánh cần đi qua kể Mức 1 từ gốc đến x.  Độ cao của cây: Độ Mức 2 dài đường đi từ gốc đến nút lá ở mức Mức 3 thấp nhất. ThS. Huỳnh Phước Danh -4- Cấu trúc dữ liệu và giải thuật
  5. CÂY NHỊ PHÂN Cây nhị phân là cây rỗng hoặc là cây mà mỗi nút có tối đa hai nút con (cây có bậc bằng 2) . Hơn nữa các nút con của cây được phân biệt thứ tự rõ ràng, một nút con gọi là nút con trái và một nút con gọi là nút con phải. Ta qui ước vẽ nút con trái bên trái nút cha và nút con phải bên phải nút cha, mỗi nút con được nối với nút cha của nó bởi một đoạn thẳng. ThS. Huỳnh Phước Danh -5- Cấu trúc dữ liệu và giải thuật
  6. CÂY NHỊ PHÂN A A Root B C B C D E F H D E F H G K G K ThS. Huỳnh Phước Danh -6- Cấu trúc dữ liệu và giải thuật
  7. CẤU TRÚC DỮ LIỆU CÂY NHỊ PHÂN struct BinT_Node { info; BinT_Node *left; // Vùng liên kết quản lý địa chỉ nút gốc cây con trái BinT_Node *right; // Vùng liên kết quản lý địa chỉ nút gốc cây con phải }; BinT_Node Left Info Right ThS. Huỳnh Phước Danh -7- Cấu trúc dữ liệu và giải thuật
  8. DUYỆTCÂY NHỊ PHÂN  Duyệt theo thứ tự nút gốc trước (Preorder): Theo cách duyệt này thì nút gốc sẽ được duyệt trước, sau đó mới duyệt đến hai cây con. Căn cứ vào thứ tự duyệt hai cây con mà chúng ta có hai cách duyệt theo thứ tự nút gốc trước:  Duyệt nút gốc, duyệt cây con trái, duyệt cây con phải (Root – Left – Right)  Duyệt nút gốc, duyệt cây con phải, duyệt cây con trái (Root – Right – Left) ThS. Huỳnh Phước Danh -8- Cấu trúc dữ liệu và giải thuật
  9. DUYỆTCÂY NHỊ PHÂN Thuật giải void Traversal_NLR(BinT_Node* Root) { A if (Root = = NULL) return; B H cout info left); C D K L Traversal_NLR(Root->right); } E F M A, B, C, D, E, F, H, K, L, M  ThS. Huỳnh Phước Danh -9- Cấu trúc dữ liệu và giải thuật
  10. DUYỆTCÂY NHỊ PHÂN  Duyệt theo thứ tự nút gốc giữa (Inorder): Theo cách duyệt này thì chúng ta duyệt một trong hai cây con trước rồi đến duyệt nút gốc và sau đó mới duyệt cây con còn lại. Căn cứ vào thứ tự duyệt hai cây con chúng ta cũng sẽ có hai cách duyệt theo thứ tự nút gốc giữa:  Duyệt cây con trái, duyệt nút gốc, duyệt cây con phải (Left – Root – Right)  Duyệt cây con phải, duyệt nút gốc, duyệt cây con trái (Right – Root – Left) ThS. Huỳnh Phước Danh - 10 - Cấu trúc dữ liệu và giải thuật
  11. DUYỆTCÂY NHỊ PHÂN Thuật giải A void Traversal_LNR(BinT_Node* Root) { B H if (Root = = NULL) return; Traversal_LNR(Root->left); C D K L cout info right); E F M } C, B, E, D, F, A, K, H, M, L ThS. Huỳnh Phước Danh - 11 - Cấu trúc dữ liệu và giải thuật
  12. DUYỆTCÂY NHỊ PHÂN  Duyệt theo thứ tự nút gốc sau (Postorder): Tương tự như duyệt theo nút gốc trước, trong cách duyệt này thì nút gốc sẽ được duyệt sau cùng so với duyệt hai nút gốc cây con. Do vậy, căn cứ vào thứ tự duyệt hai cây con mà chúng ta cũng có hai cách duyệt theo thứ tự nút gốc sau: Duyệt cây con trái, duyệt cây con phải, duyệt nút gốc (Left – Right – Root) Duyệt cây con phải, duyệt cây con trái, duyệt nút gốc (Right – Left – Root) ThS. Huỳnh Phước Danh - 12 - Cấu trúc dữ liệu và giải thuật
  13. DUYỆTCÂY NHỊ PHÂN Thuật giải void Traversal_LRN(BinT_Node* Root) A { if (Root == NULL) return; B H Traversal_LRN(Root->left); C D K L Traversal_LRN(Root->right); cout info
  14. CÂY TÌM KIẾM NHỊ PHÂN Cây tìm kiếm nhị phân (TKNP) là cây nhị phân mà khoá tại mỗi nút cây lớn hơn khoá của tất cả các nút thuộc cây con bên trái và nhỏ hơn khoá của tất cả các nút thuộc cây con bên phải. Lưu ý: Dữ liệu lưu trữ tại mỗi nút có thể rất phức tạp như là một record chẳng hạn, trong trường hợp này khoá của nút được tính dựa trên một trường nào đó, ta gọi là trường khoá. Trường khoá phải chứa các giá trị có thể so sánh được, tức là nó phải lấy giá trị từ một tập hợp có thứ tự. ThS. Huỳnh Phước Danh - 14 - Cấu trúc dữ liệu và giải thuật
  15. CÂY TÌM KIẾM NHỊ PHÂN Ví dụ: hình minh hoạ một cây TKNP có khoá là số nguyên (với quan hệ thứ tự trong tập số nguyên). 20 10 35 5 17 22 42 15 30 ThS. Huỳnh Phước Danh - 15 - Cấu trúc dữ liệu và giải thuật
  16. CÂY TÌM KIẾM NHỊ PHÂN Qui ước: Cũng như tất cả các cấu trúc khác, ta coi cây rỗng là cây TKNP Nhận xét:  Trên cây TKNP không có hai nút cùng khoá.  Cây con của một cây TKNP là cây TKNP.  Khi duyệt trung tự (InOrder) cây TKNP ta được một dãy có thứ tự tăng. Chẳng hạn duyệt duyệt cây con phải (Left – Root - Right) cây trên ta có dãy: 5, 10, 15, 17, 20, 22, 30, 35, 42. ThS. Huỳnh Phước Danh - 16 - Cấu trúc dữ liệu và giải thuật
  17. CÂY TÌM KIẾM NHỊ PHÂN Tổ chức dữ liệu và khởi tạo Cài đặt cây tìm kiếm nhị phân Cây TKNP, trước hết, là một cây nhị phân. Do đó ta có thể áp dụng các cách cài đặt như đã trình bày trong phần cây nhị phân. Sẽ không có sự khác biệt nào trong việc cài đặt cấu trúc dữ liệu cho cây TKNP so với cây nhị phân, nhưng tất nhiên, sẽ có sự khác biệt trong các giải thuật thao tác trên cây TKNP như tìm kiếm, thêm hoặc xoá một nút trên cây TKNP để luôn đảm bảo tính chất cuả cây TKNP. ThS. Huỳnh Phước Danh - 17 - Cấu trúc dữ liệu và giải thuật
  18. CÂY TÌM KIẾM NHỊ PHÂN Tổ chức dữ liệu và khởi tạo struct BinT_Node { info; BinT_Node *Left; // Vùng liên kết quản lý địa chỉ nút gốc cây con trái BinT_Node *Right; // Vùng liên kết quản lý địa chỉ nút gốc cây con phải }; // Khai báo biến root quản lý cây nhi phan: BinT_Node* Root; //Khởi tạo cây nhi phan:  Root = NULL; ThS. Huỳnh Phước Danh - 18 - Cấu trúc dữ liệu và giải thuật
  19. CÂY TÌM KIẾM NHỊ PHÂN Tìm kiếm một nút có khóa cho trước trên cây TKNP Để tìm kiếm 1 nút có khoá x trên cây TKNP, ta tiến hành từ nút gốc bằng cách so sánh khoá của nút gốc với khoá x.  Nếu nút gốc bằng NULL thì không có khoá x trên cây.  Nếu x bằng khoá của nút gốc thì giải thuật dừng và ta đã tìm được nút chứa khoá x.  Nếu x lớn hơn khoá của nút gốc thì ta tiến hành (một cách đệ qui) việc tìm khoá x trên cây con bên phải.  Nếu x nhỏ hơn khoá của nút gốc thì ta tiến hành (một cách đệ qui) việc tìm khoá x trên cây con bên trái. ThS. Huỳnh Phước Danh - 19 - Cấu trúc dữ liệu và giải thuật
  20. CÂY TÌM KIẾM NHỊ PHÂN Ví dụ: tìm nút có khoá 30 trong cây ở bên 20  So sánh 30 với khoá nút gốc là 20, vì 30 > 20 vậy ta tìm tiếp trên cây con bên phải, tức là cây 35 10 có nút gốc có khoá là 35.  So sánh 30 với khoá của nút gốc là 35, vì 30 42 5 17 22 < 35 vậy ta tìm tiếp trên cây con bên trái, tức là cây có nút gốc có khoá là 22. 15 30  So sánh 30 với khoá của nút gốc là 22, vì 30 > 22 vậy ta tìm tiếp trên cây con bên phải, tức là cây có nút gốc có khoá là 30.  So sánh 30 với khoá nút gốc là 30, 30 = 30 vậy đến đây giải thuật dừng và ta tìm được nút chứa khoá cần tìm. ThS. Huỳnh Phước Danh - 20 - Cấu trúc dữ liệu và giải thuật
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