پیمایش مورب درخت باینری


سطح دشواری متوسط
اغلب در آمازون واقعیت متعصبان فورکایت وحی PayU Quora
درخت باینری درخت عبور از درخت

بیان مسأله

مسئله "Diagonal Traversal of Binary Tree" بیان می کند که یک درخت باینری به شما داده می شود و اکنون باید نمای مورب درخت داده شده را پیدا کنید. وقتی درختی را از جهت بالا به راست می بینیم. گره هایی که برای ما قابل مشاهده هستند نمای مورب درخت باینری است.

مثال

پیمایش مورب درخت باینری

2 7
3 4
5 6

توضیح

اولین مورب دارای گره های 2 ، 7 در آنجا است. سپس مورب دوم دارای 3 ، 4 است ، به طور مشابه برای مورب سوم 5 ، 6. بنابراین خروجی به گونه ای چاپ شده است که عناصر از همان مورب در همان خط قرار دارند.

روش

پیمایش مورب درخت باینری

این مشکل از ما می خواهد گره هایی را که از جهت بالا به سمت راست برای ما قابل مشاهده هستند چاپ کنیم. بنابراین چگونه مشکل را حل کنیم؟

ما یک پیمایش غیر انتفاعی از درخت باینری انجام خواهیم داد. در حین انجام این کار ، ما فاصله را در یک جهت مورب پیگیری خواهیم کرد. هر زمان که در جهت چپ حرکت می کنیم ، 1 را به فاصله مورب اضافه می کنیم و اگر در جهت درست حرکت می کنیم ، هیچ مقداری به فاصله اضافه نمی کنیم. بنابراین ، در حین انجام این کار ، ما گره های بازدید شده در a را ردیابی خواهیم کرد نقشه. ما یک نقشه با فاصله مورب به عنوان کلید و یک بردار به عنوان مقدار ایجاد خواهیم کرد. زیرا گره ها را با فاصله مورب در یک بردار جمع خواهیم کرد. و همانطور که می توانستیم کل را مرور کنیم درخت. بعد از عبور ، ما گره ها را بر اساس فاصله مورب خود در بردارها نگه داشته ایم.

پس از تمام این محاسبات ، به راحتی عناصر موجود در نقشه را چاپ کنید در حالی که گره ها را از هر یک از بردارها جدا می کنید.

کد ++ C برای چاپ Diaversal Traversal of Binary Tree

#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

کد جاوا برای چاپ Diagonal Traversal of Binary Tree

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]

تحلیل پیچیدگی

پیچیدگی زمان

O (NlogN) ، زیرا ما درخت را رد کرده و مقادیر را به روز کرده ایم. از آنجا که ما از نقشه استفاده کرده ایم ، درج ، حذف و جستجو در زمان O (logN) انجام می شود.

پیچیدگی فضا

بر)، زیرا ما همه گره ها را در نقشه ذخیره می کنیم. پیچیدگی فضا خطی است.