• بازدید : 52 views
  • بدون نظر
این فایل در ۶۶صفحه قابل ویرایش تهیه شده وشامل موارد زیر است:
یک درخت مجموعه ای متناهی ازیک یا بیشترگره می باشد، به طوریکه :
۱- یک گره خاص به عنوان ریشه در نظر گرفته می شود.
۲- بقیه ی گره ها به  n ≥ ۰  مجموعه ی جدا ازهم T1,T2,…,Tn  افراز می شوند که هرکدام یک درخت هستند. 
هرکدام ازمجموعه ها یک زیردرخت نامیده می شوند.(تعریف بازگشتی)
شرط جدا بودن مجموعه ها مانع از اتصال زیر درخت ها می شود.
در ادامه برای آشنایی بیشتر شما توضیحات مفصلی میدهیم
درجه یک گره: تعداد زیردرختهای یک گره درجه آن گره خوانده می شود. 
deg(A)=2 , deg(C)=3   
برگ : گره با درجه ی صفر برگ یا گره پایانی نامیده می  شود.(D,E,F,G,H)
فرزندان یک گره : ریشه های زیر درخت های آن گره می باشند.( H فرزند C می باشد.)
پدر یک گره : گره x پدر y است اگر فرزند x باشد.(C پدرH است )
به فرزندان یک پدر برادریا همزاد یا  sibling گفته می شود.
درجه ی یک درخت : درجه ی گره ای ازآن درخت است که حداکثر درجه را دارد.(درجه ی درخت داده شده ۳ است .)
اجداد یک گره: تمام گرههایی هستند که درمسیرریشه به آن گره قراردارند.(اجداد گره F
A,C     هستند.)
سطح یک گره : ریشه را درسطح يك درنظرمی گیریم . 
اگریک گره درسطح L باشد  فرزندان آن گره درسطح L+1 می باشند. ( گره F درسطح ۲ می باشد)
ریشه را می توان درسطح صفرنیزدرنظرگرفت.
 ارتفاع یا عمق درخت : حداکثرسطح گره های درخت را عمق درخت می گویند. (عمق درخت شکل برابر۳ است .)
درخت k تایی : یک درخت ازدرجه یk  یک درخت  kتایی نامیده می شود.
درخت متوازن : درختی که اختلاف سطح برگ های آن حداکثر۱می باشد.
درخت کاملاً متوازن : درختی که اختلاف سطح برگ های آن ۰ می باشد. 
درخت k تایی پر: درخت کاملاً متوازن که درجه ی تمام گره ها به جزبرگها k باشد. 
درخت k  تایی کامل : یک درخت k تایی با n گره وعمق L یک درخت  kتایی کامل است اگر وتنهااگرگره های آن با شماره گذاری از۱تاn منطبق برگره های شماره گذاری شده  دریک درخت k تایی پرباعمقL باشد.(نحوه ی شماره گذاری به این صورت است که به ریشه عدد یک را نسبت می دهیم وسپس گره های هرسطح به ترتیب از چپ به راست شماره گذاری می شوند.)
چگونه یک درخت درحافظه ذخيره مي شود؟
 
۱- نمایش یک درخت به صورت یک رشته ی بازگشتی : 
ابتدا اطلاعات ریشه و سپس در داخل پرانتز اطلاعات فرزندان هر گره به ترتیب از چپ به راست ذکر می شود . به عبارت دیگر با یک تعریف بازگشتی داریم : 
           (( نمایش پرانتزی زیردرختn  ام ، … ، نمایش پرانتزی زیر درخت اول) ریشه)
چگونه یک درخت درحافظه ذخيره مي شود؟
 2- نمایش درخت با استفاده ازلیست های پیوندی : دراین طرز نمایش فرزندان هر گره در سمت راست آن ذکرمی شوند ولی هر فرزندی که خود برگ نباشد با افزودن یک سطح به لیست نمایش داده می شود .
چگونه یک درخت درحافظه ذخيره مي شود؟
۳- پیاده سازی به فرم یک درخت k تایی ثابت 
     دراین نوع نمایش هرگره درخت به وسیله ی یک المان با طول ثابت ، شامل داده واشاره گرهایی به گره های فرزند می باشد تعداد اشاره گر ها درهر المان برابر درجه ی درخت می باشد . (الگوریتم ها ساده تر) 
چگونه یک درخت درحافظه ذخيره مي شود؟
۴- روش فرزند چپ – همزاد راست : گره مورد استفاده در این نمایش به این صورت می باشد

برای تبدیل یک درخت به این نمایش:
ابتدا کلیه نودهاي همزاد به هم متصل شده
فقط سمت  چپ ترین فرزند به والد خود متصل مي ماند. 
چون دردرختها ترتیب فرزندان اهمیت ندارد ، درخت یکتایی را نتیجه نمی دهد

عتیقه زیرخاکی گنج