Усули такрорӣ барои дарёфти гузаштагони дарахти дуӣ


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Adobe Amazon Фуркайтҳо Google InfoEdge Morgan Stanley Пардохт Samsung
тӯда Дарахт

Изҳороти мушкилот

“Усули такрорӣ барои ёфтани гузаштагони додашуда дарахти дуӣ”Дар мушкилот гуфта мешавад, ки ба шумо дарахти дуӣ ва адади бутуни ифодаи калид дода мешавад. Барои чоп кардани ҳамаи гузаштагони калиди додашуда бо ёрии такрор функсия созед.

Усули такрорӣ барои дарёфти гузаштагони дарахти дуӣ

мисол

вуруди 

Усули такрорӣ барои дарёфти гузаштагони дарахти дуӣ

калид = 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.

Дар ин ҷо барои ин мушкилот, ба мо дарахти дуӣ дода мешавад ва мо бояд гузаштагони гиреҳро чоп кунем. Чӣ тавре ки мо фарзандони гиреҳ дорем, мо ба ҷуз решаи дарахт гузаштагони онро дорем. Агар шумо баргҳои дарахтро ба назар гиред, онҳо фарзанддор намешаванд. Ба ин монанд, гиреҳи реша аҷдод надорад. Дар ин ҷо мо волидайни ҳар як гиреҳро нигоҳ медорем. То ки вақте ба мо ниёгони онро чоп кардан лозим ояд. Мо волидонро барои ёфтани гузаштагони худ истифода хоҳем кард. Мо як unordered_map / HashSet барои иҷрои ин амалиёт. Азбаски HashSet ба O (1) дохил кардан / ҷустуҷӯ кардан / нест карданро иҷозат медиҳад. Мо метавонем ин масъаларо дар мураккабии хаттии вақт ҳал кунем. Дар ҳалли дар поён овардашуда, мо графикаи ҷустуҷӯро ба мисли равиш истифода мебарем бӯриш тамоми дарахт. Ва ҳангоми ҳаракат мо волидайни ҳар як гиреҳро нигоҳ медорем. Сипас, мо як функсияро эҷод кардем, дар ҳоле ки дар болои харитаи худ (ки волидонро нигоҳ медорад) гузаред, то гузаштагонро чоп кунед. тамоми ҳалли мураккабии вақти хатӣ иҷро мешавад О (Н).

рамз

Барномаи C ++ барои усули такрорӣ барои дарёфти гузаштагони дарахти дуӣ

#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

Барномаи Java барои усули такрорӣ барои пайдо кардани гузаштагони дарахти дуӣ

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

Таҳлили мураккабӣ

Мураккабии вақт

О (Н), ки дар он N шумораи гиреҳҳо дар дарахти додашуда мебошад. Мо навакак тамоми дарахтро тай кардем ва як бор харитаро тай намуда, гузаштагонро чоп кардем.

Мураккабии фазо

О (Н) зеро мо фазои иловагиро дар unordered_map ва stack истифода кардем.