در علوم کامپیوتر، درخت ساختار دادهٔ پر استفاده است که شبیه به یک ساختار درختی با مجموعه‌ای از گره‌های متصل به هم است. درخت یک گراف همبند بدون دور است. اکثر نویسندگان این قید را نیز اضافه می‌کنند که گراف باید بدون جهت باشد. یه علاوه بعضی قید بدون وزن بودن یالها را نیز اضافه می‌کنند.

گره‌ها

هر گره در درخت تعدادی( صفر یا بیشتر ) گره فرزند دارد، که در زیر آن در درخت قرار دارند( به طور قراردادی، درخت به سمت پایین رشد می‌کند، برخلاف آنچه در طبیعت می بینیم ). یک گره که فرزند دارد گره پدر آن فرزند گفته می‌شود. یک گره حداکثر 1 پدر دارد. ارتفاع یک گره طول طولانی‌ترین مسیر پایین رو از آن گره به یک برگ است. طول ریشه طول درخت نامیده می‌شود. مسیری که از گره به ریشه وصل می‌شود مسیر ریشه نام دارد و طول این مسیر عمق آن گره است.

گره‌های ریشه

بالاترین گره درخت گره ریشه نام دارد. پس گره ریشه پدر ندارد. این گره گرهی است که عملیات روی درخت معمولاً از آن شروع می‌شود.( هر چند بعضی الگوریتم‌ها از برگ شروع شده و به ریشه ختم می‌شوند ). بقیهٔ گره‌ها با دنبال کردن یالها از گره ریشه قابل دسترسی اند درنمودار درخت عموماً گره ریشه در بالا رسم می‌شود. در بعضی درخت ها، مثل پشته ها، گره ریشه ویژگی‌های خاصی دارند. هر گره در یک درخت را می‌توان ریشهٔ یک زیر درخت در نظر گرفت. که این زیر درخت درختی است ریشه دار که آن گره ریشهٔ آن است.

گره‌های برگ

پایین‌ترین گره‌های یک درخت گره‌های برگ نام دارند. چون این گره‌ها زیرترین گره هستند هیچ فرزندی ندارند.

گره‌های داخلی

یک گره داخلی هر گرهی است که فرزند داشته باشد پس برگها گره داخلی نیستند.

زیر درخت ها

زیر درخت بخشی از درخت است که خود یک درخت کامل را تشکیل می‌دهد. هر گره در درخت T با تمام گره‌های زیر آن زیر درخت درخت T را تشکیل می‌دهد. زیر درخت متناظر با گره ریشه درخت اصلی است. زیر درخت متناظر با بقیهٔ رئوس زیر درخت سره گفته می‌شود.

مرتبهٔ درخت

درخت‌ها دو نوع اصلی هستند. درخت بازگشتی یا درخت نامرتب درختی است که فرزندان هر رأس ترتیب خاصی ندارند و درخت مرتب درختی است که در آن ترتیب خاصی اعمال می‌شود. برای مثال می‌توان به هر رأس عددی طبیعی مربوط کرد.

انواع درختان دودویی

 

چرخش درخت عملیات بسیار رایج روی درختان دودویی خود متعادل است.

• درخت دودویی ریشه‌دار یک درخت با یک گره ریشه است که در آن هر گره حداکثر دو فرزند دارد.
• درخت دودویی پر(گاهی اوقات درخت دودویی مناسب یا ۲_ درخت یا درخت اکیداً دودوییگفته می‌شود) یک درخت که در آن هر گره به غیر از برگ‌ها دارای دو فرزند است. هر گره در درخت دودویی دارای دو فرزند یا بدون فرزند است. یک درخت پر گاهی‌اوقات به‌طور ابهام‌انگیزی به عنوان درخت دودویی کامل تعریف می‌شود. فیزیکدانان یک درخت دودوییرا به‌عنوان درخت دودویی پرتعریف می‌کنند.
  
  

   

  یک تبارنامه که روی یک درخت دودویی کامل به عمق ۴۴ نگاشت شده‌است
• یک درخت دودویی کامل (perfect) یک درخت دودویی پر است که در آن همه برگ‌ها دارای عمق یکسان و یا هم‌سطح باشند، و در آن هر پدری دارای دو فرزند است.(به طور مبهمدرخت دودویی کامل نامیده می‌شود (بعدی را مشاهده کنید).) نمونه‌ای از یک درخت دودویی کامل را می‌توان در تبارنامه از یک فرد به عمق داده‌شده مشاهده کرد، به‌طوری که هر فرد دقیقاً دو پدر و مادر (یک مادر و یک پدر) دارد؛ توجه داشته‌باشید که این معکوس قرارداد معمول درخت پدر فرزند است، و این درختان خلاف جهت معمول هستند (ریشه در پایین).
• یک درخت دودویی کامل (complete) یک درخت دودویی است که در آن هر سطح، به جزاحتمالاً آخرین سطح، به‌طور کامل پر شده‌است، و همهٔ گره‌ها تا جایی که ممکن است در چپ درخت قرار می‌گیرند. درختی که این استثناء را داشته‌باشد که سطح آخر آن کاملاً پر نباشد، درخت دودویی تقریباً کامل یا نزدیک به درخت دودویی کامل گویند. این نوع درختان از ساختمان دادهٔ ویژه‌ای به نام هیپ استفاده می‌کنند.
• درخت دودویی کامل نا محدود درختی است که دارای بی‌نهایت سطح قابل‌شمارش می‌باشد، که در آن هر گره دارای دو فرزند است به‌طوری که گره‌های 2^d در سطح d هستند. مجموعهٔ گره‌ها شمارای نامتناهی است، ولی مجموعه‌ای از بی‌نهایت مسیر از ریشه، ناشمارا است، که دارای عدد کاردینالیتی پیوسته است. این مسیرها رابطهٔ دوسویی را با نقاط مجموعۀ کانتر، یا مجموعه‌ای از اعداد گنگ حفظ می‌کند.
• درختی دودویی متوازن که معمولاً به‌عنوان درخت دودویی است که در آن اختلاف عمق زیردرخت چپ و راست آن ۱ یا کمتر است، اگر چه به طور کلی درخت دودویی است که هیچ برگی نسبت با برگ‌های دیگر فاصلهٔ زیادی تا ریشه ندارد. (طرح توازن متمایز اجازه می‌دهد که تعریف متفاوتی از «بسیار دورتر» ارائه شود) درخت دودویی هنگامی متوازن است که مطابق تعریف عمق آن قابل پیش بینی باشد. (بسیاری از گره‌ها از ریشه تا برگ پیموده می‌شوند، چنان‌که شمارهٔ ریشه به عنوان گرهٔ ۰ و بقیهٔ گره‌ها اعداد ۱ ۲ … n را می‌گیرند) این عمق (ارتفاع هم نامیده می‌شود) برابر قسمت صحیح (log₂(n است، که در آن n تعداد گره‌ها در درخت متوازن است. مثلاً، برای درخت متوازنی که دارای ۱ گره است، log₂(1) = ۰، درنتیجه عمق درخت برابر صفر است. برای یک درخت متوازن با ۱۰۰ گره، log₂(100) = ۶٫۶۴، درنتیجه عمق درخت برابر ۶ است.
• درخت منحط درختی است که هر گرهٔ والدین فقط به یک گرهٔ فرزند متصل است. این به این معنی است که عملکرد این درخت مانند رفتار ساختمان دادهٔ لیست پیوندی است.

فهرست مطالب:

تعریف

مفهوم درخت

مثالی از یک درخت

اصطلاحات درخت ها

نمایش لیست

استفاده از گره با طول ثابت

قضیه

اثبات

نمایش دودویی یک درخت

درخت های دودویی

ساختار درخت دودویی

تفاوت درخت عادی با درخت دودویی

خواص درختان دودیی

نمایش درخت دودویی

نمایش آرایه

نمایش لیست پیوندی

اعضای کلاس Expression

پیمایش درخت دودویی

پیمایش Inorder

پیمایش Preorder

پیمایش Postorder

پیمایش Inorder غیربازگشتی

پیمایش ترتیب سطحی

اعمال مفید بر روی درختان دودویی

درختان نخی دودویی

پیمایش Inorder درخت نخی دودویی

نوع داده مجرد هرم

اعمال اساسی بر روی Heap

صف اولویت

نمایش صف های اولویت

درج عناصر به داخل Max Heap

تحلیل تابع Insert Max Heap

حذف عنصری از Max Heap

تحلیل تابع Delete Max Heap

درختان جستجوی دودویی

تحلیل Search

و...