Итеративни метод проналажења предака датог бинарног стабла


Ниво тешкоће Средњи
Често питани у адобе амазонка Фоуркитес гоогле ИнфоЕдге Морган Стенли Паитм самсунг
Стацк Дрво

Изјава о проблему

„Итеративни метод проналажења предака датог бинарно стабло”Проблем наводи да вам се даје бинарно стабло и цео број који представља кључ. Направите функцију за испис свих предака датог кључа помоћу итерације.

Итеративни метод проналажења предака датог бинарног стабла

Пример

Улазни 

Итеративни метод проналажења предака датог бинарног стабла

кључ = 6

5 2 1

Објашњење: Стаза од корена до чвора која има вредност 6 је 1 2 5 6. стога је родитељска секвенца од 6 до корена 5 2 1.

Улазни :

Итеративни метод проналажења предака датог бинарног стабла

кључ = 10

9 7 1

Алгоритам

1. Create a structure Node which contains an integer variable to hold data and two pointers left and right of type Node.
2. After that, create the parameterized constructor of the structure which accepts an integer value as it's parameter. Store the integer value in the data variable of Node and initialize left and right pointers as null.
3. Create a function to print the tree path which accepts an unordered map and an integer variable key as it's a parameter. While the key variable is equal to the map[key], print the key.
4. Similarly, create another function to set the parents for all the nodes in the given binary tree which accepts a pointer to the root node and an unordered map as it's parameter.
5. Create a stack data structure of Node* type. Push/insert the root in the stack.
6. After that, traverse while the size of the stack is not 0. Create a pointer curr of type Node and store the element at the top of the stack in it and pop/delete it from the stack.
7. If the right of the curr is present, update the map at index data of right of curr as the data of curr. Push/insert the right of curr in the stack.
8. If the left of the curr is present, update the map at index data of the left of curr as the data of curr. Push/insert the left of curr in the stack.
9. Similarly, create another function to print the ancestors. Check if the root is equal to null, return.
10. Create an unordered map and set the data of its root as 0.
11. Call the function to set the parents of all nodes.
12. Finally, call the function to print the tree path.

Овде за овај проблем добијамо бинарно стабло и морамо да одштампамо претке чвора. Баш као што имамо децу чвора, имамо и његовог претка, осим корена дрвета. Ако узмете у обзир лишће дрвета, они немају децу. Слично томе, коријенски чвор нема претка. Овде чувамо надређеног сваког чвора. Тако да када треба да одштампамо његове претке. Користићемо родитеље да пронађемо своје претке. Користили смо унордеред_мап / ХасхСет за извођење ове операције. Пошто ХасхСет дозвољава уметање / тражење / брисање у О (1). Овај проблем смо у стању да решимо у линеарној временској сложености. У доњем решењу користимо графикон који претражује попут приступа прелаз цело дрво. И док прелазимо, чувамо надређеног сваког чвора. Тада смо створили функцију, док прелазимо преко наше мапе (која чува родитеље) за штампање предака. цело решење се одвија у линеарној временској сложености од НА).

код

Ц ++ програм за итеративну методу за проналажење предака датог бинарног стабла

#include <bits/stdc++.h>
using namespace std;

struct Node{
    int data;
    Node *left, *right;

    Node(int data){
        this->data = data;
        this->left = this->right = nullptr;
  }
};

void printTopToBottomPath(unordered_map<int, int> parent, int key){
    while(key = parent[key]){
        cout << key << " ";
    }
    cout << endl;
}

void setParent(Node* root, unordered_map<int, int> &parent){
    
    stack<Node*> stack;
    stack.push(root);

    while(!stack.empty()){
        
        Node* curr = stack.top();
        stack.pop();

        if(curr->right){
           parent[curr->right->data] = curr->data;
           stack.push(curr->right);
        }

        if(curr->left){
           parent[curr->left->data] = curr->data;
           stack.push(curr->left);
        }
    }
}

void printAncestors(Node* root, int node){
    
    if(root == nullptr){
        return;
    }

    unordered_map<int, int> parent;

    parent[root->data] = 0;

    setParent(root, parent);

    printTopToBottomPath(parent, node);
}

int main(){
    Node* root = nullptr;

    root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(7);
    root->left->left = new Node(3);
    root->left->right = new Node(5);
    root->right->left = new Node(8);
    root->right->right = new Node(9);
    root->left->left->left = new Node(4);
    root->left->right->right = new Node(6);
    root->right->right->left = new Node(10);

    int key = 6;
    printAncestors(root, key);

    return 0;
}
5 2 1

Јава програм за итеративну методу за проналажење предака датог бинарног стабла

import java.util.*;

class Node{
  int data;
  Node left = null, right = null;

  Node(int data){
    this.data = data;
  }
}

class Main{
  
  public static void printTopToBottomPath(Map<Integer, Integer> parent, int key){
    while((key = parent.get(key)) != 0){
      System.out.print(key + " ");
    }
  }

  public static void setParent(Node root, Map<Integer, Integer> parent){
    
    Deque<Node> stack = new ArrayDeque<>();
    stack.add(root);

    while(!stack.isEmpty()){
      
      Node curr = stack.pollLast();

      if(curr.right != null){
        parent.put(curr.right.data, curr.data);
        stack.add(curr.right);
      }

      if(curr.left != null){
        parent.put(curr.left.data, curr.data);
        stack.add(curr.left);
      }
    }
  }

  public static void printAncestors(Node root, int node){
    
    if(root == null){
      return;
    }

    Map<Integer, Integer> parent = new HashMap<>();

    parent.put(root.data, 0);

    setParent(root, parent);

    printTopToBottomPath(parent, node);
  }

  public static void main(String[] args){
      
      Node root = new Node(1);
      root.left = new Node(2);
            root.right = new Node(7);
            root.left.left = new Node(3);
            root.left.right = new Node(5);
            root.right.left = new Node(8);
            root.right.right = new Node(9);
            root.left.left.left = new Node(4);
            root.left.right.right = new Node(6);
            root.right.right.left = new Node(10);

      int key = 6;
    
      printAncestors(root, key);
  }
}
5 2 1

Анализа сложености

Сложеност времена

НА), где је Н број чворова у датом стаблу. Управо смо прешли цело дрво и једном прешли смо мапу да бисмо одштампали претке.

Сложеност простора

НА) јер смо користили додатни простор у унордеред_мап и стацк.