پاورپوینت مبحث درختها ساختمان داده ها

66 صفحه

بصورت پاورپوینت

ppt

یک درخت مجموعه متناهی ازیک بیشترگره باشد، طوریکه :

1- یک گره خاص عنوان ریشه نظر گرفته شود.

2- بقیه گره به  n ≥ 0  مجموعه جدا ازهم T1,T2,…,Tn  افراز شوند هرکدام یک درخت هستند.

 

 

هرکدام ازمجموعه یک زیردرخت نامیده شوند.(تعریف بازگشتی)

شرط جدا بودن مجموعه مانع اتصال زیر درخت شود.

 

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

-درجه یک گره:تعداد زیردرختهای یک گره درجه گره خوانده شود.

deg(A)=2 , deg(C)=3  

-برگ : گره درجه صفر برگ گره پایانی نامیده می  شود.(D,E,F,G,H)

-فرزندان یک گره: ریشه زیر درخت گره باشند.( H فرزند C باشد.)

 

پدر یک گره: گره x پدر y اگر فرزند x باشد.(C پدرH )

به فرزندان یک پدر برادریا همزاد  sibling گفته شود.

درجه یک درخت: درجه گره ازان درخت حداکثر درجه دارد.(درجه درخت داده شده 3 است .)

اجداد یک گره: تمام گرههایی هستند درمسیرریشه گره قراردارند.(اجداد گره F

A,C     هستند.)

 

سطح یک گره : ریشه درسطح یک درنظرمی گیریم .

–اگریک گره درسطح L باشد  فرزندان گره درسطح L+1 باشند. ( گره F درسطح 2 باشد)

–ریشه توان درسطح صفرنیزدرنظرگرفت.

ارتفاع عمق درخت: حداکثرسطح گره درخت عمق درخت گویند. (عمق درخت شکل برابر3 .)

 

جنگل : مجموعه n≥0 درخت مجزا جنگل گفته شود.

–جنگل تواند تهی باشد.

 

...نمایش درختها...

چگونه یک درخت درحافظه ذخیره شود؟

 

1- نمایش یک درخت صورت یک رشته بازگشتی :

ابتدا اطلاعات ریشه سپس داخل پرانتز اطلاعات فرزندان هر گره ترتیب چپ راست ذکر شود . عبارت دیگر یک تعریف بازگشتی داریم :

           (( نمایش پرانتزی زیردرختn  ام ، ... ، نمایش پرانتزی زیر درخت اول) ریشه)

 

...66 اسلاید پاورپوینت...