Хоёртын модны хил хязгаар  


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Accolite Амазоны явган аялал Критикал шийдэл Microsoft- Morgan Stanley PayU Snapdeal
Хоёртын мод Мод Мод хөндлөн гарах

Асуудлын мэдэгдэл  

"Хоёртын модны хилийн дагуу туулах" асуудалд танд хоёртын мод өгдөг гэж заасан байдаг. Одоо та a-ийн зааг дүрсийг хэвлэх хэрэгтэй хоёртын мод. Энд зааг дамжин өнгөрөх гэдэг нь бүх зангилаа модны зааг хэлбэрээр харагдаж байна гэсэн үг юм. Зангилаа нь дээд, зүүн, доод, баруун талаас цагийн зүүний эсрэг чиглэлд харагдана. Гэхдээ бид эдгээр бүх үзэл бодлыг шууд хэвлэх байсан бол ижил зангилаа олон удаа хэвлэгдэх болно. Тиймээс зангилаа давтагдахгүй байхаар хил хязгаарыг хэвлэ.

Жишээ нь  

2 3 5 6 4 7

Тайлбар

Энд бүх зангилаа нь хил хязгаарын зангилаа юм. Гэхдээ бид зангилаагаа цагийн зүүний эсрэг чиглэлд хэвлэх хэрэгтэй. Тиймээс бид 2-р үндсээс эхэлнэ. Дараа нь бид яг ижилхэн хөдөлж 2, 3, 4, 6, 4, 7 цэгүүдийг хэвлэ.

Хоёртын модны хил хязгаар

5 7 9 1 4 3

арга барил  

Асуудал нь модны хил хязгаарыг хэвлэхийг биднээс хүсч байна, энд бид зүүн, баруун, доод зааг байна. Хэрэв мод нь баруун эсвэл зүүн талын зааг байхгүй бол. үндэс нь өөрөө зүүн буюу баруун хязгаар гэж тооцогддог. Хэрэв бид хил хязгаарын цэгүүдийг хэвлэвэл хоёр зангилааны аль нь ч олон удаа хэвлэгдэхгүй байхыг анхаарах хэрэгтэй гэсэн нэг нөхцөл бий.

Асуудлыг шийдэхийн тулд бид модны зүүн хязгаараас эхэлнэ. Хэрэв тэр зангилаа зүүн талаасаа харагдаж байвал зангилаа зүүн хязгаарт хамаарна гэж бид хэлдэг. Үүнтэй адил бид баруун талын зангилаа ба навчны зангилааг тодорхойлдог. Зүүн хязгаарыг хэвлэхийн тулд бид модыг дайран өнгөрч, хэрэв үндэс нь зүүн зангилаатай бол нөгөө рүү шилжиж баруун зангилаа руу шилжих болно. Нэгэнт бид навчны зангилаан дээр очно. Бид навчны зангилаа рекурсив байдлаар тусад нь хэвлэдэг тул бид навчны зангилааг хэвлэдэггүй. Нэгэнт бид зүүн хил хязгаарыг барьж дуусгасан.

мөн үзнэ үү
Хоёртын модноос хамгийн дээд түвшний нийлбэрийг ол

Бид навчны зангилааг хэвлээд, зүүн модны навчийг рекурсив хэлбэрээр хэвлэв. Зүүн модны навчийг хэвлэсний дараа навчийг баруун дэд модонд хэвлэ. Ингэснээр навчны бүх зангилааг цагийн зүүний эсрэг чиглэлд хэвлэнэ. Навчийг хэвлэсний дараа бид баруун хилийн зангилаа хэвлэнэ. Энэ удаад зангилаагаа доороос дээш хэвлэх хэрэгтэй. Тиймээс дотор нь давтлага, эхлээд модны зүүн эсвэл баруун дэд модыг шийдэж, дараа нь одоогийн зангилааг pMicrrint болгоно.

Хоёртын модны Boundary Traversal-ийг хэвлэх 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

Хоёртын модны Boundary Traversal-ийг хэвлэх Java код  

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 нь модны өндөр юм. Учир нь хөрвүүлэгч стек нь орон зайг ашигладаг. Мөн хил хязгаарын элементүүдийг хэвлэхэд ашигладаг функцууд нь хөрвүүлэгч стекийг тооцдог рекурсийг ашигладаг.