نحوه پیمایش درخت دودویی

این درخت پیمایش‌های گوناگونی دارد ولی سه تای آن‌ها اصلی‌تر و مهمتر هستند:

In-order یا LVR (چپ، ریشه، راست): در این حالت ابتدا گره‌های سمت چپ ملاقات (چاپ) می‌شوند و سپس ریشه و بعد گره‌های سمت راست.

Pre-Order یا VLR (ریشه، چپ، راست) : در این حالت ابتدا گره‌های ریشه ملاقات می‌شوند. بعد گره‌های سمت چپ و بعد گره‌های سمت راست.

Post_Order یا LRV (چپ، راست، ریشه ): در این حالت ابتدا گره‌های سمت چپ، بعد راست و نهایتا ریشه، ملاقات می‌شوند.

حتما متوجه شده‌اید که منظور از v در اینجا ریشه است و با تغییر و جابجایی مکان این سه حرف RLV میتوانید به ترکیب‌های مختلفی از پیمایش دست پیدا کنید.

اجازه دهید روی شکل بالا پیمایش LVR را انجام دهیم: همانطور که گفتیم باید اول گره‌های سمت چپ را خواند، پس از 17 به سمت 9 حرکت می‌کنیم و می‌بینیم که 9، خود والد است. پس به سمت 6 حرکت می‌کنیم و می‌بینیم که فرزند چپی ندارد؛ پس خود 6 را ملاقات می‌کنیم، سپس فرزند راست را هم بررسی می‌کنیم که فرزند راستی ندارد پس کار ما اینجا تمام است و به سمت بالا حرکت می‌کنیم. 9 را ملاقات می‌کنیم و بعد عدد 5 را و به 17 بر می‌گردیم. 17 را ملاقات کرده و سپس به سمت 15 می‌رویم و الی آخر ...

6-9-5-17-8-15-10

VLR:

17-9-6-5-15-8-10

LRV:

6-5-9-8-10-15-17

نحوه پیاده سازی درخت دودویی:

public class BinaryTree<T>
{
    /// <summary>مقدار داخل گره</summary>
    public T Value { get; set; }
 
    /// <summary>فرزند چپ گره</summary>
    public BinaryTree<T> LeftChild { get; private set; }
 
    /// <summary>فرزند راست گره</summary>
    public BinaryTree<T> RightChild { get; private set; }
   
    /// <summary>سازنده کلاس</summary>
    /// <param name="value">مقدار گره</param>
    /// <param name="leftChild">فرزند چپ</param>
    /// <param name="rightChild">فرزند راست
    /// </param>
    public BinaryTree(T value,
        BinaryTree<T> leftChild, BinaryTree<T> rightChild)
    {
        this.Value = value;
        this.LeftChild = leftChild;
        this.RightChild = rightChild;
    }
 
    /// <summary>سازنده بدون فرزند
    /// </summary>
    /// <param name="value">the value of the tree node</param>
    public BinaryTree(T value) : this(value, null, null)
    {
    }
 
    /// <summary>‏‏‎LVR پیمایش</summary>
    public void PrintInOrder()
    {
        // ملاقات فرزندان زیر درخت چپ
        if (this.LeftChild != null)
        {
            this.LeftChild.PrintInOrder();
        }
 
        // ملاقات خود ریشه
        Console.Write(this.Value + " ");
 
        // ملاقات فرزندان زیر درخت راست
        if (this.RightChild != null)
        {
            this.RightChild.PrintInOrder();
        }
    }
}
 
/// <summary>
/// نحوه استفاده از کلاس بالا
/// </summary>
public class BinaryTreeExample
{
    static void Main()
    {
        BinaryTree<int> binaryTree =
            new BinaryTree<int>(14,
                    new BinaryTree<int>(19,
                          new BinaryTree<int>(23),
                          new BinaryTree<int>(6,
                                  new BinaryTree<int>(10),
                                  new BinaryTree<int>(21))),
                    new BinaryTree<int>(15,
                          new BinaryTree<int>(3),
                          null));
 
        binaryTree.PrintInOrder();
        Console.WriteLine();
 
        // خروجی
        // 23 19 10 6 21 14 3 15
    }
}

تفاوتی که این کد با کد قبلی که برای یک درخت معمولی داشتیم، در این است که قبلا لیستی از فرزندان را داشتیم که با خاصیت Children شناخته می‌شدند، ولی در اینجا در نهایت دو فرزند چپ و راست برای هر گره وجود دارند. برای جست و جو هم از الگوریتم In_Order استفاده کردیم که از همان الگوریتم DFS آمده‌است. در آنجا هم ابتدا گره‌های سمت چپ به صورت بازگشتی صدا زده می‌شدند. بعد خود گره و سپس گره‌های سمت راست به صورت بازگشتی صدا زده می‌شدند.

برای باقی روش‌های پیمایش تنها نیاز است که این سه خط را جابجا کنید:

  // ملاقات فرزندان زیر درخت چپ
        if (this.LeftChild != null)
        {
            this.LeftChild.PrintInOrder();
        }
 
        // ملاقات خود ریشه
        Console.Write(this.Value + " ");
 
        // ملاقات فرزندان زیر درخت راست
        if (this.RightChild != null)
        {
            this.RightChild.PrintInOrder();
        }

درخت دودویی مرتب شده Ordered Binary Search Tree

تا این لحظه ما با ساخت درخت‌های پایه آشنا شدیم: درخت عادی یا کلاسیک و درخت دو دویی. ولی در بیشتر موارد در پروژه‌های بزرگ از این‌ها استفاده نمی‌کنیم چرا که استفاده از آن‌ها در پروژه‌های بزرگ بسیار مشکل است و باید به جای آن‌ها از ساختارهای متنوع دیگری از قبیل درخت‌های مرتب شده، کم عمق و متوازن و کامل و پر و .. استفاده کرد. پس اجازه دهید که مهمترین درخت‌هایی را که در برنامه نویسی استفاده می‌شوند، بررسی کنیم.

همان طور که می‌دانید برای مقایسه اعداد ما از علامتهای <>= استفاده می‌کنیم و اعداد صحیح بهترین اعداد برای مقایسه هستند. در درخت‌های جست و جوی دو دویی یک خصوصیت اضافه به اسم کلید هویت یکتا Unique identification  Key داریم که یک کلید قابل مقایسه است. در تصویر زیر ما دو گره با مقدارهای متفاوتی داریم که با مقایسه‌ی آنان می‌توانیم کوچک و بزرگ بودن یک گره را محاسبه کنیم. ولی به این نکته دقت داشته باشید که این اعداد داخل دایره‌ها، دیگر برای ما حکم مقدار ندارند و کلید‌های یکتا و شاخص هر گره محسوب می‌شوند.

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

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

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

مقایسه گره‌هایی که برای جست و جو انجام دادیم:

19-11-16-13

درخت هر چه بزرگتر باشد این روش کارآیی خود را بیشتر نشان می‌دهد.

using System;
using System.Text;
using System.Xml.Linq;

namespace DotNetTips
{
    public static class ExtentionMethods
    {
        public static string Set_PersianCharacter(this string value)
        {
            return value.Replace('ی', 'ی').Replace('ک', 'ک').Replace('ة', 'ت').Replace('إ', 'ا').Replace('أ', 'ا').Replace('ؤ', 'و');
        }

        public static string Format(this string value, params object[] param)
        {
            //For Example :  "test {0} , {1}, {2} , {3}".Format(10,11,12,13);    return => test 10 , 11, 12 , 13

            return string.Format(value, param);
        }

        public static string Apend(this string text, string value)
        {
            return new StringBuilder(text).Append(value).ToString();
        }

        public static string ApendFormat(this string text, string value, params object[] param)
        {
            return new StringBuilder(text).AppendFormat(value, param).ToString();
        }

        public static int ToInt(this string value)
        {
            return Convert.ToInt32(value);
        }

        public static bool IsNullOrEmpty(this string value)
        {
            return string.IsNullOrEmpty(value.Trim());
        }

        public static bool IsNull(this object obj)
        {
            return obj == null;
        }

        public static XElement AddElement(this XElement element, XElement subElement)
        {
            /* For Example :
            var element = new XElement("Root").AddElement(new XElement("element1")).AddElement(new XElement("element2")); 
            
            return => <Root>
                         <element1 />
                         <element2 />
                      </Root>
            */
            element.Add(subElement);
            return element;
        }
        public static XElement SetAttribute(this XElement element, XName name, object value)
        {
            //For Example : var elementt = new XElement("Root").SetAttribute("name", "").SetAttribute("Id", 10);    return => <Root name="" url="10" />

            element.SetAttributeValue(name, value);
            return element;
        }
    }
}

public class EntityConfigurations
    {
        internal static void LoadEntityConfigurations(Assembly[] asm, DbModelBuilder modelBuilder)
        {
            if (asm == null) throw new ArgumentNullException(nameof(asm));

            foreach (var configurations in asm.Select(assembly => assembly.GetTypes()
                    .Where(
                     type => type.BaseType != null &&
                     type.BaseType.IsGenericType &&
                     type.BaseType.GetGenericTypeDefinition() == typeof(EntityTypeConfiguration<>))
                    .ToList()))
            {
                configurations.ForEach(type =>
                {
                    dynamic instance = Activator.CreateInstance(type);
                    modelBuilder.Configurations.Add(instance);
                });
            }
        }
    }

/// <summary>
        /// 
        /// </summary>
        /// <param name="modelBuilder"></param>
        protected override void OnModelCreating(DbModelBuilder modelBuilder)
        {
            EntityConfigurations.LoadEntityConfigurations(AppDomain.CurrentDomain.GetAssemblies(), modelBuilder);
        }

using System.Drawing;

namespace PWS.ObjectOrientedPaint.Models
{
    /// <summary>
    /// Triangle
    /// </summary>
    public class Triangle : Shape
    {
        #region Constructors (2)

        /// <summary>
        /// Initializes a new instance of the <see cref="Triangle" /> class.
        /// </summary>
        /// <param name="startPoint">The start point.</param>
        /// <param name="endPoint">The end point.</param>
        /// <param name="zIndex">Index of the z.</param>
        /// <param name="foreColor">Color of the fore.</param>
        /// <param name="thickness">The thickness.</param>
        /// <param name="isFill">if set to <c>true</c> [is fill].</param>
        /// <param name="backgroundColor">Color of the background.</param>
        public Triangle(PointF startPoint, PointF endPoint, int zIndex, Color foreColor, byte thickness, bool isFill, Color backgroundColor)
            : base(startPoint, endPoint, zIndex, foreColor, thickness, isFill, backgroundColor)
        {
            ShapeType = ShapeType.Triangle;
        }


        /// <summary>
        /// Initializes a new instance of the <see cref="Triangle" /> class.
        /// </summary>
        public Triangle()
        {
            ShapeType = ShapeType.Triangle;
        }

        #endregion Constructors

        #region Methods (1)

        // Public Methods (1) 

        /// <summary>
        /// Draws the specified g.
        /// </summary>
        /// <param name="g">The g.</param>
        public override void Draw(Graphics g)
        {
            var points = new PointF[3];
            points[0] = new PointF(X + Width / 2, Y);
            points[1] = new PointF(X + Width, Y + Height);
            points[2] = new PointF(X, Y + Height);
            if (IsFill)
                g.FillPolygon(BackgroundBrush, points);
            g.DrawPolygon(new Pen(ForeColor, Thickness), points);
            base.Draw(g);
        }

        #endregion Methods
    }
}

۰۰۰۰۰۰۰۰۰۰
۱۱۱۱۱۱۱۱۱۱
۲۲۲۲۲۲۲۲۲۲
۳۳۳۳۳۳۳۳۳۳
۴۴۴۴۴۴۴۴۴۴
۵۵۵۵۵۵۵۵۵۵
۶۶۶۶۶۶۶۶۶۶
۷۷۷۷۷۷۷۷۷۷
۸۸۸۸۸۸۸۸۸۸
۹۹۹۹۹۹۹۹۹۹

public static class Helpers
    {
        /// <summary>
        /// تعیین معتبر بودن کد ملی
        /// </summary>
        /// <param name="nationalCode">کد ملی وارد شده</param>
        /// <returns>
        /// در صورتی که کد ملی صحیح باشد خروجی <c>true</c> و در صورتی که کد ملی اشتباه باشد خروجی <c>false</c> خواهد بود
        /// </returns>
        /// <exception cref="System.Exception"></exception>
        public static Boolean IsValidNationalCode(this String nationalCode)
        {
           //در صورتی که کد ملی وارد شده تهی باشد

            if (String.IsNullOrEmpty(nationalCode))
                throw new Exception("لطفا کد ملی را صحیح وارد نمایید");


            //در صورتی که کد ملی وارد شده طولش کمتر از 10 رقم باشد
            if (nationalCode.Length != 10)
                throw new Exception("طول کد ملی باید ده کاراکتر باشد");

            //در صورتی که کد ملی ده رقم عددی نباشد
            var regex = new Regex(@"\d{10}");
            if (!regex.IsMatch(nationalCode))
                throw new Exception("کد ملی تشکیل شده از ده رقم عددی می‌باشد؛ لطفا کد ملی را صحیح وارد نمایید");

            //در صورتی که رقم‌های کد ملی وارد شده یکسان باشد
            var allDigitEqual = new[]{"0000000000","1111111111","2222222222","3333333333","4444444444","5555555555","6666666666","7777777777","8888888888","9999999999"};
            if (allDigitEqual.Contains(nationalCode)) return false;


            //عملیات شرح داده شده در بالا
            var chArray = nationalCode.ToCharArray();
            var num0 = Convert.ToInt32(chArray[0].ToString())*10;
            var num2 = Convert.ToInt32(chArray[1].ToString())*9;
            var num3 = Convert.ToInt32(chArray[2].ToString())*8;
            var num4 = Convert.ToInt32(chArray[3].ToString())*7;
            var num5 = Convert.ToInt32(chArray[4].ToString())*6;
            var num6 = Convert.ToInt32(chArray[5].ToString())*5;
            var num7 = Convert.ToInt32(chArray[6].ToString())*4;
            var num8 = Convert.ToInt32(chArray[7].ToString())*3;
            var num9 = Convert.ToInt32(chArray[8].ToString())*2;
            var a = Convert.ToInt32(chArray[9].ToString());

            var b = (((((((num0 + num2) + num3) + num4) + num5) + num6) + num7) + num8) + num9;
            var c = b%11;

            return (((c < 2) && (a == c)) || ((c >= 2) && ((11 - c) == a)));
        }
    }

if(TextBoxNationalCode.Text.IsValidNationalCode ())
     //some code

//OR

if(Helpers.IsValidNationalCode (TextBoxNationalCode.Text))
     //some code

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

مدل گزارش دهی

new PersianDateTime(t.ResponseDate.Value).ToString(PersianDateTimeFormat.DateShortTime)

    /// <summary>
    /// Initializes a new instance of the PersianDateTime class to a specified dateTime.
    /// </summary>
    /// <param name="dateTime">A date and time in the Gregorian calendar.</param>
    public PersianDateTime(DateTime dateTime)
    {
        _dateTime = dateTime;
    }

1. استفاده از جداول جدا برای هر کدام از جداول به صورتیکه یک ارتباط یک به چند مابین آنها برقرار است. از این جداول تحت عنوان HistoryTable یاد می‌شود.
2. استفاده از یک جدول برای نگهداری تاریخچه‌ی تغییرات جداولی که نیازمند این امکان هستند. 

using System.Drawing;

namespace PWS.ObjectOrientedPaint.Models
{
    /// <summary>
    /// Rectangle
    /// </summary>
    public class Rectangle : Shape
    {
        #region Constructors (2)

        /// <summary>
        /// Initializes a new instance of the <see cref="Rectangle" /> class.
        /// </summary>
        /// <param name="startPoint">The start point.</param>
        /// <param name="endPoint">The end point.</param>
        /// <param name="zIndex">Index of the z.</param>
        /// <param name="foreColor">Color of the fore.</param>
        /// <param name="thickness">The thickness.</param>
        /// <param name="isFill">if set to <c>true</c> [is fill].</param>
        /// <param name="backgroundColor">Color of the background.</param>
        public Rectangle(PointF startPoint, PointF endPoint, int zIndex, Color foreColor, byte thickness, bool isFill, Color backgroundColor)
            : base(startPoint, endPoint, zIndex, foreColor, thickness, isFill, backgroundColor)
        {
            ShapeType = ShapeType.Rectangle;
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="Rectangle" /> class.
        /// </summary>
        public Rectangle()
        {
            ShapeType = ShapeType.Rectangle;
        }

        #endregion Constructors

        #region Methods (1)

        // Public Methods (1) 

        /// <summary>
        /// Draws the specified g.
        /// </summary>
        /// <param name="g">The g.</param>
        public override void Draw(Graphics g)
        {
            if (IsFill)
                g.FillRectangle(BackgroundBrush, StartPoint.X, StartPoint.Y, Width, Height);
            g.DrawRectangle(Pen, StartPoint.X, StartPoint.Y, Width, Height);
            base.Draw(g);
        }

        #endregion Methods
    }
}

using System;
using System.Drawing;

namespace PWS.ObjectOrientedPaint.Models
{
    /// <summary>
    /// Square
    /// </summary>
    public class Square : Rectangle
    {
#region Constructors (2) 

        /// <summary>
        /// Initializes a new instance of the <see cref="Square" /> class.
        /// </summary>
        /// <param name="startPoint">The start point.</param>
        /// <param name="endPoint">The end point.</param>
        /// <param name="zIndex">Index of the z.</param>
        /// <param name="foreColor">Color of the fore.</param>
        /// <param name="thickness">The thickness.</param>
        /// <param name="isFill">if set to <c>true</c> [is fill].</param>
        /// <param name="backgroundColor">Color of the background.</param>
        public Square(PointF startPoint, PointF endPoint, int zIndex, Color foreColor, byte thickness, bool isFill, Color backgroundColor)
        {
            float x = 0, y = 0;
            float width = Math.Abs(endPoint.X - startPoint.X);
            float height = Math.Abs(endPoint.Y - startPoint.Y);
            if (startPoint.X <= endPoint.X && startPoint.Y <= endPoint.Y)
            {
                x = startPoint.X;
                y = startPoint.Y;
            }
            else if (startPoint.X >= endPoint.X && startPoint.Y >= endPoint.Y)
            {
                x = endPoint.X;
                y = endPoint.Y;
            }
            else if (startPoint.X >= endPoint.X && startPoint.Y <= endPoint.Y)
            {
                x = endPoint.X;
                y = startPoint.Y;
            }
            else if (startPoint.X <= endPoint.X && startPoint.Y >= endPoint.Y)
            {
                x = startPoint.X;
                y = endPoint.Y;
            }
            StartPoint = new PointF(x, y);
            var side = Math.Max(width, height);
            EndPoint = new PointF(x+side, y+side);
            ShapeType = ShapeType.Square;
            Zindex = zIndex;
            ForeColor = foreColor;
            Thickness = thickness;
            BackgroundColor = backgroundColor;
            IsFill = isFill;
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="Square" /> class.
        /// </summary>
        public Square()
        {
            ShapeType = ShapeType.Square;
        }

#endregion Constructors 
    }
}