பைனரி தேடல் மரத்தை சரிபார்க்கவும்


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது அமேசான் ஆப்பிள் ஆசனா அட்லாசியன் ப்ளூம்பெர்க் ByteDance சிட்டாடல் பேஸ்புக் மைக்ரோசாப்ட் ஆரக்கிள் Qualtrics , VMware யாகூ
ஆழம் முதல் தேடல் மறுசுழற்சி மரம்

பிரச்சனை

In பைனரி தேடல் மரத்தை சரிபார்க்கவும் ஒரு மூலத்தை நாங்கள் கொடுத்துள்ளோம் மரம், இது ஒரு பைனரி தேடல் மரமா இல்லையா என்பதை நாம் சரிபார்க்க வேண்டும்.

உதாரணமாக :

பைனரி தேடல் மரத்தை சரிபார்க்கவும்

வெளியீடு:

உண்மை

விளக்கம்: கொடுக்கப்பட்ட மரம் ஒரு பைனரி தேடல் மரம், ஏனென்றால் ஒவ்வொரு துணை மரத்திற்கும் எஞ்சியிருக்கும் அனைத்து கூறுகளும் சப்டிரீயின் வேரை விட சிறியதாக இருக்கும். ஒவ்வொரு சப்டிரீக்கும் சரியான அனைத்து உறுப்புகளும் சப்டிரீயின் வேரை விட பெரியவை மற்றும் ஒவ்வொரு சப்டிரீயும் ஒரு பைனரி தேடல் மரமாகும்.

அணுகுமுறை

  • முதலில், நாங்கள் ஒழுங்கற்ற முறையில் செய்கிறோம் குறுக்குவெட்டு கொடுக்கப்பட்ட மரத்தின் மற்றும் அதை ஒரு சேமிக்கவும் வரிசை. வரிசை அதிகரிக்கும் வரிசையில் வரிசைப்படுத்தப்பட்டுள்ளதா என்பதை நாங்கள் சரிபார்க்கிறோம். அது ஒரு பைனரி தேடல் மரம் என்று நாங்கள் சொல்கிறோம், அது பைனரி தேடல் மரம் அல்ல.
  • துணை இடத்தின் பயன்பாட்டைக் குறைக்க, முன்னர் பார்வையிட்ட முனையை நாம் கண்காணிக்க முடியும், தற்போதைய முனை முந்தைய முனையை விட சிறியதாக இருந்தால் அது ஒரு அல்ல பைனரி தேடல் மரம் முந்தைய முனைகள் அனைத்தும் தற்போதைய முனையை விட சிறியதாக இருந்தால் அது பைனரி தேடல் மரம்.
  • முந்தைய முனையை ஒரு அளவுருவாக அனுப்புவதன் மூலம் கூடுதல் இடத்தைப் பயன்படுத்துவதை நாம் தவிர்க்கலாம்.

பைனரி தேடல் மரத்தை சரிபார்க்க சி ++ குறியீடு

// C++ program to check if a given tree is BST. 
#include <bits/stdc++.h> 
using namespace std; 

/* A binary tree node has data, pointer to 
left child and a pointer to right child */
struct Node 
{ 
  int data; 
  struct Node* left, *right; 
  
  Node(int data) 
  { 
    this->data = data; 
    left = right = NULL; 
  } 
}; 


bool isBSTUtil(struct Node* root, Node *&prev) 
{ 
  // traverse the tree in inorder fashion and 
  // keep track of prev node 
  if (root) 
  { 
    if (!isBSTUtil(root->left, prev)) 
    return false; 

    // Allows only distinct valued nodes 
    if (prev != NULL && root->data <= prev->data) 
    return false; 

    prev = root; 

    return isBSTUtil(root->right, prev); 
  } 

  return true; 
} 

bool isBST(Node *root) 
{ 
   Node *prev = NULL; 
   return isBSTUtil(root, prev); 
} 

/* Driver program to test above functions*/
int main() 
{ 
  struct Node *root = new Node(3); 
  root->left	 = new Node(2); 
  root->right	 = new Node(5); 
  root->left->left = new Node(1); 
  root->left->right = new Node(4); 

  if (isBST(root)) 
    cout << "Is BST"; 
  else
    cout << "Not a BST"; 

  return 0; 
} 

பைனரி தேடல் மரத்தை சரிபார்க்க ஜாவா குறியீடு

// Java program to check if a given tree is BST. 
class Check
{ 
/* A binary tree node has data, pointer to 
left child and a pointer to right child */
static class Node 
{ 
  int data; 
  Node left, right; 
  
  Node(int data) 
  { 
    this.data = data; 
    left = right = null; 
  } 
}; 
static Node prev; 

static boolean isBSTUtil(Node root) 
{ 
  // traverse the tree in inorder fashion and 
  // keep track of prev node 
  if (root != null) 
  { 
    if (!isBSTUtil(root.left)) 
    return false; 

    // Allows only distinct valued nodes 
    if (prev != null && root.data <= prev.data) 
    return false; 

    prev = root; 

    return isBSTUtil(root.right); 
  } 
  return true; 
} 

static boolean isBST(Node root) 
{ 
  return isBSTUtil(root); 
} 

// Driver Code 
public static void main(String[] args) 
{ 
  Node root = new Node(3); 
  root.left	 = new Node(2); 
  root.right	 = new Node(5); 
  root.left.left = new Node(1); 
  root.left.right = new Node(4); 

  if (isBST(root)) 
    System.out.print("Is BST"); 
  else
    System.out.print("Not a BST"); 
} 
} 
Not a BST

நேர சிக்கலானது

ஓ (n) ஒவ்வொரு முனையையும் ஒரு முறை மட்டுமே பயணிக்கிறோம்.

விண்வெளி சிக்கலானது

ஓ (n) ஏனென்றால், ஒவ்வொரு பயணிக்கும் முனையையும் நாங்கள் சேமித்து வருகிறோம், மேலும் மரம் பைனரி தேடல் மரமா இல்லையா என்பதை சரிபார்க்க வரிசை அதிகரிக்கும் வகையில் வரிசைப்படுத்தப்பட்டுள்ளதா என்பதை சரிபார்க்கவும்.

குறிப்புகள்