درخت دودویی

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

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

Binary Tree

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

Full Binary Tree

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

Full Binary Tree

Complete Binary Tree

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

Complete Binary Tree

Perfect Binary Tree

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

Perfect Binary Tree

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