트리 탐색은 그래프 탐색의 한 형태입니다. 여기에는 트리의 각 노드를 정확히 한 번 확인하거나 인쇄하는 작업이 포함됩니다. 이진 검색 트리의 선주문 순회는 트리의 각 노드를 순서대로(루트, 왼쪽, 오른쪽) 방문하는 것을 포함합니다.
이진 트리의 선주문 순회 예는 다음과 같습니다.
바이너리 트리는 다음과 같이 주어진다.
선주문 순회:5 3 2 4 8 9
선주문 비재귀 순회를 수행하는 프로그램은 다음과 같습니다.
예시
#include<iostream>
#include <stack>
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 preorder(struct node *root) {
if (root == NULL)
return;
stack<node *> nodeStack;
nodeStack.push(root);
while (nodeStack.empty() == false) {
struct node *temp_node = nodeStack.top();
cout<< temp_node->data <<" ";
nodeStack.pop();
if (temp_node→right)
nodeStack.push(temp_node->right);
if (temp_node→left)
nodeStack.push(temp_node->left);
}
}
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, 5);
insertNode(root, 8);
insertNode(root, 3);
insertNode(root, 2);
insertNode(root, 6);
insertNode(root, 9);
insertNode(root, 4);
cout<<"Pre-Order traversal of the Binary Search Tree is: ";
preorder(root);
} 출력
Pre-Order traversal of the Binary Search Tree is: 5 3 2 4 8 6 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;
} preorder() 함수는 스택을 사용하여 트리의 요소를 사전 순서로 인쇄합니다. 먼저 루트 노드가 스택에 삽입됩니다. 스택이 비어 있지 않을 때까지 실행되는 while 루프가 시작됩니다. 먼저 스택의 topnode 요소에 있는 데이터가 표시된 다음 노드가 팝됩니다. 그런 다음 위 노드의 오른쪽 및 왼쪽 노드가 스택에 푸시됩니다.
이 기능은 다음 코드 스니펫을 사용하여 보여줍니다.
void preorder(struct node *root) {
if (root == NULL)
return;
stack<node *> nodeStack;
nodeStack.push(root);
while (nodeStack.empty() == false) {
struct node *temp_node = nodeStack.top();
cout<< temp_node->data <<" ";
nodeStack.pop();
if (temp_node→right)
nodeStack.push(temp_node→right);
if (temp_node→left)
nodeStack.push(temp_node→left);
}
} 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, 5); insertNode(root, 8); insertNode(root, 3); insertNode(root, 2); insertNode(root, 6); insertNode(root, 9); insertNode(root, 4);
마지막으로 preorder() 함수는 트리의 루트 노드를 사용하여 호출되며 모든 트리 값이 사전 순서로 표시됩니다. 이것은 아래와 같습니다.
cout<<"Pre-Order traversal of the Binary Search Tree is: "; preorder(root);