با سلام.اگه پیمایش preorder رو داشته باشیم و بخواهیم یک درخت کامل رسم کنیم چطور میشه اینکار رو انجام داد.آخه تو یه نکته ای خوندم که فقط با داشتن preorder میشه درخت یکتایی رو رسم کرد.
آیا با داشتن پیمایش های دیگه هم میشه چنین کاری رو انجام داد؟(فقط inorder رو داشته باشیم یا postorder)
با داشتن فقط یک پیمایش نمیشه یه درخت یکتا رو رسم کرد اگه دقت کنید علاوه بر داشتن پیمایش pre بر کامل بودن درخت هم تاکید شده یعنی گره های ما یا برگ هستند یا هم اگه برگ نیستند دو فرزند دارند.
دقیقا میشه این کار رو کرد . دقت کنید که درخت کامل شکلش معلومه . اول شکلش رو بدون اسم گره‌ها میکشیم بعد هم طبق روش Preorder اسامی رو تو گره‌ها می چینیم . به همین راحتی .
با preorder به تنهایی نمی شه درخت رسم کرد. نه واحد و نه غیر واحد
من تو کتاب ساختمان پوران خوندم که اگه فقط یکی از پیمایش های postorder یا preorder درخت جستجوی دودویی را داشته باشیم، میشه درخت یکتا رسم کرد چون پیمایش inorder در درخت جستجوی دودویی همون ارایه مرتب شده‌ی صعودیه که خودت می تونی بنویسی و با داشتن پیمایش inorder و preorder یا postorder می شه درخت منحصر به فرد کشید.
درست خوندین اما این بحث در مورد درخت هاست نه درخت های جستجوی دودویی
برای درخت ها پیمایش های مختلفی می توان مطرح کرد که سه نوع معمول آنها پیمایش preorder - postorder - level order و پیمایش inorder که مختص درخت های دودویی است.
اگر درخت کامل باشد با هر سه پیمایش و اگر درخت دودویی و کامل باشد با هر چهار پیمایش میشه درخت یکتا ساخت.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
کلاً برای رسم درخت باید در ابتدا ریشه درخت رو تشخیص بدیم بعدش زیر درخت راست و چپ اون و همین طور بطور بازگشتی پایین بریم تا به ریشه برسیم . در درختی که شکل ظاهری آن مشخصه ، مثل درخت کامل یا پر ، کافیه یه پیماش داشته باشیم تا درخت رو بطور یکتا ترسیم کنیم چرا که فقط کافیه بدونیم ریشه کدوم عنصره و با همین اطلاعات درخت رو تا پایین ترسیم میکنیم . دقیقا به همین علته که با داشتن پیمایش inorder یک درخت جستجوی دودویی نمیتونیم درخت رو بطور یکتا ترسیم کنیم چراکه نمیدونیم ریشه کدوم عنصره و نیز اینکه شکل مشخصی نداره
اگه درخت دودویی باشه می تونیم با pere یا pos به تنهای رسم کنیم زیرا اگه درخت رو به صورت صعودی بنویس پیمایش inorder درخت رو داریم پس می توان درخت رو رسم کرد
میشه درخت رو به صورت یکتا رسم کرد ولی نه به دلیل اینکه میتونیم صعودی بنویسیمش.
این موضوع روشنه که اگه pre و in رو داشته باشیم میتونیم درخت رو کتا رسم کنیم. درسته؟؟؟
از اون جهت که درخت BST (نه دودویی) رو اگه به صورت صعودی بنویسیم، پیمایش inorderش به دست میاد پس اگه فقط پیمایش preشو داشته باشیم میتونیم درختو یکتا رسم کنیم. نکتش فقط اینه که اگه BSTرو به صورت inorder پیمایش کنیم عناصر داخلش صعودی مرتب میشن. ولی این نکته در مورد درخت دودویی صادق نیست.
حالا اینجا که بحث BST نیس، بحث دودوییه. درختای دودویی رو همونطور که دوستان دیگه هم گفتن، با داشتن یه پیمایش فقط در صورتی میشه یکتا رسم کرد که گره تک فرزندی تو درخت موجود نباشه و اگه گره n تک فرزندی داشتیم هم میتونیم دو به توان n درخت رسم کنیم. یعنی درخت حاصل یکتا نخواهد بود. دلیلشم اینه... مثلاً فرض کنید ۲ تا گره A و B تک فرزندی داریم. فرزند گره A رو سمت چپ رسم کنید، بری این حالت فرزند گره B رو میشه یا چپ در نظر گرفت یا راست. یعنی ۲ حالت. حالا اگه فرزند گره A رو راست نظر بگیریم دوباره فرزند B رو میشه چپ یا راست رسم کرد. اینم دو حالت دیگه که در کل میشه ۴ حالت. یعنی دو به توان گره های تک فرزندی