Прелазак границе бинарног стабла  


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

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

Проблем „Прелазак границе бинарног стабла“ наводи да вам је дато бинарно стабло. Сада треба да одштампате гранични приказ а бинарно стабло. Овдје прелазак границе значи да су сви чворови приказани као граница стабла. Чворови се виде са горње, леве, доње и десне стране у смеру супротном од кретања казаљке на сату. Али ако бисмо директно штампали све ове погледе, то ће резултирати исписом истих чворова више пута. Дакле, испишите гранични приказ тако да се чворови не понављају.

Пример  

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

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

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

НА), јер смо прешли све чворове стабла. Кроз чворове се крећемо када користимо функцију принтЛефт, принтРигхт и принтЛеавес. Стога је временска сложеност линеарна.

Види такође
Направите целокупно бинарно стабло из његовог приказа повезане листе

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

О (Х), где је Х висина стабла. То је зато што стек компајлера користи простор. А функције које се користе за испис граничних елемената користе рекурзију која се рачуна за стек компајлера.