الأشجار الثنائية

من ويكي الهندسة المعلوماتية
اذهب إلى: تصفح، ابحث

نقول عن شجرة B أنها ثنائية إذا كانت درجتها =2 أي أن لكل عقدة ولدان على الأكثر .

حالات خاصة

الشجرة الخطية

هي الشجرة التي يكون لكل عقدة فيها ابن وحيد فقط . يكون ارتفاع هذه الشجرة عادةً = n-1

الشجرة التامة

هي الشجرة التي يكون لكل عقدة فيها ابنان اثنان. ويكون لكل الأوراق فيها نفس الارتفاع. يكون ارتفاع هذه الشجرة عادةً =

الشجرة الكاملة

هي الشجرة التي تكون كل المستويات فيها ممتلئة ما عدا المستوى الأخير فيمكن ان يكون غير ممتلئ. لكن بشرط أن تكون الأوراق كلها في يسار المستوى الأخير ما أمكن، أي تُملأ العقد في المستوى الأخير من اليسار نحو اليمين ونقف حيث نشاء.

نظريات

ارتفاع الشجرة

إن ارتفاع الشجرة الثنائية أصغر من n-1 وأكبر من ، أي:

عرض الشجرة

هو أكبر عدد عقد في مستوٍ من مستويات الشجرة.

خوارزمية حساب عرض الشجرة

نقوم بحساب عدد الأوراق في كل مستو من مستويات الشجرة ويتم تخزين العدد بمصفوفة أحادية وليكن بعدها يساوي عدد مستويات الشجرة ومن ثم نختار القيمة الأعلى لعدد الأوراق في كل مستو من المصفوفة السابقة والتي تمثل عرض الشجرة .

علاقة ارتفاع الشجرة بعدد الأوراق

كل شجرة ثنائية B تحوي f ورقة، يكون ارتفاعها H، أكبر أو يساوي

الحد الأعلى والأدنى لمسافة التجوال ضمن شجرة LC

إن مسافة التجوال محصورة كما يلي:


الحد الأدنى للارتفاع الوسطي للأوراق PF

نعرف الارتفاع الوسطي للأوراق على أنه متوسط ارتفاع الأوراق:

تنفيذ الأشجار الثنائية في الحواسيب

خوارزمية التجوال الكلي

function LCE (T:  tree , My level : integer ) : integer ; 
 
if ( T = NIL ) 
 LC := 0 
else 
 lc := My leavel + LCE(T^.R,Mylevel+1)+LCE(T^.L,MYlevel +1)

التجوال ضمن شجرة

وهي عملية المرور على كل عقد الشجرة .. لمعالجتها (طباعتها مثلا).. ليكن لدينا الشجرة الثانية إن الشكل العام للتجوال ضمن الشجرة .. (أي بكل الحالات ..)

procedure tranversal (T:  tree  ) ;
if ( T <> NIL ) 
 {
    Process1
    tranversal(L) 
    Process2
    tranversal(R)
    Process3
else 
    endtranversal
 }


  • الترتيب النظامي Inorder:

وفيه يكون:

process1 = process3 = null

process 2 <> null

أي اننا نقوم بالاستدعاء العودي للشجرة الجزئية اليسارية .. ثم نقوم بمعالجة العقدة (طباعتها مثلا) .. ثم نستدعي من أجل الشجرة الجزئية اليمينية

  • الترتيب الملحق Preorder:

وفيه يكون:

process2 = process3 = null

process 1 <> null

أي اننا نقوم بمعالجة العقدة أولا،' ثم' بالاستدعاء العودي للشجرة الجزئية اليسارية، ثم الاستدعاء من أجل الشجرة الجزئية اليمينية

  • الترتيب المصدر Postorder:

وفيه يكون:

process1 = process2 = null

process 3 <> null

أي اننا نقوم بالاستدعائين العوديين للشجرتين الجزئيتن اليسارية ثم اليمينية ثم بمعالجة العقدة.


أنواع الأشجار الثنائية

انظر أيضاً