تخفیف های ویژه عیدانه توسینسو
تا 60 درصد تخفیف ویژه
00ساعت 00دقیقه 00ثانیه

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

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

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

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

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


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

// 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 <= prev) 
   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 << "Is BST"; 
 else
  cout << "Not a BST"; 

 return 0; 



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

نویسنده: مهدی عادلی فر

منبع: tosinso.com

هرگونه نشر و کپی برداری بدون ذکر منبع و نام نویسنده دارای اشکال اخلاقی می باشد.

0 نظر

هیچ نظری ارسال نشده است! اولین نظر برای این مطلب را شما ارسال کنید...

نظر شما
برای ارسال نظر باید وارد شوید.
از سرتاسر توسینسو
تنظیمات حریم خصوصی
تائید صرفنظر
×

تو می تونی بهترین نتیجه رو تضمینی با بهترین های ایران بدست بیاری ، پس مقایسه کن و بعد خرید کن : فقط توی جشنواره پاییزه می تونی امروز ارزونتر از فردا خرید کنی ....