ከተሰጠው Inorder እና Preorder Traversals የሁለትዮሽ ዛፍ ይገንቡ


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን ፓም ብሉምበርግ ByteDance ግልብጥብጥ ፌስቡክ google የ Microsoft በ Oracle
ሁለትዮሽ ዛፍ ጥልቀት የመጀመሪያ ፍለጋ ዛፍ

በዚህ ችግር ውስጥ እኛ የ “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

መተላለፍን ቀድመው ያዙ

በቅደም ተከተል መተላለፍ ውስጥ በመጀመሪያ የስር መስቀለኛ መንገድን እናተም ፡፡ ከዚያ ካለ ተጓዙ ግራ ንዑስ ነው። እና በመጨረሻም ፣ ካለ በትክክል ትክክል ነው።

(The መተላለፍ ለሁሉም አንጓዎች በተመሳሳይ መንገድ ይከናወናል)

Inorder መተላለፍ

በ Inorder transversal ውስጥ በመጀመሪያ ካለ የመስቀለኛውን የግራ ንዑስ ክፍል እናቋርጣለን። ከዚያ የስር መስቀለኛ ክፍልን ያትሙ። እና በመጨረሻም ፣ ካለ በትክክል ትክክል ነው።

(ተሻጋሪው ለሁሉም አንጓዎች በተመሳሳይ መንገድ ይከናወናል)

  1. ስለሆነም የቅድመ-ትዕዛዝ መተላለፍ ካለብን ሁልጊዜ 0 ማለት እንችላለንth መረጃ ጠቋሚ ንጥረ ነገር የዛፉን ሥር መስቀለኛ መንገድን ይወክላል።
  2. እና ለእያንዳንዱ የ ‹ኢንች› መረጃ ጠቋሚ (ኢንአደርስ) ማቋረጥ ካለብን በግራ በኩል ያለው ሁሉም ንጥረ ነገሮች በግራው ንዑስ ክፍል ውስጥ ይገኛሉ እና በቀኝ በኩል ያሉት ሁሉም ንጥረ ነገሮች በቀኝ ንዑስ ክፍል ውስጥ ይሆናሉ ፡፡

ከላይ የተጠቀሱትን ሁለት ባህሪዎች በመጠቀም በተሰጠን ተጓalsች አንድ ዛፍ መገንባት እንችላለን ፡፡

የሁለትዮሽ ዛፍ ግንባታ አልጎሪዝም

  1. ቀጣዩን ንጥረ-ነገር በቅደም ተከተል ማዘዋወሪያ ውስጥ ይምረጡ (በመረጃ ጠቋሚ 0 መምረጥ ይጀምሩ)።
  2. እንደተመረጠው አካል ከመረጃው ጋር አዲስ መስቀለኛ መንገድ ይፍጠሩ።
  3. መረጃ ጠቋሚውን ለማግኘት የጊዜ ውስብስብነትን ለመቀነስ hashMaps ን በመጠቀም የተመረጠውን ንጥረ-ነገር መረጃ ጠቋሚ ከ Inorder ተጓዥ ያግኙ ፡፡
  4. በተመረጠው አካል ግራ ውስጥ ላሉት ንጥረ ነገሮች ተመሳሳይ ተግባርን ደጋግመው ይደውሉ እና ከተመረጠው መስቀለኛ ክፍል በስተግራ ይመድቡት።
  5. በተመረጠው ንጥረ ነገር በቀኝ ውስጥ ላሉት አካላት ተመሳሳይ ተግባርን ደጋግመው ይደውሉ እና ከተመረጠው መስቀለኛ ክፍል በስተቀኝ ይመድቡት።
  6. የስር መስቀለኛ መንገድን ይመልሱ ፡፡

እስቲ በምሳሌ እንረዳው

Inorder = [ዲ ፣ ቢ ፣ ኢ ፣ ኤ ፣ ኤፍ ፣ ሲ]

ቅድመ-ትዕዛዝ = [A, B, D, E, C, F]

1: የተመረጠው ንጥረ ነገር ኤ ነው

ከተሰጠው Inorder እና Preorder Traversals የሁለትዮሽ ዛፍ ይገንቡ

2: የተመረጠው አካል ቢ ነው

ከተሰጠው Inorder እና Preorder Traversals የሁለትዮሽ ዛፍ ይገንቡ

3: የተመረጠው ንጥረ ነገር ዲ ነው

ከተሰጠው Inorder እና Preorder Traversals የሁለትዮሽ ዛፍ ይገንቡ

4: የተመረጠው አካል ኢ ነው

ከተሰጠው Inorder እና Preorder Traversals የሁለትዮሽ ዛፍ ይገንቡ

5: የተመረጠው ንጥረ ነገር ሲ ነው

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

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

የተሰጠንን የቅድመ-ቅደም ተከተል ድርድር አንድ ጊዜ ብቻ እናልፋለን ፣ ስለሆነም ጊዜ ውስብስብ ይሆናል ሆይ (n).

በ inorder ድርድር ውስጥ የመስቀለኛ ክፍልን ማውጫ መፈለግ በሃሺንግ ምክንያት ኦ (1) ጊዜ ይወስዳል ፡፡

የቦታ ውስብስብነት

ተጨማሪ የሃሽማፕ ቦታ (መጠን n) እየተጠቀምን ስለሆነ ፣ ስለዚህ የቦታ ውስብስብነት እንዲሁ ይሆናል ሆይ (n).

ማጣቀሻዎች