TAILIEUCHUNG - Cấu trúc dữ liệu và giải thuật - chương 11

Chương 11: cây đa phân của bộ slide bài giảng đầy đủ về môn CTDL & GT của trường ĐHBK . Trình bày ngắn gọn dễ hiểu với những hiệu ứng minh họa sinh đa phân còn gọi là cây rỗng hoặc có một node gọi là gốc và nhiều cây con. | CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT (501040) 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 Biểu diễn Biểu diễn dạng nhị phân Nhị phân: left = black right = color Cây từ điển: Trie 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( ); }; 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 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; } 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 . if (node con tại vị trí next_char không có) //Tìm và thêm các node trung gian không có dữ liệu vào . Thêm một node có dữ liệu rỗng vào đây . Nhảy đến node con tương ứng với

• Kỹ thuật lập trình
• cấu trúc dữ liệu
• giải thuật
• stack vầ queue liên kết
• đệ qui
• danh sách và chuỗi
• sắp thứ tự
• cây nhị phân
• cây đa phân
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Bài giảng Cấu trúc dữ liệu
• Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• giáo trình cấu trúc dữ liệu
• bài tập cấu trúc dữ liệu
• đề cương cấu trúc dữ liệu
• lập trình dữ liệu
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Cơ sở dữ liệu
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Kiểu dữ liệu trừu tượng
• Kiểu dữ liệu cây
• Phân loại cây
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• Tài liệu Cấu trúc dữ liệu
• Cấu trúc dữ liệu căn bản
• Khái niệm cấu trúc dữ liệu
• Độ phức tạp thuật toán
• tiếp cận lập trình
• thuật toán
• thuật toán trong cấu trúc dữ liệu
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp