zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

CÂY TRONG LẬP TRÌNH

Chia sẻ: Nguyen Quoc Khanh | Ngày: | Loại File: PPT | Số trang:22

Báo xấu

132
lượt xem 21
download

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

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.

Chủ đề:

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

Lưu

Nội dung Text: CÂY TRONG LẬP TRÌNH

4.1. Khái niệm – Biểu diễn cây 4.1.1. Định nghĩa 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.
4.1. Khái niệm – Biểu diễn cây 4.1.2. Một số khái niệm liên quan Root M ức 1 A M ức 2 B D C M ức 3 G E F M ức 4 H K L Bậc của nút – Bậc của cây (degree)  Bậc của nút là số cây con của nút đó.  Bậc của cây là bậc lớn nhất của các nút của cây. Nếu cây có bậc là n thì ta gọi là cây n phân. Ví Dụ: Bậc của nút A là 3, của B là 0, của D là 2. Bậc của cây là 3. Do đó ta gọi là cây tam phân.
4.1. Khái niệm – Biểu diễn cây 4.1.2. Một số khái niệm liên quan Root M ức 1 A M ức 2 B D C M ức 3 G E F M ức 4 H K L Nút gốc: Nút gốc (root’s node) là nút không ph ải là nút g ốc cây con c ủa b ất kỳ m ột cây con nào khác trong cây (nút không làm nút g ốc cây con). Nút kết thúc và Nút trung gian Nút kết thúc (hoặc nút lá – leaf) là nút có b ậc là 0 Nút trung gian là nút có bậc khác 0 và không ph ải là nút g ốc.
4.1. Khái niệm – Biểu diễn cây 4.1.2. Một số khái niệm liên quan Root M ức 1 A M ức 2 B D C M ức 3 G E F M ức 4 H K L Mức của nút và chiều cao của cây Mức của nút gốc bằng 1 Mức của nút khác gốc bằng mức của nút cha nó cộng 1 Chiều cao cây là mức lớn nhất của các nút lá Ví Dụ: B,C,D có mức là 2. Chiều cao cây là 4
4.1. Khái niệm – Biểu diễn cây 4.1.2. Một số khái niệm liên quan Root M ức 1 A M ức 2 B D C M ức 3 G E F M ức 4 H K L Nút cha và Nút con của một nút: Nút D được gọi là nút cha (parent’s node) c ủa nút E vì nút D là nút trước của nút E và mức của nút D lớn hơn mức của nút E là 1 mức. Khi đó, nút E được gọi là nút con (child’s node) của nút D.
4.1. Khái niệm – Biểu diễn cây 4.1.2. Một số khái niệm liên quan Root M ức 1 A M ức 2 B D C M ức 3 G E F M ức 4 H K L Chiều dài đường đi Chiều dài đường đi của nút: Chiều dài đường đi từ nút g ốc đến m ột nút x và cũng chính là mức của nút x đó. Chiều dài đường đi của cây: Là tổng của các chiều dài đường đi của tất cả các nút của cây và gọi là chiều dài đường đi trong (internal path length) của cây.
4.2. Cây nhị phân (Binary Tree) 4.2.1. Định nghĩa 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. A Root A B C C B D E F H H D E F K G G K
4.2. Cây nhị phân (Binary Tree) 4.2.2. Cấu Trúc dữ liệu cây nhị phân struct BinT_Node { info; // Vùng liên kết quản lý địa chỉ nút gốc cây con trái BinT_Node *left; // Vùng liên kết quản lý địa chỉ nút gốc cây con phải BinT_Node *right; }; BinT_Node Left Info Right
4.2. Cây nhị phân (Binary Tree) 4.2.3. Duyệt câ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) Thuật giải A void Traversal_NLR(BinT_Node* Root) { if (Root = = NULL) return; H B cout info left); L C D K Traversal_NLR(Root->right); } A, B, C, D, E, F, H, K, L, M M E F
4.2. Cây nhị phân (Binary Tree) 4.2.3. Duyệt câ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) Thuật giải A void Traversal_LNR(BinT_Node* Root) { if (Root = = NULL) return; H B Traversal_LNR(Root->left); L C D K cout info right); } C, B, E, D, F, A, K, H, M, L M E F
4.2. Cây nhị phân (Binary Tree) 4.2.3. Duyệt câ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) Thuật giải A void Traversal_LRN(BinT_Node* Root) { H if (Root == NULL) return; B Traversal_LRN(Root->left); L C D K Traversal_LRN(Root->right); cout info
4.3. Cây Tìm kiếm Nhị phân (Binary Search Tree) 4.3.1. Định Nghĩa 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 ự. 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 ố 20 nguyê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: 35 10  Trên cây TKNP không có hai nút cùng khoá. 42  Cây con của một cây TKNP là cây TKNP. 22 17 5  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 30 (Left – Root - Right) cây trên ta có dãy: 5, 10, 15, 17, 20, 15 22, 30, 35, 42.
4.3. Cây Tìm kiếm Nhị phân (Binary Search Tree) 4.3.2. 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. struct BinT_Node { info; // Vùng liên kết quản lý địa chỉ nút gốc cây con trái BinT_Node *Left; // Vùng liên kết quản lý địa chỉ nút gốc cây con ph ải BinT_Node *Right; }; // 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;
4.3. Cây Tìm kiếm Nhị phân (Binary Search Tree) 4.3.3. Các phép toá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. 20 Ví dụ: tìm nút có khoá 30 trong cây ở bêsn  So sánh 30 với khoá nút gốc là 20, vì 30 > 20 v ậy ta 35 10 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à 35.  So sánh 30 với khoá của nút g ốc là 35, vì 30 < 35 v ậy 42 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ó 22 17 5 khoá là 22.  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ó 30 15 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
4.3. Cây Tìm kiếm Nhị phân (Binary Search Tree) 4.3.3. Các phép toán Tìm kiếm một nút có khóa cho trước trên cây TKNP Hàm dưới đây trả về kết quả là con trỏ trỏ tới nút chứa khoá x ho ặc NULL n ếu không tìm th ấy khoá x trên cây TKNP. BinT_Node* TreeSearch(int x, BinT_Node* Root) { if (Root == NULL) return NULL; //không tìm thấy khoá x else if (Root->info == x) /* tìm thấy khoá x */ return Root; else if (Root->info < x) //tìm tiếp trên cây bên phải return TreeSearch(x,Root->right); return TreeSearch(x,Root->left); }
4.3. Cây Tìm kiếm Nhị phân (Binary Search Tree) 4.3.3. Các phép toán Thêm một nút có khóa cho trước vào cây TKNP Theo định nghĩa cây tìm kiếm nhị phân ta th ấy trên cây tìm ki ếm nh ị phân không có hai nút có cùng một khoá. Do đó nếu ta mu ốn thêm m ột nút có khoá x vào cây TKNP thì tr ước h ết ta phải tìm kiếm để xác định có nút nào chứa khoá x ch ưa. N ếu có thì gi ải thu ật k ết thúc (không làm gì cả!). Ng ược lại, sẽ thêm m ột nút m ới ch ứa khoá x này. Vi ệc thêm m ột khoá vào cây TKNP là việc tìm ki ếm và thêm m ột nút, t ất nhiên, ph ải đ ảm b ảo c ấu trúc cây TKNP không bị phá vỡ. Giải thuật cụ thể như sau: Ta tiến hành từ nút gốc bằng cách so sánh khóa cu ả nút g ốc v ới khoá x.  Nếu nút gốc bằng NULL thì khoá x chưa có trên cây, do đó ta thêm m ột nút m ới chứa khoá x.  Nếu x bằng khoá của nút gốc thì gi ải thu ật d ừng, tr ường h ợp này ta không thêm nút.  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) gi ải thu ật này 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) gi ải thu ật này trên cây con bên trái.
4.3. Cây Tìm kiếm Nhị phân (Binary Search Tree) 4.3.3. Các phép toán Thêm một nút có khóa cho trước vào cây TKNP 20 Ví dụ: thêm khoá 19 vào cây  So sánh 19 với khoá của nút g ốc là 20, vì 19 < 20 35 10 vậy ta xét tiếp đến cây bên trái, tức là cây có nút g ốc có khoá là10. 42 22 17 5  So sánh 19 với khoá của nút g ốc là 10, vì 19 > 10 vậy ta xét tiếp đến cây bên phải, t ức là cây có nút gốc có khoá là 17. 30 19 15  So sánh 19 với khoá của nút g ốc là 17, vì 19 > 17 vậy ta xét tiếp đến cây bên phải. Nút con bên ph ải bằng NULL, chứng tỏ rằng khoá 19 chưa có trên cây, ta thêm nút mới chứa khoá 19 và nút m ới này là con bên phải của nút có khoá là 17
4.3. Cây Tìm kiếm Nhị phân (Binary Search Tree) 4.3.3. Các phép toán Thêm một nút có khóa cho trước vào cây TKNP Thủ tục sau đây tiến hành vi ệc thêm m ột khoá vào cây TKNP. void InsertNode(int x, BinT_Node* &Root ) { if (Root == NULL) /* thêm nút mới chứa khoá x */ { Root=new BinT_Node(); Root->info= x; Root->left = NULL; Root->right = NULL; } else if (x < Root->Key) InsertNode(x , Root->left); else if (x > Root->Key) InsertNode(x , Root->right); }
4.3. Cây Tìm kiếm Nhị phân (Binary Search Tree) 4.3.3. Các phép toán Xóa một nút có khóa cho trước ra khỏi cây TKNP Giả sử ta muốn xoá một nút có khoá x, trước hết ta ph ải tìm ki ếm nút ch ứa khoá x trên cây.
4.3. Cây Tìm kiếm Nhị phân (Binary Search Tree) 4.3.3. Các phép toán Xóa một nút có khóa cho trước ra khỏi cây TKNP Việc xoá một nút như vậy, tất nhiên, ta phải b ảo đ ảm c ấu trúc cây TKNP không b ị phá v ỡ. Ta có các trường hợp như sau: Ví dụ về giải thuật xóa nút trên cây  Nếu không tìm thấy nút chứa khoá x thì gi ải thu ật k ết thúc.  Nếu tìm gặp nút N có chứa khoá x, ta có ba tr ường h ợp sau  Nếu N là lá ta thay nó bởi NULL.  N chỉ có một nút con ta thay nó b ởi nút con c ủa nó.  N có hai nút con ta thay nó b ởi nút l ớn nh ất trên cây con trái c ủa nó (nút c ực ph ải c ủa cây con trái) hoặc là nút bé nhất trên cây con ph ải c ủa nó (nút c ực trái c ủa cây con ph ải). Trong giải thuật sau, ta thay x bởi khoá của nút c ực trái c ủa cây con bên ph ải r ồi ta xoá nút c ực trái này. Việc xoá nút cực trái của cây con bên ph ải s ẽ r ơi vào m ột trong hai tr ường h ợp trên.

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.