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

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


.. figure:: /_static/dot/Binary_Tree.svg
   :width: 60%
   :align: center
   :alt: Binary Tree

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

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

.. figure:: /_static/dot/Full_Binary_Tree.svg
   :width: 60%
   :align: center
   :alt: Full Binary Tree

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

.. figure:: /_static/dot/Complete_Binary_Tree.svg
   :width: 60%
   :align: center
   :alt: Complete Binary Tree

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

.. figure:: /_static/dot/Perfect_Binary_Tree.svg
   :width: 60%
   :align: center
   :alt: Perfect Binary Tree

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