پبمایش درخت دودویی

[mmehrant]

سلام دوستان خسته نباشید

استادمون واسه پروژه نهایی این برنامه رو گفته پیاده سازی کنیم :

1. تعدادی عدد بگیرد و در آرایه ای ذخیره کند
2. آرایه را مرتب کند و در لیست باکس نمایش دهد
3. عدد میانه آرایه مرتب شده را به عنوان ریشه در نظر بگیرد
4.اعداد نامرتب را بصورت درخت دودویی و عدد میانی (شماره 3) را ریشه قرار دهد و در لیست باکس نشان دهد .

------------------------

حالا خدمتتون عرض کنم من تو قسمت پیاده سازی بصورت دودویی گیر کردم
این عکس رو هم ضمیمه کردم اگه ی نگاه بندازین کاملا متوجه میشید !

مثلا :
اعداد وارد شده توسط کاربر :
1
3
2
5
6
4
10
25
7
11

حالا مرتب شده :
1
2
3
4
5
6
7
10
11
15

در اینجا عدد 6 بعنوان ریشه در نظر گرفته میشه !
bst.png

اگه میشه یه کمکی بکنید که چطوری اینو پیاده سازی کنم ، دم همتون گرم 3>

[arash69]

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

[rahnema1]

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

تصاویر پیوستی می تونه بهتر نشون بده . به ترتیب نگاه کنید:

http://img.upload724.com/images/4135...7354914286.png ,

http://img.upload724.com/images/1360...5724130944.png

[mehdi zanjani]

با سلام.

به نظر من راه حل شما اینه که درخت BST تون رو به صورت AVL پیاده سازی کنید و در ضمن برای مرتب سازی آرایه و چاپ اون فقط کافیه درخت رو بصورت inorder پیمایش کنید!!

الگوریتم پیمایش inorder هم که تو همه کتابای ساختمان داده هست میتونید استفاده کنید، هم پیاده سازی AVL و هم پیاده سازی پیمایش میان ترتیب بسیار بسیار ساده است

موفق باشد.

[mmehrant]

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

خب مرسی همه اینا درست ، ولی مشکل از اونجایی شروع میشه که وقتی تو لیست باکس میخواد چاپ بشه باید هر سطح از سمت چپ به راست چاپ بشه ، به عکسی که ضمیمه کردم ی نگاه بندازی کاملا مشخص کردم
من اونجاش کارم گیره
پنجشنبه هم خیر سرم میخوام تویلش بدم :-s

[mmehrant]

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

تصاویر پیوستی می تونه بهتر نشون بده . به ترتیب نگاه کنید:

http://img.upload724.com/images/4135...7354914286.png ,

http://img.upload724.com/images/1360...5724130944.png

دستت درد نکنه توضیح خوبی بود ، ولی عکس های پیوستی لینکش خرابه عکس آپ نشده !!

[mmehrant]

با سلام.

به نظر من راه حل شما اینه که درخت BST تون رو به صورت AVL پیاده سازی کنید و در ضمن برای مرتب سازی آرایه و چاپ اون فقط کافیه درخت رو بصورت inorder پیمایش کنید!!

الگوریتم پیمایش inorder هم که تو همه کتابای ساختمان داده هست میتونید استفاده کنید، هم پیاده سازی AVL و هم پیاده سازی پیمایش میان ترتیب بسیار بسیار ساده است

موفق باشد.

آقا مرسی دمت گرم خیلی کمک کردی میرم دنبالش ببینم میتونم کاری کنم

[mmehrant]

آقا من تا اینجا برنامه سی شارپ رو اینطوری کار کردم .
یه نگاه بندازین لطفا
لینک فایل :

http://upir.ir/files/BST.rar

حجم : 72kb

[rahnema1]

سلا م ببخشید که لینک خراب بودtree2.png
و این یکی tree3.png

[mmehrant]

خب همه اینا صحیح ولی به اولین عکس تاپیک که گذاشتم و نحوه چاپش در لیست باکس نگاه کنید : ( چاپش به گونه ای بصورت سطح به سطح از سمت چپ هستش این قسمتش خیلی سخته ) !

[rahnema1]

موقع درست کردن درخت باید عمق درخت یا تعداد لایه های اون را بدست بیاورید
وقتی که درخت درست شد شما می تونید یک لیست تو در تو درست کنید
بنابراین لیست اصلی به تعداد لایه های درخت عضو دارد و هر عضو آن که من آن را زیر لیست می گم لیستی از گره ها است
در ابتدا برای لیست اصلی به تعداد لایه های درخت زیر لیست درست کنید
زیرلیست شماره 1 تنها یک عضو خواهد داشت اون همان درخت ماست که مقدار آن برابر است با میانه و دو زیرشاخه دارد
با استفاده از حلقه for به تعداد لایه های درخت:
زیرشاخه های گره موجود در زیرلیست اول را پیدا کرده و به زیرلیست دوم اضافه می کنیم بنابراین زیر لیست دوم دو عضو خواهد داشت
زیرشاخه های گره های موجود در زیرلیست دوم را پیدا کرده و به زیرلیست سوم اضافه می کنیم بنابراین زیر لیست سوم چهار عضو خواهد داشت و....
به همین ترتیب ادامه می دهیم تا حلقه for تموم بشه
با فرض اینکه گره ها از کلاس node باشند که قبلا ما تعریف کرده ایم لیست تو در تو از اینجوری میشه:

List<List<node>>

[Mahmoud.Afrad]

منظورت از درخ جستجوی دودویی چیه؟ الگوریتمش رو توضیح بده.

اگر منظورت جستجوی دودویی هست که بگه فلان عدد در آرایه وجود داره یا نه راحت تر از اینها میتونی کدش رو بنویسی. مهم اینه که بتونی به صورت فارسی توضیحش بدی.

[mmehrant]

منظورت از درخ جستجوی دودویی چیه؟ الگوریتمش رو توضیح بده.

اگر منظورت جستجوی دودویی هست که بگه فلان عدد در آرایه وجود داره یا نه راحت تر از اینها میتونی کدش رو بنویسی. مهم اینه که بتونی به صورت فارسی توضیحش بدی.

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

[mmehrant]

موقع درست کردن درخت باید عمق درخت یا تعداد لایه های اون را بدست بیاورید
وقتی که درخت درست شد شما می تونید یک لیست تو در تو درست کنید
بنابراین لیست اصلی به تعداد لایه های درخت عضو دارد و هر عضو آن که من آن را زیر لیست می گم لیستی از گره ها است
در ابتدا برای لیست اصلی به تعداد لایه های درخت زیر لیست درست کنید
زیرلیست شماره 1 تنها یک عضو خواهد داشت اون همان درخت ماست که مقدار آن برابر است با میانه و دو زیرشاخه دارد
با استفاده از حلقه for به تعداد لایه های درخت:
زیرشاخه های گره موجود در زیرلیست اول را پیدا کرده و به زیرلیست دوم اضافه می کنیم بنابراین زیر لیست دوم دو عضو خواهد داشت
زیرشاخه های گره های موجود در زیرلیست دوم را پیدا کرده و به زیرلیست سوم اضافه می کنیم بنابراین زیر لیست سوم چهار عضو خواهد داشت و....
به همین ترتیب ادامه می دهیم تا حلقه for تموم بشه
با فرض اینکه گره ها از کلاس node باشند که قبلا ما تعریف کرده ایم لیست تو در تو از اینجوری میشه:

List<List<node>>

من همون روی inorder کار مکنم چون به نظرم شاید خیلی بهتر به جواب برسم ،

به نظر شما من میتونم ریشه رو مثلا mid در نظر بگیرم
و زیر شاخه سمت چپ رو در یک آرایه right[]
و زیر شاخه چپ رو در یک آرایه left []
قرار بدم بعد هر کدوم که سطح دوم میشه left+1 و...

[rahnema1]

سلام، اون روشی که شما می خواهید level order هست نه inorder یعنی درخت را سطح به سطح یا به عبارت دیگه لایه به لایه پیمایش کنه من هم بر همین اساس مطلب رو نوشتم گرچه واسه level order روشهای دیگه هم هست واسه رفرنس یه نگاهی به این لینک بکنید:http://en.wikipedia.org/wiki/Tree_traversal

[rahnema1]

یک نکته دیگه اینکه شما دو تا کار باید انجام بدید
یکی درست کردن درخت در پست های قبلی با شکل گذاشتم حالا می تونید روش دیگری را برای درست کردن درخت در نظر بگیرید ولی مهم اینه که درخت ساخته بشه
دوم پیمایش درخته (واسه چاپ کردن گره ها اون جور که شما می خواهید) به صورت level order
همچنیم لازم نیست شما هنگام تشکیل درخت آرایه درست کنید مثلا آرایه سمت راست و چپ چون شما یک آرایه دارید که می خواهید اون را به گره تبدیل کنید بلکه لازمه مکان یا اندکس عناصر مورد نظر در آرایه را داشته باشید همچنین فراموش نشه هنگام درست کردن درخت یک متغیر هم داشته باشید که نهایتا تعداد لایه های ایجاد شده را برای شما ذخیره کنه
مرحله اول از تشکیل درخت ایجاد یک ساختار مناسبه که اینجا به صورت کلاس node تعریف کردیم یه چیزی شبیه این:

 public class node

 {

  public int value;

  public node(int Value)  {value=Value;}

  public node left;

        public node right;

 }

شما در الگوریتم بازگشتی مرتبا گره های راست و چپ را پر می کنید

[mmehrant]

آقا دست همگی درد نکنه
فردا پروژه رو تحویل میدم ، تشکر از همه بخصوص rahnema1 عزیز 3>

پروژه اونجوری ک باید تکمیل نشد ولی level order رو پیاده سازی کردم که در بعضی از شرایط جواب کاملا صحیح نیست ولی در کل ب نتیجه میرسم .
فایل نهایی ضمیمه شد ، اگه کسی خواست بعدا خودش تکمیلش کنه .
لطفا دیگه در این تاپیک پست نزارید که اسپم پیش نیاد مرسی یا حق.

http://upir.ir/files/BST-Final-Edition.rar

[mehdi zanjani]

سلام، اون روشی که شما می خواهید level order هست نه inorder یعنی درخت را سطح به سطح یا به عبارت دیگه لایه به لایه پیمایش کنه من هم بر همین اساس مطلب رو نوشتم گرچه واسه level order روشهای دیگه هم هست واسه رفرنس یه نگاهی به این لینک بکنید:http://en.wikipedia.org/wiki/Tree_traversal

دوست عزیز تو درخت BST تنها پیمایش inorder لیست رو مرتب میکنه بحث بهتر بودن نیست!!!

[rahnema1]

دوست عزیز تو درخت BST تنها پیمایش inorder لیست رو مرتب میکنه بحث بهتر بودن نیست!!!

با سلام و تشکر از پیگیری شما
بحث سر این نبود که چه پیمایشی لیست را مرتب می کنه بلکه بحث بر سر این بود که اعداد در لیست باکس بر اساس اون ترتیبی بیایند که در عکس بالا خواسته شده. خواهش می کنم یک بار دیگه با دقت توی عکس بالا به قسمت « ترتیب چاپ در لیست باکس » نگاه کنید اون ترتیبی که خواسته شده بر اساس level order هست نه inorder من هم در ابتدا به اون عکس دقیقا نگاه نکرده بودم بعدا که mmehrant اشاره کرد متوجه شدم که منظورش چیست
و با عذرخواهی از mmehrant که گفته بود دیگه کامنت توی این پست نذارید اما چون این مساله مطرح شد لازم دیدم همین جا پاسخ بدهم تا مساله روشن بشه

[f.beigirad]

با سلام
فایل حذف شده