در این مقاله انواع روش های جستجوی المان های یک درخت جستجوی دودویی (BST) را خواهیم آموخت. همانند جستجوی یک المان در یک BST ، یافتن کوچکترین و بزرگترین المان ها و یافتن المان های قبلی و بعدی یک المان مشخص ، از این موارد هستند.
درخت جستجوی دودویی
یک درخت جستجوی دودویی ، یک درخت دودویی با خاصیت جستجو است ؛ جایی که المان زیر شاخه ی چپ کوچکتر از ریشه و المان زیر شاخه ی راست بزرگتر از ریشه است.
به عنوان مثال :
جستجوی یک المان در یک درخت جستجوی دودویی (BST) :
برای یافتن یک المان در یک درخت جستجوی دودویی ابتدا باید المان را با گره ریشه مقایسه کنیم ؛ اگر مقادیر برابر بود آنگاه المان مورد نظر ما همان ریشه است ، در غیر اینصورت باید چپ یا راست را چک کنیم.
public object SearchElement_Rec(objectelement, TNoderoot) { current = root; if (current == null) return "Not found"; if (Convert.ToInt32(element)== Convert.ToInt32(current.Data)) return element; if (Convert.ToInt32(element)< Convert.ToInt32(current.Data)) return this.SearchElement_Rec(element,current.Left); else return this.SearchElement_Rec(element,current.Right); }
در زیر نتیجه ی اجرای کد را خواهید دید :
ورودی :
Console.WriteLine(bst.SearchElement_Ite(15));
خروجی:
ورودی :
Console.WriteLine(bst.SearchElement_Ite(19));
خروجی :
یافتن کوچکترین المان در درخت جستجوی دودویی (BST) :
یافتن کوچکترین المان در درخت جستجوی دودویی آسان است ، تنها کافیست که چپ ترین المان را بدست آوریم.
کد سی شارپ مربوط به آن به صورت زیر خواهد بود :
public object TreeMin_Rec(TNode root) { current = root; if (current.Left == null) { return current.Data; } returnTreeMin_Rec(current.Left); }
نتیجه ی اجرای کد بالا به صورت زیر خواهد بود :
ورودی :
Console.WriteLine(bst.TreeMin_Rec(bst.ReturnRoot()));
خروجی :
یافتن بزرگترین المان در درخت جستجوی دودویی (BST) :
یافتن بزرگترین المان در درخت جستجوی دودویی نیز آسان است ، تنها کافیست که راست ترین المان را بدست آوریم.
کد سی شارپ مربوط به آن به صورت زیر خواهد بود :
public object TreeMax_Rec(TNode root) { current = root; if (current.Right == null) { return current.Data; } returnTreeMax_Rec(current.Right); }
در زیر نتیجه ی اجرای کد بالا را میتوانید ببینید :
ورودی :
Console.WriteLine(bst.TreeMax_Rec(bst.ReturnRoot()));
خروجی :
یافتن المان بعدی در یک درخت جستجوی دودویی (BST) :
یافتن المان بعدی در یک درخت جستجوی دودویی کمی پیچیده تر است. در اینجا دو مورد را باید مد نظر داشت :
اگر زیر شاخه ی راست Null نباشد :
اگر زیر شاخه ی راست Null نباشد آنگاه برای یافتن المان بعدی ، باید کوچکترین المان زیر شاخه ی راست را پیدا
کرد. برای یافتن کوچکترین المان زیر شاخه ی راست میتوانیم از متد TreeMin_Rec که در بالا نشان داده شد استفاده کنید.
زیر شاخه ی راست Null باشد :
اگرشاخه ی راست Null باشد ، آنگاه نیاز داریم که المان بعدی را به طرز متفاوتی بدست بیاوریم. باید از گرهی (که المان بعدیش را احتیاج داریم) و تا جایی که سمت راست والدینش موجود است بالا رفت. در جایی که شاخه ی والد به سمت چپ رفت ، آن والد المان بعدی است (اگر Null نباشد)
اجرای آن در سی شارپ به صورت زیر خواهد بود :
public objectTreeSuccessor_Ite(object element) { ////Get the Node object for an element current = this.GetNode(element); if (current!=null) { if (current.Right!= null) returnthis.TreeMin_Rec(current.Right); else { tempParent = current.Parent; while((tempParent != null) && (current == tempParent.Right)) { current = tempParent; tempParent = tempParent.Parent; } if(tempParent != null) returntempParent.Data; else return"Successor is not found!"; } } else { return "Please enter the valid tree element!"; } }
در زیر نتیجه ی اجرا را خواهید دید. این دو مورد را پوشش میدهد ( به بیان دیگر زمانی که زیر شاخه ی چپ موجود باشد (المان ۲۰) و زمانی که موجود نباشد (المان ۱۶) و زمانی که المان بعدی موجود نباشد (المان ۴۵) را خواهیم داشت)
ورودی:
Console.WriteLine(bst.TreePredecessor_Ite(20));
خروجی:
ورودی:
Console.WriteLine(bst.TreePredecessor_Ite(16));
خروجی:
ورودی :
Console.WriteLine(bst.TreeSuccessor_Ite(45));
خروجی :
یافتن المان قبلی در یک درخت جستجوی دودویی (BST) :
یافتن المان قبلی دقیقا خلاف یافتن المان بعدی است (تنها کافیست جای کلمات چپ و راست را جا به جا کنید) در اینجا نیز دو مورد را باید در نظر بگیرید :
اگر زیر شاخه ی چپ Null نباشد :
اگر زیر شاخه ی چپ Null نباشد ، آنگاه برای یافتن المان قبلی باید بزگترین المان زیر شاخه ی چپ را پیدا کنیم. برای یافتن بزرگترین المان زیر شاخه ی چپ میتوانیم از متد TreeMax_Rec که در بالا نشان داده شد ، استفاده کنید.
اگر زیر شاخه ی چپ Null باشد :
اگر زیر شاخه ی چپ Null باشد آنگاه المان بعدی را باید به روش دیگری بدست آوریم. باید از گرهی ( که المان بعدیش را میخواهیم) شروع کنیم و تا جایی که والد در سمت راست قرار دارد بالا برویم. در گرهی که دیگر والد راست موجود نبود و تنها والد چپ داشتیم ؛ آنگاه آن والد المان بعدی خواهد بود (اگر Null نباشد).
در زیر نتیجه ی اجرای کد سی شارپ را میتوانیم ببینیم :
public objectTreeSuccessor_Ite(object element) { ////Get the Node object for an element current = this.GetNode(element); if (current!=null) { if (current.Right!= null) returnthis.TreeMin_Rec(current.Right); else { tempParent = current.Parent; while((tempParent != null) && (current == tempParent.Right)) { current = tempParent; tempParent = tempParent.Parent; } if(tempParent != null) returntempParent.Data; else return"Successor is not found!"; } } else { return "Please enter the valid tree element!"; } }
در زیر نتیجه ی اجرا را خواهید دید. این دو مورد را پوشش میدهد ( به بیان دیگر زمانی که زیر شاخه ی چپ موجود باشد (المان ۲۰) و زمانی که موجود نباشد (المان ۱۶) و زمانی که المان بعدی موجود نباشد (المان ۱۳) را خواهیم داشت)
ورودی:
Console.WriteLine(bst.TreePredecessor_Ite(20));
خروجی:
ورودی:
Console.WriteLine(bst.TreePredecessor_Ite(16));
خروجی:
ورودی:
Console.WriteLine(bst.TreePredecessor_Ite(13));
خروجی:
امیدوارم از این مقاله استفاده ببرید !
موفق باشید !
مرسی
۵