트리 탐색은 그래프 탐색의 한 형태입니다. 여기에는 트리의 각 노드를 정확히 한 번 확인하거나 인쇄하는 작업이 포함됩니다. 이진 탐색 트리의 후위 순회는 트리의 각 노드를 순서대로(왼쪽, 오른쪽, 루트) 방문하는 것을 포함합니다.
이진 트리의 후위 순회 예는 다음과 같습니다.
바이너리 트리는 다음과 같이 주어진다.
후위 순회:1 5 4 8 6
후위 재귀 순회를 수행하는 프로그램은 다음과 같습니다.
예시
#include<iostream>
using namespace std;
struct node {
int data;
struct node *left;
struct node *right;
};
struct node *createNode(int val) {
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->data = val;
temp->left = temp->right = NULL;
return temp;
}
void postorder(struct node *root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
cout<<root->data<<" ";
}
}
struct node* insertNode(struct node* node, int val) {
if (node == NULL) return createNode(val);
if (val < node->data)
node->left = insertNode(node->left, val);
else if (val > node->data)
node->right = insertNode(node->right, val);
return node;
}
int main() {
struct node *root = NULL;
root = insertNode(root, 4);
insertNode(root, 5);
insertNode(root, 2);
insertNode(root, 9);
insertNode(root, 1);
insertNode(root, 3);
cout<<"Post-Order traversal of the Binary Search Tree is: ";
postorder(root);
return 0;
} 출력
Post-Order traversal of the Binary Search Tree is: 1 3 2 9 5 4
위의 프로그램에서 구조 노드는 트리의 노드를 생성합니다. 이 구조는 구조체 노드 유형의 포인터를 포함하므로 자체 참조 구조입니다. 이 구조는 다음과 같습니다.
struct node {
int data;
struct node *left;
struct node *right;
}; createNode() 함수는 temp 노드를 생성하고 malloc을 사용하여 메모리를 할당합니다. 데이터 값 val은 temp의 데이터에 저장됩니다. NULL은 temp의 좌우 포인터에 저장됩니다. 다음 코드 스니펫에서 이를 확인할 수 있습니다.
struct node *createNode(int val) {
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->data = val;
temp->left = temp->right = NULL;
return temp;
} postorder() 함수는 이진 트리의 루트를 인수로 사용하고 트리의 요소를 사후 순서로 인쇄합니다. 재귀함수입니다. 다음 코드를 사용하여 시연됩니다.
void postorder(struct node *root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
cout<<root->data<<" ";
}
} insertNode() 함수는 이진 트리의 올바른 위치에 필요한 값을 삽입합니다. 노드가 NULL이면 createNode가 호출됩니다. 그렇지 않으면 노드의 올바른 위치가 트리에서 발견됩니다. 이는 다음 코드 스니펫에서 확인할 수 있습니다.
struct node* insertNode(struct node* node, int val) {
if (node == NULL) return createNode(val);
if (val < node->data)
node->left = insertNode(node->left, val);
else if (val > node->data)
node->right = insertNode(node->right, val);
return node;
} main() 함수에서 루트 노드는 먼저 NULL로 정의됩니다. 그런 다음 필요한 값을 가진 모든 노드가 이진 검색 트리에 삽입됩니다. 이것은 아래에 나와 있습니다.
struct node *root = NULL; root = insertNode(root, 4); insertNode(root, 5); insertNode(root, 2); insertNode(root, 9); insertNode(root, 1); insertNode(root, 3);
마지막으로, 함수 postorder()는 트리의 루트 노드를 사용하여 호출되고 모든 트리 값은 postorder로 표시됩니다. 이것은 아래와 같습니다.
cout<<"Post-Order traversal of the Binary Search Tree is: "; postorder(root);