پاورپوینت آشنایی با درخت

بخشی از پاورپوینت

اسلاید 1 :

آشنايي با درخت
درخت هاي دودويي
پيمايش درختان
هرم
جنگل
فصل پنجم : درخت
اهداف

اسلاید 2 :

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

اسلاید 3 :

مفهوم درخت
درخت مجموعه محدودي از يک يا چند گره به صورت زير مي باشد :

داراي گره خاصي به نام ريشه باشد.

بقيه گره ها به n ≥ 0 مجموعه مجزا تقسيم شده که هر يک از اين مجموعه ها خود يک درخت هستند. زير درختان ريشه ناميده مي شوند.

اسلاید 4 :

به عنصر حاوي اطلاعات و انشعابات به ديگر عناصر، گره اطلاق مي شود.
تعداد زير درختهاي يك گره، درجه آن ناميده ميشود
گره اي كه درجه آن صفر باشد، برگ يا گره پاياني ناميده ميشود و در مقابل بقيه گرهها گره هاي غيرپاياني ناميده ميشوند.
گره ريشه را در هر زير درخت گره پدر(والد) و به گرههاي متصل شده به آن گره فرزند ميگويند
فرزنداني كه پدر يكسان دارند برادر (يا همزاد) ناميده ميشوند
تعريف

اسلاید 5 :

مثالي از يک درخت
A والد B ، C، D است . B ، C، D همزادند.
درجه A = 3
شکل1-5

اسلاید 6 :

اجداد گره : اجداد يک گره ، گره هايي هستند که در مسير طي شده از ريشه تا آن گره وجود دارند.

سطح گره : سطح يک گره بدين صورت تعريف مي شود که ريشه در سطح يک قرار مي گيرد. براي تمامي گره هاي بعدي ، سطح گره برابر است با سطح والد به اضافه يک .

ارتفاع درخت : ارتفاع يا عمق يک درخت به بيشترين سطح گره هاي آن درخت گفته مي شود.
اصطلاحات درخت ها

اسلاید 7 :

نمايش ليست
يک راه نمايش درخت ، استفاده از ليست است .
شکل 1-5 را مي توان به صورت زير نشان داد :

(A(B(E(K ،L)،F)،C(G)،D(H(M)،I،J)))

اسلاید 8 :

اگر بخواهيم براي نگهداري يك درخت ساختمان داده اي مانند نمايش معمول (هر گره آدرس گره هاي فرزند خود را داشته باشد) تعريف كنيم مشكل زير بوجود ميآيد:
درجه تمام درختها يكي نميباشد لذا مجبور خواهيم شد براي هر گره تعداد متغيري از اشاره گرها داشته باشيم. با اين وجود، نوشتن الگوريتم براي گرههايي كه طول متغير دارند دشوار خواهد شد
براي حل مشكل بايد از گره هايي با طول ثابت استفاده كنيم.

اسلاید 9 :

استفاده از گره با طول ثابت
اگر بيشترين درجه درخت k باشد بنابراين هر گره بايد توانايي نگهداري k اشاره گر را داشته باشد و ساختمان داده اي به شكل زير بايد تعريف كنيم.

اسلاید 10 :

اگر T درختي از درجه k با n گره باشد و هر گره آن مانند شكل قبل طول ثابتي داشته باشد آنگاه n(k-1)+1 از nk فيلد بچه آن (اشاره گرهاي به فرزند) برابر 0 (NULL) است.

اثبات:
از آنجا كه هر فيلد بچه غير صفر به يك گره اشاره ميكند و براي هر گره غير از ريشه يك اشاره گر وجود دارد از اينرو تعداد فيلدهاي بچه غيرصفر براي درختي با n گره دقيقاً برابر n-1 است. تعداد كل فيلدهاي بچه براي درختي با n گره از درجه k برابر nk ميباشد. لذا:
تعداد اشاره گرهاي بچه NULL : nk-(n-1)=n(k-1)+1
قضيه

اسلاید 11 :

براي درختان دو نمايش خاص كه از گرههايي با طول ثابت استفاده ميكند ارائه ميكنيم.
الف) نمايش درخت بصورت بچه چپ-همزاد راست
ب) نمايش درخت بصورت يك درخت درجه 2.

اسلاید 12 :

براي نمايش درختان دودويي ، دقيقا نياز به دو اتصال يا اشاره گر به ازاي هر گره است.
نمايش دودويي يک درخت

اسلاید 13 :

بصورت بچه چپ-همزاد راست

اسلاید 14 :

بصورت درخت درجه 2

اسلاید 15 :

2-5 درخت هاي دودويي
مشخصه اصلي يک درخت دودويي بدين شکل است که هر گره آن حداکثر دو انشعاب دارد يعني گره هايي که درجه اي بيشتر از دو نداشته باشند.
براي درخت هاي دودويي زير درخت سمت چپ و راست با يکديگر متمايز است.
يک درخت دودويي يا تهي است يا حاوي مجموعه اي محدود از گره ها شامل يک ريشه و دو زير درخت دودويي است. اين درخت ها زير درخت هاي چپ و راست ناميده مي شوند.
تعريف :

اسلاید 16 :

2-5 ساختار درخت دودويي
structure Binary_tree (abbreviated BinTree ) is
objects : a finite set of nodes either empty or consisting of
a root node ، left Binary_tree ، and right Binary_tree.
functions :
for all bt ، bt1 ، bt2 BinTree ، item element
BinTree Create()
Boolean IsEmpty (bt)
BinTree MakeBT(bt1 ، item ، bt 2)
BinTree Lchild(bt)
element Data(bt)
BinTree Rchild(bt)

اسلاید 17 :

در هيچ درخت عادي صفر گره وجود ندارد ، اما درخت دودويي تهي وجود دارد.

در يک درخت دودويي ترتيب فرزندان داراي اهميت بوده در حالي که در درخت عادي به اين صورت نيست.
2-5 تفاوت درخت عادي با درخت دودويي

اسلاید 18 :

2-5 خواص درختان دودويي
حداکثر تعداد گره ها در سطح i ام يک درخت دودويي 2i-1 است.

حداکثر تعداد گره ها در يک درخت دودويي به عمق k ، 2k-1 است.
حداکثر تعداد گره ها

اسلاید 19 :

2-5 خواص درختان دودويي
رابطه بين تعداد گره هاي برگ و گره هاي درجه 2

اسلاید 20 :

2-5 خواص درختان دودويي
يک درخت دودويي پر به عمق k ، يک درخت دودويي پر است مشروط به اينكه 2k-1 گره داشته باشد.
يک درخت دودويي با n گره و عمق k کامل است ، اگر و تنها اگر گره هايش مطابق با گره هاي شماره گذاري شده در يک درخت دودويي پر به عمق k باشد.
ارتفاع يك درخت دودويي كامل با n گره برابر است