Duyệt hậu tố cây nhị phân không dùng đệ quy và không dùng stack trong C++

Trong bài toán này, chúng ta được cho một cây nhị phân. Nhiệm vụ là in ra thứ tự duyệt hậu tố của cây nhị phân không sử dụng đệ quy và không sử dụng stack.

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

Để duyệt cây không dùng đệ quy và stack, ta sử dụng kỹ thuật dựa trên tìm kiếm theo chiều sâu (DFS) và lưu trữ dữ liệu trong bảng băm (hash table).

Ví dụ minh họa

Chương trình triển khai giải pháp:

#include <bits/stdc++.h> using namespace std; struct Node {    int data;    struct Node *left, *right; }; void postOrderTraversal(struct Node* head) {    struct Node* temp = head;    unordered_set<Node*> visited;    while (temp && visited.find(temp) == visited.end()) {       if (temp->left &&          visited.find(temp->left) == visited.end())          temp = temp->left;       else if (temp->right &&          visited.find(temp->right) == visited.end())          temp = temp->right;       else {          cout<<temp->data<<"\t";          visited.insert(temp);          temp = head;       }    } } struct Node* insertNode(int data){    struct Node* node = new Node;    node->data = data;    node->left = NULL;    node->right = NULL;    return (node); } int main(){    struct Node* root = insertNode(6);    root->left = insertNode(2);    root->right = insertNode(9);    root->left->left = insertNode(8);    root->left->right = insertNode(4);    root->right->left = insertNode(7);    root->right->left->left = insertNode(13);    cout<<"Duyệt hậu tố của cây nhị phân :\n";    postOrderTraversal(root);    return 0; }

Kết quả

Duyệt hậu tố của cây nhị phân : 8   4   2   13   7   9   6

Giải pháp trên có thể cải tiến bằng cách loại bỏ bảng băm. Vì bảng băm chỉ lưu các nút đã thăm, ta có thể thêm cờ visited trực tiếp vào từng nút của cây để giảm tải hệ thống, làm cho thuật toán tốt hơn.

Một giải pháp hiệu quả hơn là sử dụng unordered_map, giúp giảm chi phí truy vết ngược về nút gốc.

Ví dụ giải pháp cải tiến

Chương trình triển khai:

#include <bits/stdc++.h> using namespace std; struct Node {    int data;    struct Node *left, *right;    bool visited; }; void postOrderTraversal(Node* root) {    Node* n = root;    unordered_map<Node*, Node*> postorder;    postorder.insert(pair<Node*, Node*>(root, nullptr));    while (n) {       if (n->left && postorder.find(n->left) == postorder.end()) {          postorder.insert(pair<Node*, Node*>(n->left, n));          n = n->left;       }       else if (n->right && postorder.find(n->right) == postorder.end()) {          postorder.insert(pair<Node*, Node*>(n->right, n));          n = n->right;       }       else {          cout<<n->data<<"\t";          n = (postorder.find(n))->second;       }    } } struct Node* insertNode(int data) {    struct Node* node = new Node;    node->data = data;    node->left = NULL;    node->right = NULL;    node->visited = false;    return (node); } int main() {    struct Node* root = insertNode(6);    root->left = insertNode(2);    root->right = insertNode(9);    root->left->left = insertNode(8);    root->left->right = insertNode(4);    root->right->left = insertNode(7);    root->right->left->left = insertNode(13);    cout<<"Duyệt hậu tố của cây nhị phân :\n";    postOrderTraversal(root);    return 0; }

Kết quả

Duyệt hậu tố của cây nhị phân : 8   4   2   13   7   9   6