مشارکت فارکسی در افغانستان

درخت باینری

برای هر درخت دودویی در صورتی که درخت تهی نباشد تعداد گره های پایانی همواره یکی بیشتر از تعداد گره هایی است که دارای دو فرزند هستند.

ساختار داده های درخت باینری

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

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

  • داده ها
  • اشاره به سمت چپ کودک
  • به کودک مناسب اشاره کنید.

در صورتی که گره فرزندی نداشته باشد، اشاره گر به null اشاره می کند.

پیاده سازی درختان در جاوا

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

//برنامه زیر یک درخت ساده را تنظیم می کند که ساختار زیر را دارد:

ویژگی های درخت دودویی

  • یک درخت باینری می تواند حداکثر 2 داشته باشد i گره های سطح i. ریشه یک درخت سطح 0 در نظر گرفته می شود. بنابراین 2^0 = 1 یعنی در سطح ریشه درخت فقط می تواند یک گره داشته باشد. در سطح یک: 2^1 = 2 گره و غیره.
  • یک درخت باینری با ارتفاع 'h' حداکثر 2 خواهد داشت h – 1 درخت باینری تعداد گره ها اگر ارتفاع درختی 4 باشد، حداکثر می تواند 2^(4-1) = 8 گره داشته باشد.
  • فرمول بدست آوردن حداقل ارتفاع یا سطوح یک درخت باینری از گره های N به شرح زیر است: Log2 (N + 1).
  • اگر یک درخت دودویی دارای L تعداد برگ باشد (برگ‌ها بچه ندارند)، حداقل تعداد لایه‌هایی که درخت خواهد داشت با فرمول Log به دست می‌آید.2L + 1.
  • اگر در یک درخت دودویی، هر گره 0 یا 2 فرزند داشته باشد، تعداد کل برگ ها (گره هایی با 0 فرزند) همیشه یک بیشتر از گره هایی خواهد بود که دو فرزند دارند.

تراورس

اجازه دهید درخت زیر را همانطور که قبلا ارائه شد در نظر بگیریم تا در مورد پیمایش صحبت کنیم.

آموزش تشخیص BST بودن یک درخت باینری (Binary Tree)

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

  • در همه موارد عناصر زیردرخت راست از ریشه بزرگ‌تر است.
  • در همه موارد عناصر زیردرخت چپ از ریشه کوچک‌تر است
  • زیردرخت سمت چپ و زیردرخت سمت راست خود یک BST هستند.

مورد آخر به این معنی است که هر نودی را که شما در نظر بگیرید از ۲ قاعده اول تبعیت می کنند. با توجه به مواردی که گفته شد یک BST هیچ‌وقت عضو تکراری ندارد. در شکل زیر یک BST را می بینید.

در این مطلب می‌خواهیم مسأله گفته شده را حل کنیم یعنی یک درخت باینری داریم و می‌خواهیم مشخص کنیم که این درخت BST است یا خیر.ایده این کار به این صورت است که به صورت inorder درخت را پیمایش می‌کنیم و هر بار مقدار درخت باینری نود قبلی را نگهداری می کنیم. به خاطر اینکه پیمایش inorder یک BST باعث به وجود آمدن یک آرایه مرتب می‌شود پس در هر بار پیمایش باید مقدار قبلی ازمقدار کنونی کمتر باشد. در غیر این صورت درخت BST نیست. کد c++ این برنامه در ادامه آورده شده است.

دقت کنید که در کد بالا همانطور که BST را به صورت بازگشتی تعریف کردیم تابع isBSTUtil نیز به صورت بازگشتی تعریف شده است تا بتواند پیمایش inorder را به راحتی انجام دهد. همچنین برای بار اول مقدار prev برابر با کوچکترین عدد int قرار داده شده است.با وب سایت tosinso همراه باشید.

نویسنده: مهدی عادلی فر

هرگونه نشر و کپی برداری بدون ذکر منبع و نام نویسنده دارای اشکال اخلاقی می باشد.

مهدی عادلی فر

بنیانگذار توسینسو و برنامه نویس

مهدی عادلی، بنیان گذار TOSINSO. کارشناس ارشد نرم افزار کامپیوتر از دانشگاه صنعتی امیرکبیر و #C و جاوا و اندروید کار می کنم. در زمینه های موبایل و وب و ویندوز فعالیت دارم و به طراحی نرم افزار و اصول مهندسی نرم افزار علاقه مندم.

مقالات مرتبط

دیدگاهتان را بنویسید

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

برو به دکمه بالا