درخت جستجوی دودویی (BST) با استفاده از سی شارپ

در این مقاله انواع روش های جستجوی المان های یک درخت جستجوی دودویی (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));

خروجی:

امیدوارم از این مقاله استفاده ببرید !

موفق باشید !