트리 탐색은 그래프 탐색의 한 형태입니다. 여기에는 트리의 각 노드를 정확히 한 번 확인하거나 인쇄하는 작업이 포함됩니다. 이진 탐색 트리의 inorder traversal은 트리의 각 노드를 순서대로(Left, Root, Right) 방문하는 것을 포함합니다.
이진 트리의 Inorder traversal의 예는 다음과 같습니다.
바이너리 트리는 다음과 같이 주어진다.
중위 순회:1 4 5 6 8
Inorder recursive traversal을 수행하는 프로그램은 다음과 같다.
예시
#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 inorder(struct node *root) {
if (root != NULL) {
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
}
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<<"In-Order traversal of the Binary Search Tree is: ";
inorder(root);
return 0;
} 출력
In-Order traversal of the Binary Search Tree is: 1 2 3 4 5 9
위의 프로그램에서 구조 노드는 트리의 노드를 생성합니다. 이 구조는 구조체 노드 유형의 포인터를 포함하므로 자체 참조 구조입니다. 이 구조는 다음과 같습니다.
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;
} inorder() 함수는 이진 트리의 루트를 인수로 취하고 트리의 요소를 순서대로 인쇄합니다. 재귀함수입니다. 다음 코드를 사용하여 시연됩니다.
void inorder(struct node *root) {
if (root != NULL) {
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
} 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);
마지막으로 트리의 루트 노드를 사용하여 inorder() 함수를 호출하고 모든 트리 값을 순서대로 표시합니다. 이것은 아래와 같습니다.
cout<<"In-Order traversal of the Binary Search Tree is: "; inorder(root);