روز درخت‌کاری

درخت یک ساختار مرتبه‌ای دارد که از اتصال چند گره بهم به‌وجود می‌آید. درخت‌ها انواع متفاوتی دارند، در این مقاله یکی از انواع آن را به نام درخت جستجوی دودویی (Binary search tree) را به‌همراه پیاده‌سازی آن بررسی می‌کنیم.

درخت جستجوی دودویی چیست؟

این درخت خود از درخت دودویی مشتق شده است. درخت دودویی درختی است که هر گره آن دو فرزند دارد. درخت جستجوی دودویی یک تفاوت اصلی با درخت دودویی دارد. در درخت جستجوی دودویی (برخلاف درخت دودویی که ترتیب ذخیره‌سازی داده‌ها در آن مهم نیست)، مقدار فرزند راست باید از گره پدر بیشتر باشد و مقدار فرزند چپ از گره پدر کوچکتر. این تفاوت باعث افزایش سرعت جستجوی اطلاعات در درخت جستجو دودویی می‌شود.

پیاده‌سازی

برای پیاده‌سازی درخت جستجو دودویی نیاز به تعریف ساختار زیر داریم:

class BSTnode{

public:

   int data;

   BSTnode *left, *right;

   BSTnode(){

      left = right = NULL;  }

   BSTnode(int dat, BSTnode *lft

=NULL, BSTnode *rgt=NULL){

      data = dat;

      left = lft;

      right = rgt; }

}

هر شیء از کلاس BSTnode نمایانگر یک گره از درخت است. برای ساخت درخت ابتدا باید ریشه آنرا تعریف کنیم. ریشه، اولین عضو درخت است و هیچ فرزندی هم ندارد. بنابراین دستور تولید آن به‌این صورت می‌شود:

BSTnode *root = new BSTnode(data,NULL,NULL);

برای درج عناصر باید قاعده بالا را رعایت کنیم، برای افزودن گره به درخت از تابع زیر استفاده می‌کنیم:

void insert (int el, BSTnode* &myroot){

if (myroot == NULL){

   myroot = new BSTnode (el,NULL,NULL);

   cout «« el «« " inserted\n"; }

else if (el « myroot-»data){

   insert(el , myroot-»left); }

else if (el » myroot-»data){

   insert(el,myroot-»right);}

}

همان‌طور که می‌بینید، اگر مقدار myRoot تهی باشد، ابتدا مقداردهی می‌شود، سپس گره مشخص در جای خود قرار می‌گیرد، برای ساخت درخت، زمانی که درخت هیچ داده‌ای را ذخیره نکرده است، مقدار myRoot برابر ریشه درخت است.

پیمایش درخت

منظور از پیمایش درخت نمایش داده‌های درون درخت و پردازش آنها است. سه روش برای پیمایش درخت وجود دارد:

1- روش پیشوندی: ابتدا پردازش گره و سپس پیمایش پیشوندی فرزند چپ، سپس پیمایش پیشوندی فرزند راست.

?- روش میانوندی: ابتدا پیمایش میانوندی فرزند چپ، سپس پردازش گره، و پس از آن پیمایش پسوندی فرزند راست.

?- روش پسوندی: ابتدا پیمایش پسوندی فرزند چپ، سپس پیمایش پسوندی فرزند راست، پس از آن پیمایش پردازش داده.

جستجو در درخت جستجو دودویی

جستجو در درخت جستجوی دودویی سریع‌تر از جستجو در درخت دودویی است، به این علت که فقط نیمی از درخت مورد بررسی قرار می‌گیرد. به‌عنوان مثال شما دنبال داده‌ای به‌نام X هستید. اگر مقدار X از ریشه بزرگتر باشد، فرزندان سمت راست و در غیر این‌صورت فرزندان چپ درخت را بررسی می‌کنید. نوشتن برنامه جستجو برای درخت جستجو دودویی این‌گونه است:

bool search(int el, BSTnode* &start) {

   if (start != NULL){

      if (el « start-»data) {

         return search(el,start-»left); }

else if (el » start-»data){

         return search(el,start-»right); }

else{

      return true; }

return false;}

}

مقدار عمق درخت

برای این کار از یک تابع برگشتی استفاده می‌کنیم:

int depth(BSTnode* start){

if(start == NULL){

   return 0; }

else{

   return max(depth(start-»left),

   depth(start-»right)) + 1; }

}

خالی بودن یک درخت

اگر مقدار ریشه برابر تهی باشد یعنی درخت خالی است. به‌همین ترتیب اگر مقدار leftChild برابر تهی باشد، درخت فرزند چپ ندارد و همین‌طور برای rightChild اگر برابر تهی باشد درخت فرزند راست ندارد. برای مطالعه بیشتر و دریافت متن برنامه به لینک زیر بروید:

http://www.esnips.com/web/jamejam-click/

امیربهاالدین سبط‌الشیخ