tailieunhanh - Chương 11: Cây đa phân

Cây đa phân Cây rỗng Hoặc có một node gọi là gốc (root) và nhiều cây con. Biểu diễn: Mỗi node gồm có nhiều nhánh con Mỗi node có 2 liên kết first_child và next_sibling Dùng cây nhị phân | CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Chương 11: Cây đa phân Định nghĩa Cây đa phân Cây rỗng Hoặc có một node gọi là gốc (root) và nhiều cây con. Biểu diễn: Mỗi node gồm có nhiều nhánh con Mỗi node có 2 liên kết first_child và next_sibling Dùng cây nhị phân Chương 11: Cây đa phân Biểu diễn Chương 11: Cây đa phân Biểu diễn dạng nhị phân Nhị phân: left = black right = color Chương 11: Cây đa phân Cây từ điển: Trie Chương 11: Cây đa phân Thiết kế Trie class Trie { public: // Add method prototypes here. private: // data members Trie_node *root; }; const int num chars = 28; struct Trie_node { // data members Record *data; Trie_node *branch[num_chars]; // constructors Trie_node( ); }; Chương 11: Cây đa phân Giải thuật tìm kiếm trên Trie Algorithm trie_search Input: target là khóa cần tìm Output: mẫu tin tìm thấy 1. Bắt đầu tìm từ node root với ký tự đầu tiên của target 2. while (còn node để tìm và chưa xét hết chuỗi target) . Nhảy đến node con tương ứng tùy theo ký tự từ . | CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Chương 11: Cây đa phân Định nghĩa Cây đa phân Cây rỗng Hoặc có một node gọi là gốc (root) và nhiều cây con. Biểu diễn: Mỗi node gồm có nhiều nhánh con Mỗi node có 2 liên kết first_child và next_sibling Dùng cây nhị phân Chương 11: Cây đa phân Biểu diễn Chương 11: Cây đa phân Biểu diễn dạng nhị phân Nhị phân: left = black right = color Chương 11: Cây đa phân Cây từ điển: Trie Chương 11: Cây đa phân Thiết kế Trie class Trie { public: // Add method prototypes here. private: // data members Trie_node *root; }; const int num chars = 28; struct Trie_node { // data members Record *data; Trie_node *branch[num_chars]; // constructors Trie_node( ); }; Chương 11: Cây đa phân Giải thuật tìm kiếm trên Trie Algorithm trie_search Input: target là khóa cần tìm Output: mẫu tin tìm thấy 1. Bắt đầu tìm từ node root với ký tự đầu tiên của target 2. while (còn node để tìm và chưa xét hết chuỗi target) . Nhảy đến node con tương ứng tùy theo ký tự từ target . Xét ký tự kế tiếp trong chuỗi target 3. if (có node và dữ liệu của nó khác rỗng) . return dữ liệu của node này 4. return not_present End trie_search Chương 11: Cây đa phân Mã C++ tìm kiếm trên Trie Error_code Trie :: trie_search(const Key &target, Record &x) const { int position = 0; char next_char; Trie_node *location = root; while (location != NULL && (next_char = (position)) !=‘ ’) { location = location->branch[alphabetic order(next char)]; position++; } if (location != NULL && location->data != NULL) { x = *(location->data); return success; } else return not present; } Chương 11: Cây đa phân Giải thuật thêm vào Trie Algorithm trie_insert Input: new_entry là dữ liệu cần thêm vào Output: cây sau khi thêm vào dữ liệu mới 1. if (cây rỗng) . Thêm node mới vào đây . Kết thúc 2. Bắt đầu từ node root và ký tự đầu tiên trong khóa của new_entry 3. while (vẫn chưa xét hết chuỗi của khóa của new_entry) . next_char là ký tự hiện tại trên khóa . .