درخت باینری
_ _ حداکثر باینری _ _به روش زیر ساخته شده است: _
حداکثر درخت دوتایی را از دو درخت دودویی داده شده درخت باینری بسازید
حداکثر درخت دوتایی را از دو درخت دودویی داده شده بسازید
با توجه به دو مورد درختان دودویی ، وظیفه ایجاد یک است حداکثر درخت دودویی از دو درخت باینری داده شده و چاپ کنید Inorder Traversal از آن درخت
حداکثر درخت دودویی چقدر است؟
_ _ حداکثر باینری _ _به روش زیر ساخته شده است: _
_در مورد هر دو درخت دودویی دارای دو گره متناظر ، حداکثر دو مقدار به عنوان مقدار گره حداکثر درخت دودویی در نظر گرفته می شود. _
_اگر هر یک از دو گره NULL باشد و اگر گره دیگر null نباشد ، آن مقدار را در آن گره حداکثر درخت دودویی وارد کنید. _
مثال:
Input: Tree 1 Tree 2 3 5 / / 2 6 1 8 / 20 2 8 Output: 20 2 2 5 8 8 Explanation: 5 / 2 8 / 20 2 8 To construct the required Binary Tree, Root Node value: Max(3, 5) = 5 Root->left value: Max(درخت باینری 2, 1) = 2 Root->right value: Max(6, 8) = 8 Root->left->left value: 20 Root->left->right value: 2 Root->right->right value: 8 Input: Tree 1 Tree 2 9 5 / / 2 6 1 8 / 20 3 2 8 Output: 20 2 3 9 8 8 Explanation: 9 / 2 8 / 20 3 8
#ساختار داده ها #ریاضی #بازگشت #درخت #پیش ثبت سفارش #پیمایش درخت
www.geeksforgeeks.org
حداکثر درخت دوتایی را از دو درخت دودویی داده شده بسازید
یک پورتال علوم کامپیوتر برای گیک ها. این شامل مقالات علوم کامپیوتر و برنامه نویسی به خوبی نوشته شده ، خوب فکر شده و به خوبی توضیح داده شده است ، آزمونها و تمرینات/رقابتی.
ساختمان داده جستجوی درخت دودویی در جاوا (Java Binary Search Tree) آموزش برنامه نویسی جاوا Java
درختی است که هر گره آن دارای حداکثر دو گره فرزند است که به آنها فرزند راست و چپ گره گفته می‌شود. به همین ترتیب زیردرختی که درخت باینری فرزند راست در رأس آن قرار دارد زیردرخت راست و زیردرختی که فرزند چپ در رأس آن قرار دارد زیردرخت چپ گره نامیده می‌شوند.
درخت جستجوی دودویی
درختی دودویی است که برای هر گره آن شروط زیر برقرار هستند:
۱- مقادیر تمامی گره‌های زیردرخت راست – در صورت وجود – از مقدار گره بزرگتر هستند.
۲- مقادیر تمامی گره‌های زیردرخت چپ – در صورت وجود – از مقدار گره کوچکتر هستند.
با توجه به چنین تعریفی، واضح است که فرزندان چپ و راست یک گره در صورت وجود به ترتیب مقداری کمتر و بیشتر از مقدار خود گره دارند.
کاربرد درخت جستجوی دودویی
Java Binary Search Tree
مهمترین کاربرد چنین درختی از نام آن مشخص است. این درخت با توجه به تعریف آن برای انجام عملیات جستجو مناسب است. فرض کنید در مجموعه اعداد درخت فوق به دنبال عدد ۶ هستیم. ابتدا ۶ را با مقدار گره رأس یعنی۵ مقایسه می‌کنیم. این گره، گره مورد نظر ما نیست. عدد ۶ هم از عدد ۵ بزرگتر است. در نتیجه با توجه به تعریف درخت جستجوی دودویی، مطمئن هستیم که اگر گرهی با مقدار۶ وجود داشته باشد، به طور حتم در زیردرخت راست گره ۵ است. پس به سمت راست حرکت کرده و عدد ۶ را با ۸ مقایسه می‌کنیم. باز هم به گره مطلوب نرسیدیم. اما با توجه به اینکه ۶ از ۸ کوچکتر است، به زیردرخت چپ گره ۸ مراجعه می‌کنیم. در این مرحله به گره با مقدار ۶ می‌رسیم که گره مطلوب ما است.
اگر در حین جستجو مجبور به حرکت به سمتی شدیم که زیردرختی وجود ندارد، به این معنی است که گره مورد نظر در درخت وجود ندارد.
عملیات‌های اصلی بر روی درخت جستجوی دودویی
Java Binary Search Tree
معمولاً عملیات زیر بر روی یک درخت جستجوی دودویی تعریف می‌شود:
- ایجاد یک درخت جستجوی خالی
- آزمایش خالی بودن درخت
- درج کردن یک کلید جدید در درخت، بدون برهم خوردن خاصیت درخت
- جستجو کردن و یافتن یک کلید خاص در درخت
- حذف کردن یک کلید از درخت، با حفط خاصیت درخت
- پیمایش درخت جستجوی دودویی، به طوری تمام گره‌ها دقیقاً یک بار مورد دسترسی قرار گیرند.
درج گره جدید در درخت جستجوی دودویی
Java Binary Search Tree
زمانی که اقدام به درج یک گره جدید در درخت جستجوی دودویی می‌کنیم، باید محل مناسبی برای این گره پیدا کنیم. برای یافتن محل مناسب، فرض می‌کنیم که چنین گرهی در درخت وجود دارد و عملیات جستجو را برای آن درخت باینری انجام می‌دهیم. در نهایت به طور حتم به گرهی خواهیم رسید که حداقل یکی از فرزندان آن تهی است (چرا؟). این گره والد گره جدید خواهد بود.
برای مثال فرض کنید می‌خواهیم گرهی با مقدار ۷ را به درخت زیر اضافه کنیم:
و اگر گرهی با مقدار صفر درج کنیم:
زمانی که قصد ساخت یک درخت جستجوی دودویی را داریم، ترتیب درج مقادیر تاثیر مستقیمی در عمق درخت و سرعت اجرای عملیات جستجو خواهد داشت. اگر مجموعه اعداد وارد شده از قبل مرتب باشند، درخت به دست آمده از عمق n خواهد بود که در هر لایه‌ی آن تنها یک گره وجود دارد:
حذف گره از درخت جستجوی دودویی
Java Binary Search Tree
حذف گره از درخت جستجوی دودویی پیچیده‌گی‌هایی دارد که گاهی گره را تنها با علامت‌گذاری حذف می‌کنند. به عبارت دیگر در این حالت هر گره درخت شامل فیلدی است که وضعیت حذف آن را مشخص میکند. اگر گرهی را با استفاده از تغییر مقدار این فیلد حذف کنیم، در عمل حافظه آن آزاد نشده و تغییری در ساختار درخت ایجاد نمی‌شود. اما در پردازش‌های آتی، این گره را در نظر نمی‌گیریم. اما گاهی نیاز است که گره به طور کامل حذف شده و حافظه‌ی مصرفی آن نیز آزاد شود.
هر گره در درخت جستجوی دودویی ممکن است در یکی از سه وضعیت زیر باشد:
۱٫گره فاقد فرزند است: یعنی گره مذکور یک برگ است. در چنین حالتی به راحتی می‌توان گره را حذف کرده و فضای مصرفی آن را آزاد کرد.
۲٫گره دارای یک فرزند است: در این حالت گره فرزند را جایگزین گره مذکور می‌کنیم. به عبارت ساده‌تر، بین والد گره و فرزند گره ارتباط مستقیم برقرار کرده و گره مطلوب را حذف می‌کنیم.
۳٫گره دارای دو فرزند است: این حالت کمی پیچیده‌تر از حالت‌های قبلی است. ابتدا گرهی با کوچک‌ترین مقدار در زیردرخت راست گره را درخت باینری پیدا می‌کنیم. درج این گره به جای گره قبلی شروط درخت جستجوی درخت باینری دودویی را به هم نمی‌زند (چرا؟). در نتیجه می‌توان به راحتی آن را جایگزین کرد.
گرهی که جایگزین می‌شود به طور حتم فرزند چپ ندارد (چرا؟). اما ممکن است فرزند راست داشته باشد. در این حالت عمل حذف طی دو مرحله انجام می‌شود. ابتدا گره جایگزین از محل خود بنا به حالت شماره‌ی ۲حذف می‌شود. سپس گره اصلی با جایگزین شدن این گره حذف می‌گردد. حال نوبت به پیاده سازی درخت دودویی جستجو در جاوا رسیده است.
پیاده سازی درخت جستجوی دودویی
Java Binary Search Tree
برای پیاده سازی درخت دودویی در جاوا ابتدا باید یک کلاس برای نگهداری مقدار هر گره و فرزندان چپ و راست آن داشته باشیم.کلاس Node همین کار را برای ما میکند.
