הדפס מבט ימני של עץ בינארי  


רמת קושי קַל
נשאל לעתים קרובות נאמן Adobe אמזון בעברית MakeMyTrip Snapdeal
עץ בינארי עֵץ מעבר עץ

הצהרת בעיה  

הבעיה "הדפס תצוגה ימנית של עץ בינארי" קובעת שאתה מקבל עץ בינארי. עכשיו אתה צריך למצוא את התצוגה הנכונה של העץ הזה. כאן, תצוגה נכונה של העץ הבינארי פירושה להדפיס את הרצף כפי שהעץ נראה במבט מכיוון הנכון.

דוגמה  

הדפס מבט ימני של עץ בינאריאורן

2 7 4 6

הסבר

אם אתה מתבונן בעץ הבינארי בכיוון הנכון. אנו יכולים לראות רק את הצמתים המודפסים בפלט. מכיוון שצמתים 3 ו -5 מסתתרים מאחורי 7 ו -4 בהתאמה.

גישה להדפסת תצוגה ימנית של עץ בינארי  

בבעיה זו עלינו למצוא את התצוגה הנכונה של ה- עץ בינארי. ניתן לפתור את הבעיה בשתי גישות. אחד מהם משתמש בתור והשני משתמש ברקורסיה. ראשית, נדון בגישה באמצעות התור. לכן, כדי לפתור את הבעיה באמצעות תור. אנו מתחילים משורש העץ הבינארי. בכל מפלס העץ אנו ממשיכים לשמור את הצמתים בתור. לצורך אחסון הצמתים של הרמה הבאה, עלינו לעבור על צמתי הרמה הנוכחית. אז כשאנחנו חוצים את צמתי הרמה הנוכחית. אנו מדפיסים את הצומת האחרון ברמה זו. כאשר אנו צופים בעץ מצד ימין. הצומת היחיד שנראה לעינינו הוא הצומת הימני ביותר ברמה. גישה זו משתמשת בתור שלוקח מקום.

ראה גם
ההבדל המרבי בין תדר של שני אלמנטים כך שאלמנט בעל תדירות גדולה יותר הוא גם גדול יותר

בואו נדון בפתרון באמצעות רקורסיה. הפיתרון דומה מאוד לזה של מציאת המבט השמאלי של העץ. בגישה זו. אנחנו פשוט עושים מעבר של העץ שמנוגד לחציית סדר. אך אנו עוקבים אחר הרמה בה אנו נמצאים כרגע והרמה המקסימלית שהושגה עד כה. כשאנחנו עוברים לעץ המשנה הימני לפני העץ השמאלי. בכל פעם שאנחנו נכנסים לרמה החדשה בעץ. אנו פוגשים לראשונה את הצומת הימני ביותר. אז אנחנו תמיד שומרים לבדוק אם הרמה הנוכחית גדולה מהרמה המקסימלית, אנו מדפיסים את הצומת. הגישה טובה יותר אם לא ניקח בחשבון את השטח הנדרש לערמת המהדר. מורכבות החלל לבעיה תלויה בגובה העץ אם ניקח בחשבון את החלל שנלקח על ידי ערימת המהדר.

קופונים  

קוד C ++ להדפסת מבט ימני של עץ בינארי

#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 printRightView(node* root, int level, int &max_level){
    if(root){
        if(level > max_level){
            max_level = level;
            cout << root->data <<" ";
        }
        printRightView(root->right, level+1, max_level);
        printRightView(root->left, level+1, max_level);
    }
}

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);

  int max_level = 0;
  printRightView(root, 1, max_level);
}
2 7 4 6

קוד ג'אווה להדפסת תצוגה ימנית של עץ בינארי

import java.util.*;

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

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

  static int max_level;
  static void printRightView(node root, int level){
      if(root != null){
          if(level > max_level){
              max_level = level;
              System.out.print(root.data+" ");
          }
          printRightView(root.right, level+1);
          printRightView(root.left, level+1);
      }
  }

  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);
    
    max_level = 0;
    printRightView(root, 1);
  }
}
2 7 4 6

ניתוח מורכבות  

מורכבות זמן

O (N) אנחנו פשוט עוברים מעל הצמתים בעץ. אז אם יש צמתים N בעץ, האלגוריתם דורש לבצע פעולות O (N).

ראה גם
כתוב קוד כדי לקבוע אם שני עצים זהים

מורכבות בחלל

O (1). אם לא מתחשבים במרחב המשמש את ערימת המהדר, אחרת O (H) נדרש מקום.