52 : 36 : 09
مانده تا پایان تخفیف
فقط تا آخر امروز
فقط امروز
مهدی عادلی فر
بنیانگذار توسینسو و برنامه نویس

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

تصور کنید که یک درخت باینری به شما داده شده است و از شما خواسته شده است که ببینید که این درخت یک درخت جستجوی باینری یا همون BST هست یا خیر.یک  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 همراه باشید.

0 0
مهدی عادلی فر

بنیانگذار توسینسو و برنامه نویس

مهدی عادلی، بنیان گذار TOSINSO. کارشناس ارشد نرم افزار کامپیوتر از دانشگاه صنعتی امیرکبیر و #C و جاوا و اندروید کار می کنم. در زمینه های موبایل و وب و ویندوز فعالیت دارم و به طراحی نرم افزار و اصول مهندسی نرم افزار علاقه مندم.

نظرات