이진 트리의 중위 순회를 포함하는 배열 arr[]이 제공됩니다. 목표는 해당 배열에서 특수 이진 트리를 구성하는 것입니다. 특수 이진 트리는 루트 노드의 가중치가 왼쪽 및 오른쪽 자식의 가중치보다 큰 것입니다.
예를 들어
입력
int arr[] = {10, 20, 28, 40, 32, 31, 30} 출력
주어진 inordertraversal로 생성될 특별한 이진 트리는 다음과 같습니다 -
설명
we are given with an array of integer values or the inorder traversal of a tree. So, the special tree formed is 10, 20, 28, 40, 32, 31, 30
입력
int arr[] = {10, 20, 25, 28, 40, 32, 31, 30, 35} 출력
The special binary tree which will be constructed with the given inorder traversal is given below −
설명
we are given with an array of integer values or the inorder traversal of a tree. So, the special tree formed is 10, 20, 25, 28, 40, 32, 31, 30, 35.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다. -
이 접근 방식에서는 최대 요소를 루트 노드로 사용하여 주어진 배열에서 특수 이진 트리를 구성합니다. 왼쪽 요소는 왼쪽 하위 트리의 일부가 되고 오른쪽 요소는 오른쪽 하위 트리의 일부가 됩니다. 이 프로세스는 트리를 구성하기 위해 재귀적으로 수행됩니다.
-
inorder traversal을 포함하는 입력 배열로 arr[]을 사용합니다.
-
함수 new_node(int 데이터)는 왼쪽 및 오른쪽 자식이 NULL인 노드를 생성합니다.
-
total(int arr[], int first, int last) 함수는 해당 요소의 인덱스를 반환합니다.
-
가장 높은 =arr[첫 번째] 및 가장 낮은 =첫 번째를 취합니다.
-
첫 번째 + 1 인덱스에서 마지막 인덱스까지 순회하고 요소 arr[i]가 가장 높은 것보다 많이 발견되면 해당 인덱스를 가장 낮은 위치에 저장하고 가장 높은 값을 업데이트합니다.
-
for 루프의 끝에서 가장 낮은 요소는 가장 높은 요소의 인덱스를 포함합니다.
-
함수 create_tree(int arr[], int first, int last)는 arr[]에서 재귀적으로 특수 이진 트리를 생성합니다.
-
first>last이면 트리가 불가능하므로 NULL을 반환합니다.
-
temp =total(arr, first, last)를 사용하여 배열의 최대값으로 temp를 취합니다.
-
temp를 데이터로 사용하여 노드를 만들고 포인터 부모가 트리의 루트 노드에 대한 포인터를 가리키도록 합니다.
-
first==last이면 트리에는 노드가 하나만 있습니다. 부모를 반환합니다.
-
재귀적으로 parent->left =create_tree(arr, first, temp − 1);
를 재귀적으로 계산합니다. -
그리고 parent->right =create_tree(arr, temp + 1, last).
-
마지막에 부모를 반환합니다.
-
Inorder_traversal(tree_node* node) 함수는 위에서 생성된 트리의 중위 순회를 출력합니다.
-
노드가 NULL이면 아무 것도 반환하지 않습니다. 그렇지 않으면 Inorder_traversal(node−>left)을 사용하여 왼쪽 하위 트리를 먼저 인쇄합니다.
-
그런 다음 현재 노드를 인쇄합니다.
-
그런 다음 Inorder_traversal(node->right)을 사용하여 오른쪽 하위 트리를 인쇄합니다.
예시
#include <bits/stdc++.h>
using namespace std;
int total(int arr[], int first, int last);
class tree_node{
public:
int data;
tree_node* left;
tree_node* right;
};
tree_node* new_node(int data);
tree_node* create_tree (int arr[], int first, int last){
if(first > last){
return NULL;
}
int temp = total(arr, first, last);
tree_node *parent = new_node(arr[temp]);
if(first == last){
return parent;
}
parent−>left = create_tree(arr, first, temp − 1);
parent−>right = create_tree(arr, temp + 1, last);
return parent;
}
int total(int arr[], int first, int last){
int highest = arr[first];
int lowest = first;
for(int i = first + 1; i <= last; i++){
if(arr[i] > highest){
highest = arr[i];
lowest = i;
}
}
return lowest;
}
tree_node* new_node (int data){
tree_node* newNode = new tree_node();
newNode−>data = data;
newNode−>left = NULL;
newNode−>right = NULL;
return newNode;
}
void Inorder_traversal(tree_node* node){
if (node == NULL){
return;
}
Inorder_traversal(node−>left);
cout<<node−>data<<" ";
Inorder_traversal (node−>right);
}
int main(){
int arr[] = {10, 20, 28, 40, 32, 31, 30};
int size = sizeof(arr)/sizeof(arr[0]);
tree_node *root = create_tree(arr, 0, size − 1);
cout<<"Construct Special Binary Tree from given Inorder traversal are: "<<"\n";
Inorder_traversal(root);
return 0;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Construct Special Binary Tree from given Inorder traversal are: 10, 20, 28, 40, 32, 31, 30