]-->lang="fa-IR"> آموزش تشخیص BST بودن یک درخت باینری | مرکز درس

آموزش تشخیص BST بودن یک درخت باینری

تصور کنید که یک درخت باینری به شما داده شده است و از شما خواسته شده است که ببینید که این درخت یک درخت جستجوی باینری یا همون BST هست یا خیر.یک  BST یک ساختمان داده درخت باینری است که قابلیت‌های زیر را دارد.

  • در همه موارد عناصر زیردرخت راست از ریشه بزرگ‌تر است.
  • در همه موارد عناصر زیردرخت چپ از ریشه کوچک‌تر است
  • زیردرخت سمت چپ و زیردرخت سمت راست خود یک BST هستند.

مورد آخر به این معنی است که هر نودی را که شما در نظر بگیرید از ۲ قاعده اول تبعیت می کنند. با توجه به مواردی که گفته شد یک  BST هیچ‌وقت عضو تکراری ندارد.

در این مطلب از مرکز درس می‌خواهیم مسأله گفته شده را حل کنیم یعنی یک درخت باینری داریم و می‌خواهیم مشخص کنیم که این درخت  BST است یا خیر. ایده این کار به این صورت است که به صورت inorder درخت را پیمایش می‌کنیم و هر بار مقدار نود قبلی را نگهداری می کنیم. به خاطر اینکه پیمایش inorder یک  BST باعث به وجود آمدن یک آرایه مرتب می‌شود پس در هر بار پیمایش باید مقدار قبلی ازمقدار کنونی کمتر باشد. در غیر این صورت درخت  BST نیست. کد c++ این برنامه در ادامه آورده شده است.

#include  
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; 
 } 
}; 

// Utility function to check if Binary Tree is BST 
bool isBSTUtil(struct Node* root, int& 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 (root->data    return false; 

  // Initialize prev to current 
  prev = root->data; 

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

 return true; 


// Function to check if Binary Tree is BST 
bool isBST(Node* root) 

 int prev = INT_MIN; 
 return isBSTUtil(root, prev); 


/* Driver program to test above functions*/
int main() 

 struct Node* root = new Node(5); 
 root->left = new Node(2); 
 root->right = new Node(15); 
 root->left->left = new Node(1); 
 root->left->right = new Node(4); 

 if (isBST(root)) 
  cout  else
  cout 
 return 0; 



دقت کنید که در کد بالا همانطور که  BST را به صورت بازگشتی تعریف کردیم تابع isBSTUtil نیز به صورت بازگشتی تعریف شده است تا بتواند پیمایش inorder را به راحتی انجام دهد. همچنین برای بار اول مقدار prev برابر با کوچکترین عدد int قرار داده شده است

منبع: tosinso.com

بیشتر بخوانید :   آموزش نصب قالب وردپرس در CPanel 
ساسان سروشه

نوشته‌های مرتبط

دیدگاه‌ها

*
*