در این مقاله به بررسی روش پیاده‌سازی درخت دودویی در جاوا می‌پردازیم. ما در این راهنما از یک درخت دودویی مرتب استفاده می‌کنیم که شامل مقادیر عدد صحیح (int) است.

درخت دودویی در جاوا

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

در زیر بازنمایی مختصری از این نوع درخت دودویی را می‌بینید:

درخت دودویی در جاوا

ما برای پیاده‌سازی این درخت از یک کلاس کمکی Node استفاده می‌کنیم که مقادیر int را ذخیره می‌کند و ارجاعی به هر فرزند نگه می‌دارد:

در ادامه گره آغازین درخت را که «ریشه» (Root) نامیده می‌شود اضافه می‌کنیم:

عملیات رایج

در این بخش برخی از رایج‌ترین عملیات که می‌توان روی یک درخت دودویی اجرا کرد را بررسی می‌کنیم.

درج عنصر

نخستین عملیاتی که بررسی می‌کنیم درج گره‌های جدید در درخت دودویی است. ابتدا باید مکانی را بیابیم که می‌خواهیم گره جدید را به صورت ترتیبی اضافه کنیم تا کل درخت مرتب باقی بماند. برای درج گره جدید قواعد زیر را با آغاز از گره ریشه پیگیری می‌کنیم:

  • اگر مقدار گره جدید کمتر از گره کنونی باشد، به فرزند سمت چپ می‌رویم.
  • اگر مقدار گره جدید بزرگ‌تر از گره جاری باشد، به فرزند سمت راست می‌رویم.
  • زمانی که گره کنونی null باشد، به گره رسیده‌ایم و می‌توانیم گره جدید را در این موقعیت درج کنیم.

ابتدا یک متد بازگشتی برای انجام این عملیات درج ایجاد می‌کنیم:

سپس متد عمومی را ایجاد می‌کنیم که فرایند بازگشتی را از گره ریشه آغاز می‌کند:

اکنون بررسی می‌کنیم که چگونه می‌توانیم از این متد برای ایجاد درخت در مثال خود استفاده کنیم:

یافتن یک عنصر

در این بخش یک متد اضافه می‌کنیم تا بررسی کنیم آیا درخت شامل مقدار خاصی است یا نه. همانند عملیات قبل ابتدا یک متد بازگشتی می‌نویسیم تا درخت را پیمایش کنیم:

در این متد با مقایسه مقدار مورد نظر با مقادیر گره جاری به جستجوی آن می‌پردازیم و سپس بسته به نتیجه مقایسه، ادامه کار را در فرزندان سمت چپ یا راست ادامه می‌دهیم.

سپس متد عمومی را ایجاد می‌کنیم که از گره ریشه آغاز می‌شود.

اکنون می‌توانیم یک تست ساده بنویسیم که تأیید کند آیا درخت واقعاً شامل عنصر درج شده است یا نه.

همه گره‌های اضافه شده باید در درخت موجود باشند.

حذف یک عنصر

عملیات رایج دیگری که روی درخت‌های دودویی استفاده می‌شود، حذف یک گره از درخت است. ابتدا باید گرهی را که می‌خواهیم حذف کنیم به روشی که قبلاً معرفی کردیم بیابیم:

زمانی که گره مورد نظر را یافتیم، 3 حالت متفاوت وجود دارد:

  • این گره هیچ فرزندی ندارد: این ساده‌ترین حالت است و کافی است که گره را در والدینش با مقدار null عوض کنیم.
  • گره مورد نظر دقیقاً یک فرزند دارد: در این حالت در گره والد، این گره را با آن فرزند عوض می‌کنیم.
  • گره مورد نظر دو فرزند دارد: این پیچیده‌ترین حالت است، چون نیازمند سازماندهی مجدد درخت است.

در ادامه شیوه پیاده‌سازی حالت نخست را می‌بینید که در آن گره مورد نظر یک برگ است:

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

در کد فوق یک فرزند غیر تهی بازگشت می‌دهیم تا بتواند به گره والد انتساب یابد.

در نهایت باید حالتی را مدیریت کنیم که گره دو فرزند دارد. در این حالت ابتدا باید گرهی را که جایگزین گره حذف شده خواهد شد بیابیم. به این منظور از کوچک‌ترین گرهی که در زیردرخت سمت راست گره مورد نظر قرار دارد استفاده می‌کنیم:

سپس کمترین مقدار را به گرهی که باید حذف شود انتساب می‌دهیم و سپس آن را از زیردرخت راست حذف می‌کنیم.

در نهایت متد عمومی را ایجاد می‌کنیم که فرایند حذف را از ریشه آغاز می‌کند:

اکنون بررسی می‌کنیم که آیا عملیات حذف مطابق انتظار پیش می‌رود یا نه.

پیمایش یک درخت

در این بخش روش‌های مختلف پیمایش یک درخت را بررسی می‌کنیم و جستجوهای «عمق-اول» و «سطح-اول» را بررسی می‌کنیم. ما از همان درختی که قبلاً استفاده کردیم بهره می‌گیریم و ترتیب پیمایش را در هر حالت نمایش می‌دهیم.

جستجوی عمق-اول

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

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

در پیمایش پیش‌ترتیبی ابتدا گره ریشه مورد بازدید قرار می‌گیرد، سپس زیردرخت چپ و در نهایت زیردرخت راست بازدید می‌شود:

خروجی پیمایش پیش‌ترتیبی در کنسول به صورت زیر خواهد بود:

در روش پیمایش پس‌ترتیبی، ابتدا زیردرخت چپ مورد بازدید قرار می‌گیرد و سپس زیردرخت راست و در نهایت گره ریشه بازدید می‌شود:

خروجی پیمایش پس‌ترتیبی گره‌ها به صورت زیر است:

جستجوی سطح-اول

این نوع جستجو نیز یکی دیگر از روش‌های رایج پیمایش درخت است و در آن ابتدا همه گره‌های یک سطح مورد بازدید قرار می‌گیرند و سپس به سطح بعدی مراجعه می‌شود. این نوع از پیمایش به نام پیمایش ترتیب سطح نیز نامید می‌شود و در آن همه سطوح درخت با آغاز از ریشه و از چپ به راست مورد بازدید قرار می‌گیرد.

برای پیاده‌سازی این نوع جستجو از «صف» (Queue) استفاده می‌کنیم تا گره‌ها را در هر سطح به ترتیب حفظ کنیم. به این منظور هر گره را از لیست استخراج و مقدار آن را پرینت می‌کنیم، سپس فرزندانش را به صف اضافه می‌کنیم:

در این حالت، ترتیب گره‌ها به صورت زیر خواهد بود:

سخن پایانی

در این مقاله با شیوه پیاده‌سازی درخت دودویی در جاوا و رایج‌ترین عملیات مربوط به آن آشنا شدیم. مانند همیشه همه کدهای معرفی شده در این مقاله را می‌توانید در این آدرس گیت‌هاب (+) مشاهده کنید.

اگر این مطلب برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

==

میثم لطفی (+)

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

بر اساس رای 2 نفر

آیا این مطلب برای شما مفید بود؟

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *