درخت دودویی (Binary Tree)¶

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

در این قسمت به سه نوع درخت دودویی اشاره می کنیم.

Full Binary Tree¶

درخت دودویی که در آن تمامی راس ها یا دو بچه دارند و یا برگ هستند.

Complete Binary Tree¶

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

Perfect Binary Tree¶

به درختی که تمامی برگ ها در طبقه آخر باشند و تعداد بچه های تمامی راس ها در دیگر طبقات دو باشد گویند.

یکی از بیشترین استفاده ها از درخت دودویی، درخت جست و جوی دودویی است که جلوتر با آن بیشتر آشنا می شویم.