이 문제에서 우리는 이진 트리. 주어진 Inorder 및 Preorder 순회에서 이진 트리를 구성해야합니다.
차례
예
Input: Inorder= [D, B, E, A, F, C] Preorder= [A, B, D, E, C, F] Output: Pre-order traversal of the tree formed by the given preorder and inorder A B D E C F In-order traversal of the tree formed by the given preorder and inorder D B E A F C Post-order traversal of the tree formed by the given preorder and inorder D E B F C A
선주문 순회
사전 주문 순회에서는 먼저 루트 노드를 인쇄합니다. 그런 다음 존재하는 경우 왼쪽 하위 트리를 횡단합니다. 그리고 마지막으로 오른쪽 하위 트리가있는 경우 횡단합니다.
( 순회 모든 노드에 대해 동일한 방식으로 수행됨)
순서 순회
Inorder traversal에서는 노드의 왼쪽 하위 트리가있는 경우 먼저 탐색합니다. 그런 다음 루트 노드를 인쇄하십시오. 마지막으로, 존재한다면 오른쪽 하위 트리를 통과하십시오.
(순회는 모든 노드에 대해 동일한 방식으로 수행됩니다)
- 따라서 사전 주문 순회가있는 경우 항상 0th 인덱스 요소는 트리의 루트 노드를 나타냅니다.
- 그리고 우리가 inorder traversal을 가지고 있다면 모든 i 번째 인덱스에 대해 왼쪽에있는 모든 요소는 왼쪽 하위 트리에 있고 오른쪽에있는 모든 요소는 오른쪽 하위 트리에 있습니다.
위의 두 속성을 사용하여 주어진 순회로 트리를 구성 할 수 있습니다.
이진 트리 생성을위한 알고리즘
- 사전 주문 순회에서 다음 요소를 선택합니다 (인덱스 0으로 선택 시작).
- 선택한 요소로 데이터를 사용하여 새 노드를 만듭니다.
- hashMaps를 사용하여 Inorder traversal에서 선택한 요소의 인덱스를 찾아 인덱스를 찾는 데 걸리는 시간을 줄입니다.
- 선택한 요소의 왼쪽에있는 요소에 대해 동일한 함수를 재귀 적으로 호출하고 선택한 노드의 왼쪽에 할당합니다.
- 선택한 요소의 오른쪽에있는 요소에 대해 동일한 함수를 재귀 적으로 호출하고 선택한 노드의 오른쪽에 할당합니다.
- 루트 노드를 반환합니다.
예를 들어 이해합시다
순서 = [D, B, E, A, F, C]
선주문 = [A, B, D, E, C, F]
1: 선택한 요소는 A입니다.
2: 선택한 요소는 B입니다.
3: 선택한 요소는 D입니다.
4: 선택한 요소는 E입니다.
5: 선택한 요소는 C입니다.
6: 선택한 요소는 F입니다.
실시
이진 트리 생성을위한 C ++ 프로그램
#include<bits/stdc++.h>
using namespace std;
struct node{
char data;
node* left;
node* right;
//constructor
node(char data){
this->data = data;
left = right = NULL;
}
};
//Function to print pre-order of binary tree
void preorder(node* root){
if(root!=NULL){
cout<<root->data<<" ";
preorder(root->left);
preorder(root->right);
}
}
//Function to print in-order of binary tree
void inorder(node* root){
if(root!=NULL){
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
}
//Function to print post-order of binary tree
void postorder(node* root){
if(root!=NULL){
postorder(root->left);
postorder(root->right);
cout<<root->data<<" ";
}
}
//Function to construct binary tree from it's preorder and inorder traversal
node* buildTree(char in[], char pre[], int start, int end, unordered_map<char, int>& m, int& index){
//base case
if(start>end){
return NULL;
}
char current = pre[index++];
node* p = new node(current);
int inFind = m[current];
p->left = buildTree(in, pre, start, inFind-1, m, index);
p->right = buildTree(in, pre, inFind+1, end, m, index);
return p;
}
int main(){
int n;
cin>>n;
char in[n],pre[n];
for(int i=0;i<n;i++){
cin>>in[i];
}
for(int i=0;i<n;i++){
cin>>pre[i];
}
//make hashmap to find the node in inorder
unordered_map<char,int> m;
for(int i=0;i<n;i++){
m[in[i]] = i;
}
int start = 0,end = n-1, index = 0;
node* root = buildTree(in, pre, start, end, m, index);
cout<<"Pre-order traversal of the tree formed by the given preorder and inorder ";
preorder(root);
cout<<endl;
cout<<"In-order traversal of the tree formed by the given preorder and inorder ";
inorder(root);
cout<<endl;
cout<<"Post-order traversal of the tree formed by the given preorder and inorder ";
postorder(root);
cout<<endl;
}
6 D B E A F C A B D E C F
Pre-order traversal of the tree formed by the given preorder and inorder A B D E C F In-order traversal of the tree formed by the given preorder and inorder D B E A F C Post-order traversal of the tree formed by the given preorder and inorder D E B F C A
이진 트리 생성을위한 JAVA 프로그램
import java.util.*;
public class Main {
public static class node {
char data;
node left;
node right;
//constructor
node(char x) { data = x; }
};
static int index=0;
//Function to construct binary tree from it's preorder and inorder traversal
public static node buildTree(char in[], char pre[], int start, int end, Map<Character, Integer> m)
{
//base case
if(start>end){
return null;
}
char current = pre[index++];
node p = new node(current);
//leaf node
if(start == end){
return p;
}
int inFind = m.get(current);
p.left = buildTree(in, pre, start, inFind-1, m);
p.right = buildTree(in, pre, inFind+1, end, m);
return p;
}
//Function to print pre-order of binary tree
public static void preorder(node root){
if(root!=null){
System.out.print(root.data+" ");
preorder(root.left);
preorder(root.right);
}
}
//Function to print in-order of binary tree
public static void inorder(node root){
if(root!=null){
inorder(root.left);
System.out.print(root.data+" ");
inorder(root.right);
}
}
//Function to print post-order of binary tree
public static void postorder(node root){
if(root!=null){
postorder(root.left);
postorder(root.right);
System.out.print(root.data+" ");
}
}
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
char[] in = new char[n],pre = new char[n];
for(int i=0;i<n;i++){
in[i] = sc.next().charAt(0);
}
for(int i=0;i<n;i++){
pre[i] = sc.next().charAt(0);
}
//make hashmap to find the node in inorder
Map<Character, Integer> m=new HashMap<Character, Integer>();
for(int i=0;i<n;i++){
m.put(in[i], i);
}
int start = 0,end = n-1;
node root = buildTree(in, pre, start, end, m);
System.out.print("Pre-order traversal of the tree formed by the given preorder and inorder ");
preorder(root);
System.out.print("\n");
System.out.print("In-order traversal of the tree formed by the given preorder and inorder ");
inorder(root);
System.out.print("\n");
System.out.print("Post-order traversal of the tree formed by the given preorder and inorder ");
postorder(root);
System.out.print("\n");
}
}
8 D B E A F C G H A B D E C F H G
Pre-order traversal of the tree formed by the given preorder and inorder A B D E C F H G In-order traversal of the tree formed by the given preorder and inorder D B E A F C G H Post-order traversal of the tree formed by the given preorder and inorder D E B F G H C A
복잡성 분석
시간 복잡성
주어진 선주문 배열을 한 번만 순회하므로 시간이 복잡해집니다. O (N).
inorder 배열에서 노드의 인덱스를 검색하는 것은 해싱으로 인해 O (1) 시간이 걸립니다.
공간 복잡성
해시 맵 (크기 n)의 추가 공간을 사용하므로 공간 복잡성도 O (N).
