ایجاد درخت با لیست پیوندی

[azita90]

سلام.صبح همه بخیر.من میخوام یک درخت رو با لیست پیوندی پیاده سازی کنم.(جستجوی best first search) اما توی کلاس bfs اجازه تعریف اشاره گر از نوع bfsNode رو بهم نمیده.لطفا راهنمایی ام کنید.

1.JPG

[ROSTAM2]

این چه نوع نوشتن Struct ِ ، منم بودم اجازه نمی دادم

[azita90]

این چه نوع نوشتن Struct ِ ، منم بودم اجازه نمی دادم

خب من اینو توی کلاس گذاشتمش و درست شد.اما حالا یه مشکل بزرگتر دارم:
میخواهم درخت جستجوی BFS رو با لینک لیست پیاده سازی کنم.میشه یه توضیحی بدین که توی حلقه ی while اینکار رو میشه کرد یا نه؟یعنی هر بار بفهمیم که child ای وجود داره یانه و اگه وجود داره اونو توی لینک لیست درج کنبم؟

[Davidd]

تعريف كلاس bfs كاملا اشتباهه. شما بايد براي درخت كلاس بسازي و الگوريتم bfs روي درخت اجرا بشه. فيلدهاي top , left , ... براي چي هست؟ تو درخت (باينري) هر نود يك فرزند چپ و يك فرزند راست داره ( درخت غيرباينري يك ليست فرزند داره).
اين يك كلاس و الگوريتم bfs براي درخت باينري :

 class TreeNode

    {

        public TreeNode(int data) { this.data = data; }

       public int data;

       public TreeNode Left;

       public TreeNode Right;

    }





 TreeNode t = new TreeNode(10);

            t.Left = new TreeNode(5);

            t.Right = new TreeNode(11);

            t.Left.Left = new TreeNode(3);



   

            Queue<TreeNode> childs = new Queue<TreeNode>();

            childs.Enqueue(t);

            while (childs.Count>0)

            {

                TreeNode temp = childs.Dequeue();

                

                //print temp.data

                if (temp.Left!=null)

                {

                    childs.Enqueue(temp.Left);

                }

                if (temp.Right != null)

                {

                    childs.Enqueue(temp.Right);

                }

[azita90]

خیلی ممنون.چون هر گره حداکثر4تا فرزند داره که در 4 جهتش هستند(پازل8) من leftNode و ... رو در نظر گرفتم.درست متوجه نشدم.لیستی از فرزندان یعنی چجوری؟میشه یه کد واسش بنویسید؟

[Davidd]

خیلی ممنون.چون هر گره حداکثر4تا فرزند داره که در 4 جهتش هستند(پازل8) من leftNode و ... رو در نظر گرفتم.درست متوجه نشدم.لیستی از فرزندان یعنی چجوری؟میشه یه کد واسش بنویسید؟

اگه يك درخته كه هر نود حداكثر 4 تا فرزند داره كد بالارو ميتوني راحت تغيير بدي ( من نميتونم درختي تصور كنم كه يك فرزند بالا، پايين، چپ و راست داشته باشه چون تبديل به گراف ميشه)

class TreeNode

   {

       public TreeNode(int data) { this.data = data; }

      public int data;

      public TreeNode Child1;



      public TreeNode Child2;

            public TreeNode Child3;

      public TreeNode Child4;



   }

 

 TreeNode t=// نودها را به درخت اضاف كنيد

           Queue<TreeNode> childs = new Queue<TreeNode>();

           childs.Enqueue(t);

           while (childs.Count>0)

           {

               TreeNode temp = childs.Dequeue();

                

               //print temp.data

               if (temp.Child1!=null)



               {

                   childs.Enqueue(temp.Child1);



               }

               if (temp.Child2!= null)



               {

                   childs.Enqueue(temp.Child2);



               }

                 if (temp.Child3!=null)

               {

                   childs.Enqueue(temp.Child3);



               }

               if (temp.Child4!= null)



               {

                   childs.Enqueue(temp.Child4);



               }

                                                                                                                                                                                                                                                                

[azita90]

ممنون از توضیحاتتون.من مبتدی ام و تاحالا نه درخت ساختم و نه با صف کارکردم! تقریبا فهمیدم کدتون چیکار می کنه اما میشه لطف کنید و نحوه عملکرد خط13 ب بعد رو یه توضیحی بدین؟
میشه لطف کنید و بگید چجوری بایدبه فرزندان ریشه ، فرزند اضافه کنم؟یعنی آیا باید توی یک حلقه while چک کنم که آیا به وضعیت هدف (توی پازل8) رسیدم یا نه و اگه نرسیده بودم ، یک عمق دیگه به درخت اضافه کنم.درسته؟

[Davidd]

خب با اين اوصاف من هرچي هم توضيح بدم باز شما تو مرحله بعدش ميموني. من از پازل 8 و كاربرد bfs توي پازل 8 چيزي نميدونم.
روش ساخت درخت و اضافه كردن ريشه با مقدار 5 :

TreeNode t=new TreeNode(5);

اضافه كردن يك نود به عنوان فرزند اول ريشه با مقدار فرضي 2:

t.Child1=new TreeNode(2);

اضافه كردن فرزند دوم به فرزند اول ريشه :

t.Child1.Child2=new TreeNode(3);

توضيح خط 13 به بعد! ابتدا ريشه به صف اضافه ميشه. توي حلقه while يك نود از صف خارج ميشه و پردازش ميشه (مثلا چاپ مقدار نود) و سپس چنانچه اين نود فرزندي داشته باشد، فرزندادن به ترتيب به صف اضافه مي شوند. اين روند تا زماني كه تمام نودها پردازش شوند(صف خالي شود) ادامه مي يابد.

[azita90]

ممنون از لطفتون! حالا کاملا متوجه شدم. موفق باشید!