बाइनरी ट्री का बाउंड्री ट्रैवर्सल


कठिनाई स्तर मध्यम
में अक्सर पूछा एकोलाइट वीरांगना वृद्धि क्रिटिकल सॉल्यूशंस माइक्रोसॉफ्ट मॉर्गन स्टेनली PayU स्नैपडील
बाइनरी ट्री पेड़ वृक्ष का त्राटक

समस्या का विवरण

समस्या "बाइनरी ट्री की बाउंड्री ट्रैवर्सल" बताती है कि आपको बाइनरी ट्री दिया जाता है। अब आपको एक के सीमा दृश्य को प्रिंट करने की आवश्यकता है बाइनरी ट्री। यहां बाउंड्री ट्रैवर्सल का मतलब है कि सभी नोड्स को पेड़ की सीमा के रूप में दिखाया गया है। नोड्स को एंटी-क्लॉकवाइज दिशा में ऊपर की ओर, बाईं ओर, नीचे की तरफ, और दाईं ओर से देखा जाता है। लेकिन अगर हम इन सभी विचारों को सीधे प्रिंट कर लेते हैं, जिसके परिणामस्वरूप कई बार एक ही नोड की छपाई होगी। तो सीमा दृश्य को ऐसे प्रिंट करें कि नोड्स दोहराए नहीं जाते हैं।

उदाहरण

2 3 5 6 4 7

व्याख्या

यहां, सभी नोड्स सीमा नोड्स हैं। लेकिन हमें नोड्स को एक विरोधी घड़ी की दिशा में प्रिंट करने की आवश्यकता है। इस प्रकार हम उस जड़ से शुरू करते हैं जो 2. है। फिर, हम बस उसी तरीके से आगे बढ़ते हैं और नोड्स 2, 3, 4, 6, 4, 7 को प्रिंट करते हैं।

बाइनरी ट्री का बाउंड्री ट्रैवर्सल

5 7 9 1 4 3

दृष्टिकोण

समस्या हमें पेड़ की सीमा को प्रिंट करने के लिए कहती है, यहां हमने बाएं, दाएं और नीचे की सीमा को छोड़ दिया है। यदि पेड़ के पास कोई बाईं या दाईं सीमा नहीं है। मूल को ही बाईं या दाईं सीमा के रूप में माना जाता है। एक शर्त यह भी है कि यदि हम सीमा नोड्स को प्रिंट करते हैं, तो हमें ध्यान रखना होगा कि दोनों नोड्स में से कोई भी कई बार मुद्रित नहीं होता है।

समस्या को हल करने के लिए, हम पेड़ की बाईं सीमा के साथ शुरू करेंगे। हम कहते हैं कि एक नोड बाईं सीमा के अंतर्गत आता है यदि वह नोड बाईं ओर से दिखाई देता है। इसी तरह, हम सही साइड नोड्स और लीफ नोड्स को परिभाषित करते हैं। बाईं सीमा को मुद्रित करने के लिए, हम पेड़ को इस तरह से पार करेंगे कि यदि जड़ में एक बाएं नोड है तो उस पर जाएं और उसके दाएं नोड पर जाएं। एक बार हम पत्ती नोड को प्राप्त करेंगे। हम लीफ नोड्स को प्रिंट नहीं करते क्योंकि हम लीफ नोड्स को अलग से प्रिंट करते हैं। एक बार जब हम बाईं सीमा के साथ किया जाता है।

हम पत्तों के नोड्स को प्रिंट करते हैं, सबसे पहले बाईं उपरी पत्तियों को प्रिंट करके। बाएं सबट्री प्रिंट करने के बाद पत्तियों को राइट सबट्री में प्रिंट करें। इस तरह सभी लीफ नोड्स एक एंटी-क्लॉक वाइज दिशा में प्रिंट हो जाएंगे। एक बार जब हम पत्तियों को प्रिंट करते हैं, तो हम सही सीमा के नोड्स को प्रिंट करते हैं। इस बार नोड्स को बॉटम-अप तरीके से प्रिंट करना होगा। इस प्रकार अंदर प्रत्यावर्तन, पहले हम पेड़ के बाएं या दाएं सबट्री को हल करते हैं और फिर वर्तमान नोड को पिनक्रिमेंट करते हैं।

बाइनरी ट्री के बाउंड्री ट्रैवर्सल को प्रिंट करने के लिए सी ++ कोड

#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

जटिलता विश्लेषण

समय जटिलता

पर), क्योंकि हमने पेड़ के सभी नोड्स के माध्यम से पता लगाया है। जब हम PrintLeft, PrintRight और PrintLeaves फ़ंक्शन का उपयोग करते हैं, तो हम नोड्स के माध्यम से आगे बढ़ते हैं। इस प्रकार समय जटिलता रैखिक है।

अंतरिक्ष जटिलता

ओ (एच), जहाँ H वृक्ष की ऊँचाई है। ऐसा इसलिए है क्योंकि कंपाइलर स्टैक अंतरिक्ष का उपयोग करता है। और सीमा तत्वों को मुद्रित करने के लिए उपयोग किए जाने वाले फ़ंक्शन पुनरावर्तन का उपयोग करते हैं जो संकलक स्टैक के लिए मायने रखता है।