Поглед одоздо на бинарно дрво  


Ниво тешкоће Лако
Често питани у Аццолите амазонка ЦоупонДуниа Флипкарт Паитм Валмарт Лабс
Бинарно дрво Дрво Прелазак дрвета

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

Проблем „Поглед одоздо на бинарно стабло“ наводи да вам је дато бинарно стабло и сада треба да пронађете приказ одоздо за дано дрво. Када видимо дрво из правца надоле. Чворови који су нам видљиви је доњи приказ бинарног стабла.

Пример  

Поглед одоздо на бинарно дрвоПин

5 6 4 7

Приступ  

Приступ је једноставан јер смо већ решили проблем сличан овом. Проблем Поглед одозго на бинарно стабло сличан је овом где смо морали да одштампамо чворове који су нам видљиви из горњег правца. Па како да решимо проблем?

Овде треба да користимо концепт хоризонталне удаљености. Кад год се крећемо у левом смеру чвора, одузимамо од хоризонталне удаљености тренутног чвора. Слично томе, ако се крећемо у правом смеру, додајемо 1 хоризонталној удаљености. Једном када се упознамо са овим концептом. Мапу ћемо користити за праћење чворова на свакој хоризонталној удаљености. Тада ћемо прећи дрво и кад год нађемо чвор ажурирамо нашу мапу. Држат ћемо хоризонталну удаљеност као кључ, а чвор као вриједност на мапи. Дакле, користећи обилазак реда нивоа, наставите да рачунате хоризонталну удаљеност и ажурирате Мапа.

Види такође
Направите целокупно бинарно стабло из његовог приказа повезане листе

После свих ових прорачуна, једноставно одштампајте елементе на мапи. Зато што је најлевији чвор са најнегативнијом хоризонталном удаљеностом, а крајњи десни чвор има највећу позитивну вредност.

Ц ++ код за испис дна бинарног стабла одоздо  

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

struct node{
    int data;
    node *left, *right;
};

node* create(int data){
    node* tmp = new node();
    tmp->data = data;
    tmp->left = tmp->right = NULL;
    return tmp;
}

int main(){
    node *root = create(2);
    root->left = create(3);
    root->right = create(7);
    root->left->left = create(5);
    root->left->right = create(4);
    root->left->right->left = create(6);

    map<int,int> m;
    queue<pair<int,node*>> q;
    q.push(make_pair(0, root));
    m[0] = root->data;
    while(!q.empty()){
        pair<int, node*> now = q.front();
        q.pop();

        m[now.first] = now.second->data;
        if(now.second->left)
        q.push(make_pair(now.first - 1, now.second->left));
        if(now.second->right)
        q.push(make_pair(now.first + 1, now.second->right));
    }
    for(auto x: m)
        cout<<x.second<<" ";
}
5 6 4 7

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

import java.util.*;

class node{
  int data;
  node left, right;
  int hd;
}

class Main{

  static node create(int data){
      node tmp = new node();
      tmp.data = data;
      tmp.left = tmp.right = null;
      tmp.hd = 0;
      return tmp;
  }

  public static void main(String[] args){
    node root = create(2);
      root.left = create(3);
      root.right = create(7);
      root.left.left = create(5);
      root.left.right = create(4);
      root.left.right.left = create(6);

      Map<Integer, Integer> m = new TreeMap<Integer, Integer>();
      Queue<node> q = new LinkedList<node>();
      q.add(root);
      m.put(root.hd, root.data);
      while(!q.isEmpty()){
          node now = q.remove();

          m.put(now.hd, now.data);
          if(now.left != null){
          	now.left.hd = now.hd - 1;
          	q.add(now.left);
          }
          if(now.right != null){
          	now.right.hd = now.hd + 1;
          	q.add(now.right);
          }
      }
      for(Map.Entry<Integer, Integer> entry : m.entrySet())
          System.out.print(entry.getValue()+" ");
  }
}
5 6 4 7

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

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

О (НлогН), јер смо прешли дрво и ажурирали вредности. Будући да смо користили мапу, уметање, брисање и претраживање се врши у О (логН) времену.

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

НА), највише може бити (Н + 1) / 2 на последњем нивоу. Стога је сложеност простора линеарна.