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

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

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

Full Binary Tree

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

Complete Binary Tree

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

Perfect Binary Tree

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

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