이 문제에서는 이진 트리가 제공됩니다. 우리의 임무는 재귀와 스택을 사용하지 않고 이진 트리의 후위 순회를 인쇄하는 것입니다. .
이진 트리 각 노드가 최대 2개의 자식 노드를 가질 수 있는 특수한 유형의 트리입니다.
포스터 순회 첫 번째 왼쪽 하위 트리가 오른쪽 하위 트리보다 탐색되고 루트가 끝에서 탐색되는 트리 탐색 기술입니다.
위 트리의 후위 순회 − 8 4 2 7 9 6
재귀와 스택을 사용하지 않고 트리를 탐색합니다. 우리는 깊이 우선 검색 기반 기술을 사용할 것이며 데이터는 해시 테이블에 저장됩니다. .
예시
이 솔루션의 구현을 보여주는 프로그램,
#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<<"Post Order Traversal of the binary tree :\n";
postOrderTraversal(root);
return 0;
} 출력
Post Order Traversal of the binary tree : 8 4 2 13 7 9 6
동일한 솔루션을 업데이트할 수 있으며 해시 테이블의 사용을 제거할 수 있습니다. 그 작업은 방문한 노드를 저장하는 것입니다. 시스템 부하를 줄이기 위해 트리 자체의 모든 노드에 방문 플래그를 추가하여 알고리즘을 개선할 것입니다.
보다 효과적인 솔루션은 순서가 지정되지 않은 맵을 사용하는 것입니다. 이렇게 하면 헤드에 대한 트랙백의 오버헤드가 줄어듭니다.
예시
구현을 보여주는 프로그램
#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<<"Post Order Traversal of the binary tree :\n";
postOrderTraversal(root);
return 0;
} 출력
Post Order Traversal of the binary tree : 8 4 2 13 7 9 6