ساختار داده درخت دودویی

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

بازنمایی درخت دودویی

یک درخت باینری توسط یک اشاره گر به بالاترین گره (که معمولاً به عنوان "ریشه" شناخته می شود) درخت نشان داده می شود. اگر درخت خالی باشد ، مقدار ریشه تهی است. هر گره یک درخت باینری شامل قسمتهای زیر است:

1. داده ها
2. اشاره گر به کودک چپ
3. اشاره گر به کودک راست

عملکرد اساسی روی درخت باینری:

• درج یک عنصر.
• حذف یک عنصر.
• در جستجوی یک عنصر.
• عبور از درخت.

عمل کمکی روی درخت باینری:

• پیدا کردن ارتفاع درخت
• سطح گره درخت را پیدا کنید
• پیدا کردن اندازه کل درخت.

موضوع :

• معرفی
• عمل اصلی

• گذرگاه
• مشکلات استاندارد در درختان باینری

معرفی :

1. آشنایی با درخت باینری - ساختار داده و آموزش الگوریتم
2. خواص درخت باینری
3. انواع درخت باینری
4. برنامه ها ، مزایا و مضرات درخت باینری
5. درخت باینری (اجرای آرایه)
6. درخت باینری کامل
7. درخت باینری عالی

عملیات اساسی روی درخت باینری:

1. گذرگاه های درختی (Inorder ، Preworder و Postorder)
2. تراز درخت سفارش سطح
3. حداکثر عمق یا ارتفاع درخت باینری داده شده را پیدا کنید
4. درج در یک درخت باینری
5. حذف در یک درخت باینری
6. شمارش درختان باینری

برخی از مسیرهای مهم دیگر باینری درختان:

1. سطح سفارش سطح به شکل مارپیچی
2. ردیابی سفارش سطح معکوس
3. BFS در مقابل DFS برای درخت باینری
4. گذرگاه درختی بدون بازگشت
5. Morris Traversal برای پیش نویس
6. پیمایش پیش ساخته تکراری
7. گذرگاه پستی تکراری با استفاده از دو پشته
8. گذرگاه مورب درخت باینری
9. گذرگاه مرزی درخت باینری

باید مشکلات استاندارد را در ساختار داده های درخت باینری حل کنید:

• آسان
  1. عمق یک درخت باینری کامل را از پیش تنظیم محاسبه کنید
  2. درختی را از مسافر inorder و سطح سفارش دهید
  3. بررسی کنید که آیا یک درخت باینری داده شده sumtree است
  4. بررسی کنید که آیا دو گره پسر عموی در یک درخت باینری هستند
  5. بررسی کنید که آیا از بین بردن لبه می تواند یک درخت باینری را در دو نیمه تقسیم کند
  6. بررسی کنید که آیا یک درخت باینری معین کامل است یا خیر
  7. بررسی کنید که آیا یک درخت باینری حاوی زیر درختان کپی به اندازه 2 یا بیشتر است
  8. بررسی کنید که آیا دو درخت آینه است
  9. درختان باینری تاشو
  10. درخت متقارن (تصویر آینه از خود)
  11. برای تعیین اینکه آیا دو درخت یکسان هستند ، کد را بنویسید
  12. زیر درخت با مبلغ داده شده در یک درخت باینری
  13. رمزگذاری مختصر درخت باینری
  14. برای محاسبه اندازه یک درخت برنامه ای بنویسید
  15. قطر یک درخت باینری
  16. سطح یک گره را در یک درخت باینری دریافت کنید
• متوسط
  1. تمام درخت های دودویی ممکن را با پیمایش Inorder داده شده پیدا کنید
  2. جانشین Inorder را برای همه گره ها پر کنید
  3. درخت باینری کامل را از نمایش لیست پیوندی آن بسازید
  4. حداقل مبادله مورد نیاز برای تبدیل درخت باینری به درخت جستجوی باینری
  5. یک درخت باینری داده شده را به لیست پیوندی دوگانه تبدیل کنید |مجموعه 1
  6. یک درخت را به جنگل گره های زوج تبدیل کنید
  7. درخت دودویی را برگردانید
  8. چاپ مسیرهای ریشه به برگ بدون استفاده از بازگشت
  9. بررسی کنید که آیا پیمایش های Preorder، Inorder و Postorder از یک درخت هستند یا خیر
  10. بررسی کنید که آیا درخت باینری داده شده کامل است یا نه |مجموعه 1 (راه حل تکراری)
  11. بررسی کنید که آیا یک درخت باینری زیردرخت درخت باینری دیگر است |مجموعه 2
  12. بزرگترین مجموع زیردرخت را در یک درخت بیابید
  13. حداکثر مجموع گره ها در درخت باینری به طوری که هیچ دو مجاور وجود نداشته باشند
  14. پایین ترین جد مشترک در یک درخت باینری |مجموعه 1
  15. ارتفاع یک درخت عمومی از آرایه والد
  16. فاصله بین دو کلید داده شده از یک درخت باینری را پیدا کنید
• سخت
  1. یک درخت دودویی را تغییر دهید تا پیمایش پیش سفارش را فقط با استفاده از نشانگرهای راست انجام دهید
  2. درخت دودویی کامل را با استفاده از پیمایش پیش سفارش آن و پیمایش پیش سفارش درخت آینه آن بسازید
  3. از پیمایش پیش سفارش داده شده، یک درخت ویژه بسازید
  4. ساخت درخت از ماتریس اجداد
  5. درخت k-ary کامل را از پیمایش پیش سفارش آن بسازید
  6. درخت دودویی را از رشته با نمایش براکت بسازید
  7. یک درخت باینری را به صورت مارپیچی به فهرست پیوندی دوتایی تبدیل کنید
  8. یک درخت باینری را به یک لیست دایره ای پیوند دوتایی تبدیل کنید
  9. تبدیل عبارت سه تایی به درخت باینری
  10. بررسی کنید که آیا مسیر ریشه به برگ با توالی داده شده وجود دارد یا خیر
  11. Remove all nodes which don’t lie in any path with sum>= k
  12. حداکثر مجموع مارپیچ در درخت دودویی
  13. مجموع گره ها در سطح k-ام در یک درخت به صورت رشته نمایش داده می شود
  14. مجموع تمام اعدادی که از مسیرهای ریشه تا برگ تشکیل شده اند
  15. ادغام دو درخت دودویی با انجام Node Sum (باز گشتی و تکراری)
  16. ریشه درخت را پیدا کنید که در آن تعداد شناسه فرزندان برای هر گره داده می شود

لینک های سریع :

• "مشکلات تمرین" در درختان
• "کوئیز" در درختان دودویی
• "ویدیوها" در درختان

توصیه شده:

• آموزش ساختار داده ها و الگوریتم ها |آموزش DSA

اگر GeeksforGeeks را دوست دارید و مایل به مشارکت هستید، همچنین می توانید مقاله بنویسید و مقاله خود را به آدرس review-team@geeksforgeeks. org ایمیل کنید. مشاهده مقاله خود در صفحه اصلی GeeksforGeeks و به سایر Geeks کمک کنید. لطفاً در صورت مشاهده موارد نادرست، نظرات خود را بنویسید، یا می خواهید اطلاعات بیشتری در مورد موضوع مورد بحث در بالا به اشتراک بگذارید.