Trong bài toán này, chúng ta được cho một cây nhị phân và một nút. Nhiệm vụ là in ra nút kế tiếp (successor) của nút đó theo thứ tự duyệt hậu tố (postorder).
Cây nhị phân là loại cây đặc biệt mà mỗi nút có tối đa 2 nút con.
Duyệt hậu tố (Postorder Traversal) là kỹ thuật duyệt cây, trong đó duyệt trước cây con trái, sau đó cây con phải, và cuối cùng mới duyệt nút gốc.
Thứ tự hậu tố của cây trên: 8 4 2 7 9 6
Hãy xem ví dụ sau để hiểu rõ bài toán:
Đầu vào – cây nhị phân như ví dụ, nút = 7
Đầu ra – 9
Giải thích – Ta có thể thấy trong thứ tự hậu tố của cây nhị phân.
Để giải bài toán này, một giải pháp đơn giản là tìm toàn bộ thứ tự hậu tố rồi in phần tử tiếp theo. Nhưng ta cần một giải pháp hiệu quả hơn.
Giải pháp hiệu quả dựa trên các quan sát chung về duyệt hậu tố:
Vì nút gốc là nút cuối cùng trong duyệt hậu tố, nên nó không có nút kế tiếp (NULL).
Nếu nút hiện tại là con phải, thì nút cha là nút kế tiếp.
Nếu nút hiện tại là con trái, thì:
Nếu không có anh em ruột phải, nút kế tiếp là nút cha.
Nếu có anh em ruột phải, thì nút kế tiếp là nút đó hoặc nút con trái nhất của nó.
Phương pháp này hiệu quả với độ phức tạp thời gian O(h), trong đó h là chiều cao của cây.
Ví dụ minh họa
Chương trình triển khai giải pháp:
#include <iostream> using namespace std; struct Node { struct Node *left, *right, *parent; int value; }; struct Node* insertNode(int value) { Node* temp = new Node; temp->left = temp->right = temp->parent = NULL; temp->value = value; return temp; } Node* findPostorderSuccessor(Node* root, Node* n) { if (n == root) return NULL; Node* parent = n->parent; if (parent->right == NULL || parent->right == n) return parent; Node* curr = parent->right; while (curr->left != NULL) curr = curr->left; return curr; } int main(){ struct Node* root = insertNode(6); root->parent = NULL; root->left = insertNode(2); root->left->parent = root; root->left->left = insertNode(8); root->left->left->parent = root->left; root->left->right = insertNode(4); root->left->right->parent = root->left; root->right = insertNode(9); root->right->parent = root; root->right->left = insertNode(7); root->right->left->parent = root->right; root->left->right->left = insertNode(14); struct Node* successorNode = findPostorderSuccessor(root, root->left->right); if (successorNode) cout<<"Nút kế tiếp hậu tố của "<<root->left->right->value<<" là "<<successorNode->value; else cout<<"Nút kế tiếp hậu tố của "<<root->left->right->value<<" là NULL"; return 0; }Kết quả
Nút kế tiếp hậu tố của 4 là 2