Дијагонално прелажење бинарног стабла  


Ниво тешкоће Средњи
Често питани у амазонка Фацтсет Фанатици Фоуркитес пророчанство ПаиУ Куора
Бинарно дрво Дрво Прелазак дрвета

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

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

Пример  

Дијагонално прелажење бинарног стаблаПин

2 7
3 4
5 6

Објашњење

Прва дијагонала има тамо чворове 2, 7. Тада друга дијагонала има 3, 4, слично као и трећа дијагонала 5, 6. Тако се излаз исписао на такав начин да елементи из исте дијагонале имају исти ред.

Приступ  

Дијагонално прелажење бинарног стаблаПин

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

Извршићемо унутрашње заокретање бинарног стабла. Док то радимо, пратићемо растојање у дијагоналном смеру. Кад год се крећемо у левом смеру, дијагоналној удаљености додамо 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;
}

void diagonalView(node* root, int dis, map<int, vector<int>> &m){
    if(root){
        m[dis].push_back(root->data);
        // move in the left direction with dis+1 distance
        diagonalView(root->left, dis+1, m);
        // move in the right direction with dis distance
        diagonalView(root->right, dis, m);
    }
}

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, vector<int>> m;
    diagonalView(root, 0, m);
    for(auto x: m){
        for(auto nodes: x.second)
            cout<<nodes<<" ";
        cout<<endl;
    }
}
2 7
3 4
5 6

Јава код за испис Дијагоналног преласка бинарног стабла  

import java.util.*;

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

class Main{

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

  static void diagonalView(node root, int dis, Map<Integer, Vector<Integer>> m){
      if(root != null){
      	Vector<Integer> v = m.get(dis);
      	if(v == null){
      		v = new Vector<Integer>();
      		v.add(root.data);
      	}
      	else
      		v.add(root.data);
          m.put(dis, v);
          // move in the left direction with dis+1 distance
          diagonalView(root.left, dis+1, m);
          // move in the right direction with dis distance
          diagonalView(root.right, dis, m);
      }
  }

  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, Vector<Integer>> m = new TreeMap<Integer, Vector<Integer>>();
      diagonalView(root, 0, m);
      for(Map.Entry<Integer, Vector<Integer>> entry : m.entrySet())
          System.out.println(entry.getValue());
  }
}
[2, 7]
[3, 4]
[5, 6]

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

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

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

Види такође
Пронађите чвор са минималном вредношћу у бинарном стаблу претраживања

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

НА), јер чувамо све чворове на мапи. Сложеност простора је линеарна.