در علوم کامپیوتر، درخت ساختار دادهٔ پر استفاده است که شبیه به یک ساختار درختی با مجموعهای از گرههای متصل به هم است. درخت یک گراف همبند بدون دور است. اکثر نویسندگان این قید را نیز اضافه میکنند که گراف باید بدون جهت باشد. یه علاوه بعضی قید بدون وزن بودن یالها را نیز اضافه میکنند.
گرهها
هر گره در درخت تعدادی( صفر یا بیشتر ) گره فرزند دارد، که در زیر آن در درخت قرار دارند( به طور قراردادی، درخت به سمت پایین رشد میکند، برخلاف آنچه در طبیعت می بینیم ). یک گره که فرزند دارد گره پدر آن فرزند گفته میشود. یک گره حداکثر 1 پدر دارد. ارتفاع یک گره طول طولانیترین مسیر پایین رو از آن گره به یک برگ است. طول ریشه طول درخت نامیده میشود. مسیری که از گره به ریشه وصل میشود مسیر ریشه نام دارد و طول این مسیر عمق آن گره است.
گرههای ریشه
بالاترین گره درخت گره ریشه نام دارد. پس گره ریشه پدر ندارد. این گره گرهی است که عملیات روی درخت معمولاً از آن شروع میشود.( هر چند بعضی الگوریتمها از برگ شروع شده و به ریشه ختم میشوند ). بقیهٔ گرهها با دنبال کردن یالها از گره ریشه قابل دسترسی اند درنمودار درخت عموماً گره ریشه در بالا رسم میشود. در بعضی درخت ها، مثل پشته ها، گره ریشه ویژگیهای خاصی دارند. هر گره در یک درخت را میتوان ریشهٔ یک زیر درخت در نظر گرفت. که این زیر درخت درختی است ریشه دار که آن گره ریشهٔ آن است.
گرههای برگ
پایینترین گرههای یک درخت گرههای برگ نام دارند. چون این گرهها زیرترین گره هستند هیچ فرزندی ندارند.
گرههای داخلی
یک گره داخلی هر گرهی است که فرزند داشته باشد پس برگها گره داخلی نیستند.
زیر درخت ها
زیر درخت بخشی از درخت است که خود یک درخت کامل را تشکیل میدهد. هر گره در درخت T با تمام گرههای زیر آن زیر درخت درخت T را تشکیل میدهد. زیر درخت متناظر با گره ریشه درخت اصلی است. زیر درخت متناظر با بقیهٔ رئوس زیر درخت سره گفته میشود.
مرتبهٔ درخت
درختها دو نوع اصلی هستند. درخت بازگشتی یا درخت نامرتب درختی است که فرزندان هر رأس ترتیب خاصی ندارند و درخت مرتب درختی است که در آن ترتیب خاصی اعمال میشود. برای مثال میتوان به هر رأس عددی طبیعی مربوط کرد.
انواع درختان دودویی
- درخت دودویی ریشهدار یک درخت با یک گره ریشه است که در آن هر گره حداکثر دو فرزند دارد.
- درخت دودویی پر(گاهی اوقات درخت دودویی مناسب یا ۲_ درخت یا درخت اکیداً دودویی گفته میشود) یک درخت که در آن هر گره به غیر از برگها دارای دو فرزند است. هر گره در درخت دودویی دارای دو فرزند یا بدون فرزند است. یک درخت پر گاهیاوقات بهطور ابهامانگیزی به عنوان درخت دودویی کامل تعریف میشود. فیزیکدانان یک درخت دودویی را بهعنوان درخت دودویی پر تعریف میکنند.یک تبارنامه که روی یک درخت دودویی کامل به عمق ۴۴ نگاشت شدهاست
- یک درخت دودویی کامل (perfect) یک درخت دودویی پر است که در آن همه برگها دارای عمق یکسان و یا همسطح باشند، و در آن هر پدری دارای دو فرزند است.(به طور مبهم درخت دودویی کامل نامیده میشود (بعدی را مشاهده کنید).) نمونهای از یک درخت دودویی کامل را میتوان در تبارنامه از یک فرد به عمق دادهشده مشاهده کرد، بهطوری که هر فرد دقیقاً دو پدر و مادر (یک مادر و یک پدر) دارد؛ توجه داشتهباشید که این معکوس قرارداد معمول درخت پدر\ فرزند است، و این درختان خلاف جهت معمول هستند (ریشه در پایین).
- یک درخت دودویی کامل (complete) یک درخت دودویی است که در آن هر سطح، به جز احتمالاً آخرین سطح، بهطور کامل پر شدهاست، و همهٔ گرهها تا جایی که ممکن است در چپ درخت قرار میگیرند. درختی که این استثناء را داشتهباشد که سطح آخر آن کاملاً پر نباشد، درخت دودویی تقریباً کامل یا نزدیک به درخت دودویی کامل گویند. این نوع درختان از ساختمان دادهٔ ویژهای به نام هیپ استفاده میکنند.
- درخت دودویی کامل نا محدود درختی است که دارای بینهایت سطح قابلشمارش میباشد، که در آن هر گره دارای دو فرزند است بهطوری که گرههای 2d در سطح d هستند. مجموعهٔ گرهها شمارای نامتناهی است، ولی مجموعهای از بینهایت مسیر از ریشه، ناشمارا است، که دارای عدد کاردینالیتی پیوسته است. این مسیرها رابطهٔ دوسویی را با نقاط مجموعۀ کانتر، یا مجموعهای از اعداد گنگ حفظ میکند.
- درختی دودویی متوازن که معمولاً بهعنوان درخت دودویی است که در آن اختلاف عمق زیردرخت چپ و راست آن ۱ یا کمتر است، اگر چه به طور کلی درخت دودویی است که هیچ برگی نسبت با برگهای دیگر فاصلهٔ زیادی تا ریشه ندارد. (طرح توازن متمایز اجازه میدهد که تعریف متفاوتی از «بسیار دورتر» ارائه شود) درخت دودویی هنگامی متوازن است که مطابق تعریف عمق آن قابل پیش بینی باشد. (بسیاری از گرهها از ریشه تا برگ پیموده میشوند، چنانکه شمارهٔ ریشه به عنوان گرهٔ ۰ و بقیهٔ گرهها اعداد ۱ ۲ … n را میگیرند) این عمق (ارتفاع هم نامیده میشود) برابر قسمت صحیح (log2(n است، که در آن n تعداد گرهها در درخت متوازن است. مثلاً، برای درخت متوازنی که دارای ۱ گره است، log2(1) = ۰، درنتیجه عمق درخت برابر صفر است. برای یک درخت متوازن با ۱۰۰ گره، log2(100) = ۶٫۶۴، درنتیجه عمق درخت برابر ۶ است.
- درخت منحط درختی است که هر گرهٔ والدین فقط به یک گرهٔ فرزند متصل است. این به این معنی است که عملکرد این درخت مانند رفتار ساختمان دادهٔ لیست پیوندی است.
فهرست مطالب:
تعریف
مفهوم درخت
مثالی از یک درخت
اصطلاحات درخت ها
نمایش لیست
استفاده از گره با طول ثابت
قضیه
اثبات
نمایش دودویی یک درخت
درخت های دودویی
ساختار درخت دودویی
تفاوت درخت عادی با درخت دودویی
خواص درختان دودیی
نمایش درخت دودویی
نمایش آرایه
نمایش لیست پیوندی
اعضای کلاس Expression
پیمایش درخت دودویی
پیمایش Inorder
پیمایش Preorder
پیمایش Postorder
پیمایش Inorder غیربازگشتی
پیمایش ترتیب سطحی
اعمال مفید بر روی درختان دودویی
درختان نخی دودویی
پیمایش Inorder درخت نخی دودویی
نوع داده مجرد هرم
اعمال اساسی بر روی Heap
صف اولویت
نمایش صف های اولویت
درج عناصر به داخل Max Heap
تحلیل تابع Insert Max Heap
حذف عنصری از Max Heap
تحلیل تابع Delete Max Heap
درختان جستجوی دودویی
تحلیل Search
و...
پاورپوینت کامل و جامع با عنوان درخت در کامپیوتر در 100 اسلاید
