이 문제에서는 이진 트리와 노드가 제공됩니다. 우리의 임무는 이진 트리에서 노드의 후위 순서를 인쇄하는 것입니다.
바이너리 나무 각 노드가 최대 2개의 자식 노드를 가질 수 있는 특수한 유형의 트리입니다.
포스터 순회 첫 번째 왼쪽 하위 트리가 오른쪽 하위 트리보다 탐색되고 루트가 끝에서 탐색되는 트리 탐색 기술입니다.
위 트리의 후위 순회:8 4 2 7 9 6
문제를 이해하기 위해 예를 들어보겠습니다.
입력 - 위의 예에서 이진 트리, 노드=7
출력 − 9
설명 − 이진 트리의 후위 순회에서 볼 수 있습니다.
이 문제를 해결하기 위해 간단하고 쉬운 멍청한 해결책은 단순히 후위 순회를 찾은 다음 순회에서 그 옆에 있는 숫자를 인쇄하는 것입니다.
하지만 더 효과적인 솔루션을 배워야 합니다.
효과적인 솔루션은 후위 순회에 대한 몇 가지 일반적인 관찰을 사용하는 것입니다.
-
루트는 후위 순회에서 마지막 노드이므로 후속 노드는 NULL입니다.
-
현재 노드가 오른쪽 자식인 경우 부모 노드가 후속 노드입니다.
-
현재 노드가 자식으로 남아 있는 경우
-
오른쪽 형제가 없으면 후임자가 부모 노드입니다.
-
오른쪽 형제가 존재하는 경우 노드 또는 가장 왼쪽에 있는 자식이 후임자입니다.
-
이 방법이 효과적이며 시간 복잡도는 O(h), 그의 트리 높이입니다.
예시
솔루션 구현을 보여주는 프로그램,
#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<<"Postorder successor of "<<root->left->right->value<<" is "<<successorNode->value;
else
cout<<"Postorder successor of "<<root->left->right->value<<" is NULL";
return 0;
} 출력
Postorder successor of 4 is 2