מעבר גבולות של עץ בינארי


רמת קושי בינוני
נשאל לעתים קרובות נאמן אמזון בעברית טיול Kritikal Solutions מיקרוסופט מורגן סטנלי PayU Snapdeal
עץ בינארי עֵץ מעבר עץ

הצהרת בעיה

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

דוגמה

2 3 5 6 4 7

הסבר

כאן, כל הצמתים הם צמתים גבוליים. אבל עלינו להדפיס את הצמתים בכיוון נגד כיוון השעון. לפיכך אנו מתחילים מהשורש שהוא 2. לאחר מכן, אנו פשוט עוברים באותו אופן ומדפיסים את הצמתים 2, 3, 4, 6, 4, 7.

מעבר גבולות של עץ בינארי

5 7 9 1 4 3

גישה

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

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

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

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

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

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

// print the leaves (nodes from the bottom)
void printLeaves(node* root)
{
  if(root){
    // recursively solve the problem for the left subtree
    printLeaves(root->left);
    // if current node is a leaf
    if ((root->left) == NULL && (root->right) == NULL)
      cout<<root->data<<" ";
    // recursively solve the problem for right subtree
    printLeaves(root->right);
  }
}

// print all the nodes of left boundary
// this function will not print the leaves viewed from left side
void printLeft(node* root)
{
  if(root){
    if(root->left != NULL){
      cout<<root->data<<" ";
      // recursively move down the left subtree
      printLeft(root->left);
    }
    else if(root->right){
      cout<<root->data<<" ";
      // recursively move down the right subtree
      printLeft(root->right);
    }
  }
}

// print all the nodes of right boundary
// this function will not print the leaves viewed from the right side
void printRight(node* root)
{
  // printing is done after moving down the tree
  // thus printing is done in bottom up manner
  if(root){
    if (root->right) {
      printRight(root->right);
      cout<<root->data<<" ";
    }
    else if (root->left) {
      printRight(root->left);
      cout<<root->data<<" ";
    }
  }
}

void boundaryUtil(node* root)
{
  // first print the root, then print the left boundary
  // then the leaves which are seen from bottom
  // at last print the right boundary
  if(root){
    cout<<root->data<<" ";
    printLeft(root->left);
    printLeaves(root->left);
    printLeaves(root->right);
    printRight(root->right);
  }
}

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

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

  boundaryUtil(root);
}
5 7 9 1 4 3

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

import java.util.*;

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

class Main{

  // print the leaves (nodes from the bottom)
  static void printLeaves(node root)
  {
    if(root != null){
      // recursively solve the problem for the left subtree
      printLeaves(root.left);
      // if current node is a leaf
      if ((root.left) == null && (root.right) == null)
        System.out.print(root.data+" ");
      // recursively solve the problem for right subtree
      printLeaves(root.right);
    }
  }

  // print all the nodes of left boundary
  // this function will not print the leaves viewed from left side
  static void printLeft(node root)
  {
    if(root != null){
      if(root.left != null){
        System.out.print(root.data+" ");
        // recursively move down the left subtree
        printLeft(root.left);
      }
      else if(root.right != null){
        System.out.print(root.data+" ");
        // recursively move down the right subtree
        printLeft(root.right);
      }
    }
  }

  // print all the nodes of right boundary
  // this function will not print the leaves viewed from the right side
  static void printRight(node root)
  {
    // printing is done after moving down the tree
    // thus printing is done in bottom up manner
    if(root != null){
      if(root.right != null){
        printRight(root.right);
        System.out.print(root.data+" ");
      }
      else if(root.left != null){
        printRight(root.left);
        System.out.print(root.data+" ");
      }
    }
  }

  static void boundaryUtil(node root)
  {
    // first print the root, then print the left boundary
    // then the leaves which are seen from bottom
    // at last print the right boundary
    if(root != null){
      System.out.print(root.data+" ");
      printLeft(root.left);
      printLeaves(root.left);
      printLeaves(root.right);
      printRight(root.right);
    }
  }

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

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

    boundaryUtil(root);
  }
}
5 7 9 1 4 3

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

מורכבות זמן

O (N) כי עברנו בכל צמתי העץ. אנו עוברים דרך הצמתים כאשר אנו משתמשים בפונקציה printLeft, printRight ו- printLeaves. לפיכך מורכבות הזמן היא לינארית.

מורכבות בחלל

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