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