بعض الإجرائيات الخاصة بالأشجار الثنائية

من ويكي الهندسة المعلوماتية
اذهب إلى: تصفح، ابحث
لأعتبر أن لدي تعبير ثنائي ممثل على شجرة ثنائية بحيث :
1.JPG

تكون العقد الداخلية عبارة عن عمليات .

والعقد الخارجية(الأوراق) عبارة عن معاملات .

كالشجرة المبينة في الشكل التالي :










أريد طباعة عناصر الشجرة بثلاث طرق : infix - prefix - postfix

أولاً : الطباعة بطريقة الـ postfix :

أي سنطبعها بالشكل التالي :

print postfix (T:tree)
	if (T<>nill)
		postfix(T^.l)
		postfix(T^.R)
		Write (T^.value)

ثانياً : الطباعة بطريقة الـ prefix :

أي سنطبعها بالشكل التالي :

print prefix (T:tree)
	if (T<>nill)
		Write (T^.value)
		prefix(T^.l)
		prefix(T^.R)

ثالثاً : الطباعة بطريقة الـ infix :

أي سنطبعها بالشكل التالي :

فلنلاحظ هنا أنه يمكن أن يكون هناك خطأ في التعبير لأننا لا نعرف ما هو الترتيب الصحيح بل تكون العمليات بناءً على الأولوية ..

(مثلاً لو اعتبرنا في الرسم السابق أنه بدل عملية الجمع يوجد ضرب وبدل الضرب لدينا جمع .. مثلاً (( فعندما نرتب التعبير بطريقة الـinorder سيكون شكله كالتالي: A*B+C وهنا يتبين لدينا الخطأ .. لأننا حسب الشجرة المرسومة(التي اعتبرناها) نريد ناتج التعبير التالي: وليس .. وهكذا نجد أننا بحاجة لوضع الأقواس هُنا ))

procedure infix (T:tree)
	if (not leaf(T)) 
		print ("(")
		infix (T^.L)
		print (T^.value)
		infix (T^.R)
		print (")")
	else
	    print (T^.value)


تابع حساب ارتفاع شجرة

function height (T:  tree  ) :integer ;
    if (T==NULL)
         height <-- 0 ;
    else if (T==leaf)
         height <-- 0 ;
    else
         height <-- 1 + max(height(T^.R),height(T^.L));


تابع حساب عرض شجرة

size : array [1..h] of integer ;
 function width (T: tree ,level:integer  ) :integer ;
   if (T<>NULL)
         size[level] <-- size[level]+1;
         width (T^.R,level+1);
         width (T^.L,level+1);
    width <-- max (size) ;


إجرائية طباعة طريق عقدة في شجرة ثنائية (ليست شجرة بحث)

procedure print (T: tree ,x:integer,var b:bool  ) :integer ;
   if (T<>NULL)
      if (T^.value == x )
           b <-- true ;
           write (T^.value);
      else
           print (T^.L ,x , b);
           if (! b )
               print (T^.R,x,b);
           else
               write (T^,value);

تابع حساب حجم شجرة

function vol (T:tree):integer
	if (T<>nill)
		vol= 1 + vol(T^.L)+vol(T^.R)
	else
	    vol=0

إجرائية لحساب مسافة التجول في الشجرة

procedure LC (T:tree,level:integer , var sum:integer)
	if (T<>nill)
		sum = sum + level 
		LC(T^.L,level+1,sum)
		LC(T^.R,level+1,sum)

إجرائية لحساب مسافة التجول الداخلي في الشجرة

procedure LCI (T:tree,level:integer , var sum:integer)
	if (T<>nill)
	 	if not leaf(T)
			sum = sum + level 
		LC(T^.L,level+1,sum)
		LC(T^.R,level+1,sum)

إجرائية لحساب مسافة التجول الخارجي في الشجرة

procedure LCE (T:tree,level:integer , var sum:integer)
	if (T<>nill)
	 	if leaf(T)
			sum = sum + level 
		else
			LC(T^.L,level+1,sum)
			LC(T^.R,level+1,sum)