درخت ها
درخت، از مجموعه ای از عناصر به نام گره تشکیل شده است که یکی از گره‌ها ریشه نام دارد. بر خلاف درخت های طبیعی که ریشه آنها در پائین و برگها در بالا قرار دارند، در درخت های کامپیوتری، ریشه در بالا و برگها در پائین قرار دارند.
هر گاه شامل فیلدی برای داده ها است و تعدادی پیوند دارد که به گرههای دیگری وصل می‌شود. گره‌ای که هیچ انشعابی از آن خارج نشود، برگ نام دارد.
درخت‌ها به طور کلی بر دو دسته‌اند: درخت‌های عمومی و درخت‌های دو دویی. درخت دودویی (Binary tree) در ختی از هر گره آن حداکثر دو پیوند خارج می‌شود. درختی که دودویی نباشد، درخت عمومی است.
گره، مسیر و طول مسیر: عناصر درخت را گره گویند. هر گره دارای مسیر منحصر بفردی است که آن را به ریشه درخت وصل می‌کند.
مسیر (path)، دنباله‌ای از گرههای همجوار است. طول مسیر برابر با تعداد اتصال همجوار است که یکی کمتر از تعداد گرههای موجود در آن مسیر است.
عمق گره : طول مسیر آن به گره ریشه است.
عمق درخت: برابر با بیشترین عمق گرههای برگ آن است. معمولاً با d نمایش داده می شود.
سطح گره : هر گره موجود در درخت دودویی دارای سطح است. سطح گره ریشه، صفر در نظر گرفته می‌شود. سطوح بقیه گرهمها یک واحد بیشتر از گره بالایی خویش است.
سطح درخت : بزرگترین سطح برگهای آن است.
ارتفاع درخت: حداکثر تعداد گرههای موجود در مسیری از ریشه به یک گره برگ، ارتفاع درخت نامیده می‌شود. معمولاً با h نمایش داده می‌شود.
شامل 110 صفحه فایل word
دانلود مقاله درخت پشته و لیست پیوندی
