Дарахти ҷустуҷӯи бинариро тасдиқ кунед


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Amazon себ Асано Atlassian Блумберг ByteDance Citadel Facebook Microsoft Oracle Qualities VMware Yahoo
Ҷустуҷӯи аввал Барқароркунӣ Дарахт

Масъалаи

In Дарахти ҷустуҷӯи бинариро тасдиқ кунед мушкилоте, ки мо решаи а дарахт, мо бояд тафтиш кунем, ки он дарахти ҷустуҷӯи дуӣ аст ё не.

Намуна:

Дарахти ҷустуҷӯи бинариро тасдиқ кунед

Натиҷа:

ҳақиқӣ

Шарҳ: Дарахти додашуда дарахти ҷустуҷӯи бинарӣ мебошад, зеро ҳамаи унсурҳое, ки ба ҳар як дарахт мондаанд, аз решаи дарахт хурдтаранд. Ҳама унсурҳое, ки ба ҳар як дарахти рост рост меоянд, аз решаи субтри калонтаранд ва ҳар як дарахт худ як дарахти ҷустуҷӯи дуӣ мебошад.

усул

  • Аввалан, мо номуайянӣ мекунем гузариш аз дарахти додашуда ва онро дар ан асал. Пас мо месанҷем, ки оё массив бо тартиби афзоянда мураттаб карда шудааст. Он гоҳ мо мегӯем, ки ин дарахти ҷустуҷӯи дуӣ аст, дар сурате ки он дарахти ҷустуҷӯи дуӣ нест.
  • Барои кам кардани истифодаи фазои ёрирасон, мо гиреҳи қаблан диданшударо пайгирӣ карда метавонем ва агар гиреҳи кунунӣ аз гиреҳи қаблӣ хурдтар бошад, пас ин нест дарахти ҷустуҷӯи бинарӣ ва агар ҳамаи гиреҳҳои қаблӣ аз гиреҳи кунунӣ хурдтар бошанд, пас он дарахти ҷустуҷӯи дуӣ мебошад.
  • Мо метавонем аз истифодаи фазои иловагӣ бо гузаштани гиреҳи гузашта ҳамчун параметр канорагирӣ намоем.

Коди C ++ барои дарахти ҷустуҷӯи бинариро тасдиқ кунед

// 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 барои тасдиқи дарахти ҷустуҷӯи дуӣ

// 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

Мураккабии вақт

Эй (н) чунон ки мо ҳар як гиреҳро танҳо як маротиба убур мекунем.

Мураккабии фазо

Эй (н) зеро мо ҳар як гиреҳи тайшударо нигоҳ медорем ва месанҷем, ки массив бо тартиби афзоянда ҷобаҷо карда шудааст, то тафтиш кунем, ки дарахт дарахти ҷустуҷӯи бинарӣ аст ё не.

Адабиёт